Code Submission Evaluation System Login

Datatähti 2020 alku

Start:2019-09-30 00:00:00
End:2019-10-14 00:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2020 alku - KetjupeliCSES - Ketjupeli

Ketjupeli

Time limit:N/A
Memory limit:N/A

Tarkastellaan peliä, jonka alkutilanteessa ruudukossa on palloja seuraavassa kuviossa:

Ruudukko on äärettömän kokoinen, ja jokaisella ruudulla on koordinaatit muotoa $(x,y)$. Ruudut on numeroitu niin, että yllä olevassa kuvassa vasemman ylänurkan koordinaatit ovat $(-5,-5)$ ja oikean alanurkan koordinaatit ovat $(6,6)$.

Jokainen pelin siirto muodostuu seuraavasti: Rajoituksena on, että ketjua ei voi muodostaa, jos sen osana on kaksi vierekkäistä palloa, jotka on jo ketjutettu toisiinsa.

Tehtäväsi on etsiä mahdollisimman pitkä siirtosarja.

Esimerkki

Tässä on esimerkkinä siirtosarja, jossa on kolme siirtoa:


Palautus

Tässä tehtävässä sinun tulee palauttaa tekstitiedosto, jossa on kuvaus siirroista. Tiedoston ensimmäisellä rivillä on luku $k$: siirtojen määrä. Tämän jälkeen tiedostossa on $k$ riviä, jotka kuvaavat siirrot. Jokaisella rivillä on neljä lukua $x_1$, $y_1$, $x_2$ ja $y_2$: muodostetun ketjun päissä olevien pallojen koordinaatit.

Esimerkiksi seuraava kuvaus vastaa äskeistä esimerkkiä:
3
-4 -1 0 -1
2 1 2 5
-1 -2 3 2
Saat tehtävästä $\min(100,\lfloor k/2 \rfloor)$ pistettä, kun lähetät kelvollisen ratkaisun, jossa $k \ge 4$.