Code Submission Evaluation System Login

Datatähti 2017 loppu

Start:2017-01-19 12:15:00
End:2017-01-19 17:15:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2017 loppu - SukujuhlaCSES - Sukujuhla

Sukujuhla

Time limit:10.00 s
Memory limit:512 MB

Uolevin suvun sukujuhlassa on paikalla $n$ henkilöä. Pian on aika siirtyä ruokasaliin, jossa sukulaiset istuvat $m$ pyöreän pöydän ääressä. Jokaisessa pöydässä istuu $n/m$ henkilöä, ja tarjolla on kolme vaihtoehtoa menuksi (A, B ja C).

Jokaisella henkilöllä on yksilöllinen tunnusnumero väliltä $1 \ldots n$, ja jokainen pystyy näkemään pöydässä oman tunnusnumeronsa lisäksi $k$ lähimmän vasemmalla ja oikealla istuvan tunnusnumeron.

On kiusallista, jos kaksi vierekkäin istuvaa henkilöä valitsee saman menun. Tehtäväsi onkin keksiä strategia, jota noudattamalla näin ei tapahdu. Uolevi kertoo strategian kaikille etukäteen, ja kaikki noudattavat samaa strategiaa.

Syöte

Syötteen ensimmäisellä on kolme lukua $n$, $m$ ja $k$: sukulaisten määrä, pöytien määrä ja näköetäisyys.

Sitten syötteessä on $m$ riviä, yksi rivi kullekin pöydälle. Jokaisella rivillä on $2k+1$ lukua, jotka kuvaavat pöydässä vierekkäin istuvat henkilöt.

Tuloste

Tulosta jokaisen pöydän kohdalla omalle rivilleen kirjain A, B tai C sen mukaan, minkä menun keskimmäisenä istuva henkilö valitsee.

Arvostelu

Toisin kuin yleensä, tässä tehtävässä yhdessä testitapauksessa ohjelmaasi suoritetaan useita kertoja (enintään 50 kertaa). Jokainen suorituskerta koskee samaa istumajärjestystä, ja pöydät ovat samassa järjestyksessä syötteessä.

Ohjelmasi hyväksytään, jos sen valitsemat menut eivät aiheuta sitä, että kahdella vierekkäin istuvalla henkilöllä olisi sama menu.

Esimerkki

Tarkastellaan esimerkkinä seuraavaa tilannetta ($n=16,m=1,k=7$):

Oletetaan, että ohjelma suoritetaan kaksi kertaa, ensin henkilölle 14 ja sitten henkilölle 4. Henkilöt istuvat vierekkäin, joten ohjelman tulee valita eri menut heille. Esimerkiksi ohjelma voi toimia seuraavasti:

Syöte:
16 1 7
2 7 16 15 12 3 9 14 4 1 8 5 11 6 10


Tuloste:
B

Syöte:
16 1 7
7 16 15 12 3 9 14 4 1 8 5 11 6 10 13


Tuloste:
A

Siis henkilö 14 valitsee menun B ja henkilö 4 valitsee menun A.

Osatehtävä 1 (19 pistettä)
Osatehtävä 2 (32 pistettä)
Osatehtävä 3 (49 pistettä)