Transformacija matrice
vreme | memorija | ulaz | izlaz |
---|---|---|---|
2 s | 128 Mb | standardni izlaz | standardni ulaz |
Nakon duge igre sa brojevima, Mabu i Džo su rešili da promene temu njihove zabave. Sada su na red došle matrice! Mabu je napisao na papiru kvadratnu matricu , dok je Džo napisao kvadratnu matricu . Obe kvadratne matrice su iste dimenzije i ona iznosi ( svaka matrica ima tačno vrsta i kolona ).
Kada su napisali matrice na papiru, Mabu je odjednom poželeo da promeni svoju matricu u onu koju je Džo napisao ( želeo je da transformiše matricu u matricu ). Za ovaj poduhvat Mabu sme da koristi sledeće dve operacije proizvoljan broj puta u proizvoljnom redosledu:
Promena vrednosti jednog elementa u matrici - element može da se zameni proizvoljnom vrednošću
Rotacija matrice za stepeni u desno.
Mabua interesuje minimalan broj operacija koje mora da izvrši na matrici kako bi dobio matricu .
Opis ulaza
Prva linija standardnog ulaza sadrži prirodan broj , dimenziju kvadratnih matrice koje su napisali Mabu i Džo.
Sledećih linija standarnog ulaza sadrži po prirodnih brojeva koji predstaljaju matricu .
Poslednjih linija standarnog ulaza sadrži po prirodnih brojeva koji predstaljaju matricu .
Opis izlaza
U jedinoj liniji standardnog izlaza ispisati minimalan broj operacija potrebnih da se matrica transformiše u matricu .
Primer
Ulaz
2 1 2 3 8 6 1 8 5
Izlaz
3
Primer
Ulaz
1 5 5
Izlaz
0
Objašnjenje primera
U prvom primeru matricu možemo transformisati u matricu sa najmanje koraka.
Promena vrednosti polja (, ) ,
Rotacija matrice za stepeni u desno
Promena vrednosti polja (, ) ,
U drugom primeru matrice i imaju samo po jedan element i on ima vrednost u obe matrice. Nije potrebno izvršiti neku operaciju, tako da je rešenje
Ograničenja
Test primeri su podeljeni u disjunktne grupe :
U test primerima vrednim poena važiće ograničenje .
U test primerima vrednim poena za optimalno rešenje biće potrebne samo operacije prvog tipa.
U test primerima vrednim poena važiće ograničenje .
U test primerima vrednim poena nema dodatnih ograničenja.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.