Бұл — коммуникациялық есеп.
Екі программа, Алиса мен Боб, келесі бірлескен ойынды ойнайды.
$0 \le A, B < 2^{64}$ шартын қанағаттандыратын $A$ және $B$ бүтін сандары берілген. Бастапқыда тек Алиса $A$ санын біледі, ал тек Боб $B$ санын біледі. $C := \min(A, B)$ болсын. Мақсат — Алиса да, Боб та $C$ санын шығара алатындай ету.
Ақпарат алмасу үшін Алиса мен Боб келесі функцияларды шақыра алады:
send(x): Екінші программаға 1-биттік $x$ мәнін жіберу. Бұл шақыру екінші программаreceive()функциясын шақырғанша аяқталмайды.receive(): Екінші программадан 1-биттік мәнді қабылдап, оны қайтару. Бұл шақыру екінші программаsend()функциясын шақырғанша аяқталмайды.
Алиса мен Бобтың бірге жасаған send() шақыруларының жалпы саны $76$-дан аспауы керек. Дәл сол шарт receive() үшін де орындалады.
Байланыс аяқталғаннан кейін, әр программа келесі функцияны дәл бір рет шақыруы тиіс:
answer(x): $C$ мәні $x$-ке тең екенін жариялау. Осы функцияны шақырғаннан кейін программа бірден жұмысын тоқтатуы тиіс.
Егер Алиса да, Боб та $C$ мәнін дұрыс тапса, ойын сәтті аяқталады.
Ойында әрқашан жеңіске жететін Алиса мен Боб атты екі программа жазыңыз.
Әрекеттесу протоколы
Бұл — интерактивті коммуникациялық есеп (сіздің программаларыңыз бен қазылар алқасының программасы стандартты енгізу/шығару арқылы байланысады). Алиса рөлін атқаратын программаңыз бен Боб рөлін атқаратын программаңыз ойынды қазылар программасы арқылы ойнайды.
Программаның іске қосылуы
Сіздің программаңыз алдымен келесі форматтағы кіріс деректерін алады:
Player X
Мұндағы Player — Alice немесе Bob жолы, ал $X$ — $0 \le X < 2^{64}$ шартын қанағаттандыратын бүтін сан.
- Егер
PlayerмәніAliceболса, онда $A = X$. Осы сәттен бастап программаңыз Алиса ретінде әрекет етуі керек. - Егер
PlayerмәніBobболса, онда $B = X$. Осы сәттен бастап программаңыз Боб ретінде әрекет етуі керек.
Оدان кейін төменде сипатталғандай send, receive және соңында answer функцияларын шақырыңыз.
send
send(x) шақыру үшін келесіні шығарыңыз:
send x
Мұндағы $x$ мәні $0$ немесе $1$ болуы керек.
Бұл шақыру екінші программа receive() шақырғанша аяқталмайды. Төмендегі жағдайлардың кез келгені орын алса, сізге Wrong Answer беріледі:
- сіз күтіп тұрғанда екінші программа жұмысын тоқтатса,
- сіз күтіп тұрғанда екінші программа да
send()шақырса, - Алиса мен Бобтың
send()шақыруларының жалпы саны $76$-дан асып кетсе.
receive
receive() шақыру үшін келесіні шығарыңыз:
receive
Содан кейін стандартты енгізуден қабылданған $x$ битін оқыңыз:
x
Бұл шақыру екінші программа send() шақырғанша аяқталмайды. Төмендегі жағдайлардың кез келгені орын алса, сізге Wrong Answer беріледі:
- сіз күтіп тұрғанда екінші программа жұмысын тоқтатса,
- сіз күтіп тұрғанда екінші программа да
receive()шақырса, - Алиса мен Бобтың
receive()шақыруларының жалпы саны $76$-дан асып кетсе.
Егер әрекеттесу барысында сізге Wrong Answer берілсе, кіріске $-1$ беріледі. Егер $-1$ оқысаңыз, программаңызды дереу тоқтатыңыз, әйтпесе Time Limit Exceeded алуыңыз мүмкін.
answer
answer(x) шақыру үшін келесіні шығарыңыз:
answer x
Мұндағы $x$ мәні $\min(A, B)$ мәніне тең болуы керек. Бұл функцияны шақырғаннан кейін программаңызды дереу тоқтатыңыз.
Ескертпе
- Әрбір шығарудан кейін программаңыз стандартты шығару буферін тазартуы (flush) тиіс; әйтпесе Time Limit Exceeded алуыңыз мүмкін.
- Қазылар программасы, Алиса рөліндегі программаңыз және Боб рөліндегі программаңыз бір уақытта жұмыс істейді. Уақыт пен жад шектеулері осы үшеуінің қосындысы ретінде өлшенеді, сондықтан уақыт пен жад үшін жеткілікті қор қалдырыңыз.
- Қазылар программасы шамамен $50$ мс және $5$ МиБ дейін ресурс жұмсайды.
- Сіз $0$ мен $2^{64} - 1$ аралығындағы бүтін сандармен жұмыс істейсіз. Асып кетуден (overflow) сақ болыңыз.
Мысалдар
1-мысал кіріс
Alice 31 1
1-мысал шығыс
send 0 receive send 1 answer 25
2-мысал кіріс
Bob 25 0 1
2-мысал шығыс
receive send 1 receive answer 25