Code Submission Evaluation System Login

Datatähti 2018 loppu

Start:2018-01-18 12:15:00
End:2018-01-18 17:15:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2018 loppu - VaihdotCSES - Vaihdot

Vaihdot

Time limit:1.00 s
Memory limit:512 MB

Annettuna on kaksi $n \times n$ -ruudukkoa, joista molemmat sisältävät kokonaisluvut $1,2,\ldots,n^2$ jossain järjestyksessä. Ruudukon rivit ja sarakkeet on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Käytössäsi on seuraavat operaatiot:
  1. vaihda keskenään kaksi riviä
  2. vaihda keskenään kaksi saraketta
Tehtäväsi on muuttaa ensimmäinen ruudukko toiseksi operaatioiden avulla niin, että operaatioiden määrä on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: ruudukoiden koko.

Sitten syötteessä on $n$ riviä, jotka kuvaavat ensimmäisen ruudukon, ja lopuksi $n$ riviä, jotka kuvaavat toisen ruudukon.

Tuloste

Tulosta ensin kokonaisluku $k$: pienin operaatioiden määrä. Tulosta sitten $k$ riviä, jotka sisältävät operaatiot järjestyksessä.

Jokaisen operaation tulee olla muotoa "$1$ $a$ $b$" (vaihda rivit $a$ ja $b$) tai "$2$ $a$ $b$" (vaihda sarakkeet $a$ ja $b$).

Jos mitään ratkaisua ei ole olemassa, tulosta vain luku $-1$.

Esimerkki 1

Syöte:
3
1 2 3
4 5 6
7 8 9
2 1 3
8 7 9
5 4 6


Tuloste:
2
2 1 2
1 2 3


Esimerkki 2

Syöte:
3
6 3 7
8 1 4
9 2 5
8 5 2
7 3 1
9 4 6


Tuloste:
-1

Osatehtävä 1 (12 pistettä)
Osatehtävä 2 (55 pistettä)
Osatehtävä 3 (33 pistettä)