Бұл — көп кезеңді (multi-pass) интерактивті есеп. Әрбір шығарудан кейін шығыс буферін тазартуды (flush) ұмытпаңыз. Шығысты тазарту үшін келесіні пайдалана аласыз:
- C/C++ тілдерінде
fflush(stdout)немесеcout.flush(); - Java және Kotlin тілдерінде
System.out.flush(); - Python тілінде
sys.stdout.flush().
ChatGPT салған ойын тұжырымдамасының иллюстрациясы.
Классикалық онлайн жұптастыру (online matching) ойынында графтың қырлары бірінен соң бірі ашылады. Әр жолы қыр көрсетілгенде, оны өз жұптастыруыңызға қосу не қоспау туралы шешімді бірден және қайтарымсыз қабылдауыңыз керек. Сіздің мақсатыңыз — таңдалған ешбір екі қырдың ортақ төбесі болмауын қамтамасыз ете отырып, таңдалған қырлардың жалпы санын барынша арттыру.
Сіз — атаққа құштар, өршіл информатик ғалымсыз. Өзіңіз жақсы білетіндей, онлайн режимде ең үлкен жұптастыруды табу жоғары ықтималдықпен мүмкін емес екені дәлелденген — тіпті екі үлесті графтар сияқты ең қарапайым граф кластары үшін де солай. Алайда басқалар іргелі кедергі көрген жерден сіз даңққа жетелейтін мүмкіндікті көресіз. Бүгін сіз ағаштарға арналған көптен бері шешілмей келе жатқан ашық мәселені бағындырдым деп мәлімдеп, әлемге өзіңіздің төңкерісшіл алгоритміңізді таныстыруға дайынсыз.
Тек бір ғана мәселе бар: кеше сіз өз дәлелдеуіңізден қате таптыңыз және оны қалай түзету керектігін әлі білмейсіз. Сахна төрінен кеткіңіз келмей, көрсетіліміңізді сиқырлы шоуға айналдыруды ұйғарасыз — сахна сыртында жасырынған көмекшіңіз ойын басталмас бұрын $n$ төбесі бар бүкіл ағаш туралы кішкентай кеңес жібереді.
Сіздің бастапқы жоспарыңыз қарапайым еді: көмекшіңіз әрбір қыр сұранысына тікелей жауап жіберуі керек болатын. Осы мақсатта сіз ұзындығы $(n - 1)$ болатын бір ғана екілік жолды қабылдай алатын құпия құлаққап орнаттыңыз. Бірақ көрермендер сіздің «жаңалығыңызға» күмәнмен қарайды. Алдын ала келісілген кез келген айла-шарғыға жол бермеу үшін олар қырлардың бірқалыпты кездейсоқ ретпен — сіз де, көмекшіңіз де болжай немесе бақылай алмайтын ретпен ұсынылуын талап етеді.
Сахна дайын. Жарық сізге бағытталған. Енді арнаны ауыстырмай, өз мәлімдемеңізді дәлелдеңіз.
Өзара әрекеттесу хаттамасы
Сіздің шешіміңіз әр тестте екі рет іске қосылады. prepare раундында шешіміңіз көмекші рөлін атқарады. play раундында шешіміңіз сіздің — сиқыршының рөлін атқарады. Екі раундта да шешіміңіз интерактивті процедура ретінде бағаланады.
Дайындық раунды (Prepare Round)
Кірістің бірінші жолында prepare сөзі берілген. Екінші жолда төбелер санын білдіретін бүтін $n$ ($2 \le n \le 500$) саны берілген. Келесі $(n - 1)$ жолдың әрқайсысында ағаштағы $u$ мен $v$ арасындағы бағытталмаған қырды білдіретін екі бүтін $u$ және $v$ ($1 \le u, v \le n$, $u < v$) сандары берілген.
Сіз тек 0 және 1 таңбаларынан тұратын, ұзындығы дәл $(n - 1)$ болатын $s$ екілік жолы бар бір жолды шығаруыңыз керек. Бұл — екінші play раундына жіберілетін жол. Егер шығысыңыз талап етілген форматқа сәйкес келмесе, сіз Wrong Answer вердиктін аласыз.
Ойын раунды (Play Round)
Шешіміңіз play раунды үшін қайта іске қосылады.
Бірінші жолда play сөзі берілген. Екінші жолда бүтін $n$ саны берілген. Үшінші жолда prepare раундында өзіңіз басып шығарғандай дәл сол $s$ екілік жолы берілген.
Оدان кейін $(n - 1)$ жүрістен тұратын ойын басталады. Әр жүрісте екі бүтін $u$ және $v$ ($1 \le u, v \le n$, $u < v$) сандары бар жол беріледі. Жауап ретінде сіз take немесе ignore сөзі бар бір жолды шығаруыңыз керек. Бірінші раундтағы барлық қырлар дәл бір реттен беріледі және қырлардың реті $(n - 1)!$ мүмкін орын ауыстырулардың ішінен бірқалыпты кездейсоқ түрде таңдалады.
Егер жарамсыз форматтағы шығыс берілсе, ойын интерактордан қосымша ақпаратсыз бірден аяқталады.
Дұрыстықты бағалау
$M$ — шешіміңіз алған қырлар жиыны болсын. Егер ешбір төбе алынған бір қырдан артық қырға тиісті болмаса және $|M| = |M^*|$ болса (мұндағы $M^*$ — графтың ең үлкен жұптастыруы), шешім қолайлы деп есептеледі.
Мысал тесттерді қоспағанда, дәл $50$ тест бар. Есептен өту үшін шешіміңіз барлық тесттерде, соның ішінде мысал тесттерде де дұрыс болуы керек.
Барлық араластырулар шешімнің шығысын алғанға дейін бекітілетініне кепілдік беріледі. Кездейсоқтық әр тест үшін жалған кездейсоқ сандар генераторының бастапқы мәнін (seed) бекіту арқылы тұрақтандырылған.
Шешіміңізді әзірлеуге және тексеруге көмектесу үшін тестілеу құралы ұсынылады.
Мысал
1-мысал, 1-өту
Кіріс деректер
prepare 3 1 2 1 3
Шығыс деректер
00
1-мысал, 2-өту
Кіріс деректер
play 3 00 1 3 1 2
Шығыс деректер
take ignore
1-мысалға түсініктеме
$|M^*| = 1$ болғандықтан, кез келген қырды алуға болады, ал кеңес кез келген болуы мүмкін.