Universal Cup Judging System

Universal Cup

実行時間制限: 0.5 s メモリ制限: 1024 MB 満点: 100 コミュニケーション
統計

Tämä on viestintätehtävä (communication problem).

Kaksi ohjelmaa, Alice ja Bob, pelaavat seuraavaa yhteistyöpeliä.

Annettuna ovat kokonaisluvut $A$ ja $B$, joille $0 \le A, B < 2^{64}$. Aluksi vain Alice tietää luvun $A$ ja vain Bob tietää luvun $B$. Olkoon $C := \min(A, B)$. Tavoitteena on, että sekä Alice että Bob pystyvät tulostamaan luvun $C$.

Vaihtaakseen tietoja Alice ja Bob voivat kutsua seuraavia funktioita:

  • send(x): Lähetä 1-bittinen arvo $x$ toiselle ohjelmalle. Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiota receive().
  • receive(): Vastaanota 1-bittinen arvo toiselta ohjelmalta ja palauta se. Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiota send().

Alicen ja Bobin tekemien send()-kutsujen yhteismäärä saa olla enintään $76$. Sama pätee funktioon receive().

Kun viestintä on päättynyt, kummankin ohjelman on kutsuttava seuraavaa funktiota täsmälleen kerran:

  • answer(x): Ilmoita, että luvun $C$ arvo on $x$. Välittömästi tämän funktion kutsumisen jälkeen ohjelman on päätyttävä.

Peli onnistuu, jos sekä Alice että Bob vastaavat $C$ oikein.

Kirjoita kaksi ohjelmaa, Alice ja Bob, jotka onnistuvat pelissä aina.

Vuorovaikutusprotokolla

Tämä on vuorovaikutteinen viestintätehtävä (ohjelmasi ja tuomariohjelma kommunikoivat standardisyötteen ja -tulosteen kautta). Alicena toimiva ohjelmasi ja Bobina toimiva ohjelmasi pelaavat peliä tuomariohjelman välityksellä.

Ohjelman käynnistys

Ohjelmasi saa ensin syötteen seuraavassa muodossa:

Player
X

Tässä Player on merkkijono Alice tai Bob, ja $X$ on kokonaisluku, jolle $0 \le X < 2^{64}$.

  • Jos Player on Alice, niin $A = X$. Tästä eteenpäin ohjelmasi on toimittava Alicena.
  • Jos Player on Bob, niin $B = X$. Tästä eteenpäin ohjelmasi on toimittava Bobina.

Kutsu sen jälkeen funktioita send, receive ja lopuksi answer alla kuvatulla tavalla.

send

Kutsuaksesi send(x), tulosta:

send x

Tässä $x$:n on oltava $0$ tai $1$.

Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiota receive(). Saat tuloksen Wrong Answer, jos jokin seuraavista tapahtuu:

  • toinen ohjelma päättyy odottaessasi,
  • toinen ohjelma kutsuu myös funktiota send() odottaessasi,
  • Alicen ja Bobin tekemien send()-kutsujen yhteismäärä ylittää $76$.

receive

Kutsuaksesi receive(), tulosta:

receive

Lue sitten vastaanotettu bitti $x$ standardisyötteestä:

x

Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiota send(). Saat tuloksen Wrong Answer, jos jokin seuraavista tapahtuu:

  • toinen ohjelma päättyy odottaessasi,
  • toinen ohjelma kutsuu myös funktiota receive() odottaessasi,
  • Alicen ja Bobin tekemien receive()-kutsujen yhteismäärä ylittää $76$.

Jos saat vuorovaikutuksen aikana tuloksen Wrong Answer, syötteenä annetaan $-1$. Jos luet arvon $-1$, lopeta ohjelmasi välittömästi, tai muuten saatat saada tuloksen Time Limit Exceeded.

answer

Kutsuaksesi answer(x), tulosta:

answer x

Tässä $x$:n on oltava yhtä suuri kuin $\min(A, B)$. Lopeta ohjelmasi välittömästi tämän funktion kutsumisen jälkeen.

Huomautus

  • Jokaisen tulostuksen jälkeen ohjelmasi on tyhjennettävä standarditulosteen puskuri (flush); muuten saatat saada tuloksen Time Limit Exceeded.
  • Tuomariohjelma, Alicena toimiva ohjelmasi ja Bobina toimiva ohjelmasi suoritetaan samanaikaisesti. Aika- ja muistirajat mitataan näiden kaikkien kolmen summana, joten jätä riittävästi marginaalia sekä ajalle että muistinkäytölle.
    • Tuomariohjelma kuluttaa enintään noin $50$ ms ja $5$ MiB.
  • Käsittelet kokonaislukuja välillä $0$ – $2^{64} - 1$. Varo ylivuotoa (overflow).

Esimerkit

Esimerkkisyöte 1

Alice
31
1

Esimerkkituloste 1

send 0
receive
send 1
answer 25

Esimerkkisyöte 2

Bob
25
0
1

Esimerkkituloste 2

receive
send 1
receive
answer 25

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.