- 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):
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ä)
- n = 16
- m = 1
- k = 7
Osatehtävä 2 (32 pistettä)
- n=1000
- m = 10
- k = 7
Osatehtävä 3 (49 pistettä)
- n=10^9
- m = 1000
- k = 3