Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 인터랙티브
통계

Kuvaus

Annettuna on suunnattu verkko, jossa on $n$ solmua numeroituina $1$:stä $n$:ään. Jokaiselle solmulle $1 \le i \le n$ solmun $i$ lähtöaste on enintään yksi; niinpä voimme kuvata verkon taulukolla $p_i$, missä $p_i = 0$, jos solmun $i$ lähtöaste on nolla, ja muulloin $1 \le p_i \le n$, $p_i \ne i$ ja solmusta $i$ solmuun $p_i$ on suunnattu kaari. Verkossa ei ole suunnattuja syklejä, joten mistä tahansa solmusta $i$ polku, joka muodostuu siirtymällä toistuvasti seuraavaan solmuun suunnattuja kaaria pitkin, päättyy lopulta solmuun, jonka lähtöaste on nolla.

Aluksi yhdessä solmuista on puinen pelinappula. Kun taputat käsiäsi, jos nappula on solmussa $i$, jolle $p_i$ on nollasta poikkeava, se siirtyy solmuun $p_i$; muuten se ei liiku. Et kuitenkaan lainkaan näe, missä nappula on — ainoa toimenpide, jonka voit tehdä, on valita solmujen osajoukko, asettaa nappula johonkin valitsemistasi solmuista, taputtaa käsiäsi tietyn määrän kertoja ja havainnoida, päätyykö nappula johonkin valitsemistasi solmuista. Jopa nappulan alkusijainnin ja taputusten määrän valitsee interaktori: sinä saat vain valita solmujen osajoukon ja havainnoida suurimman mahdollisen taputusmäärän, jolla nappula voi aloittaa jostakin valitsemastasi solmusta ja päätyä johonkin valitsemaasi solmuun.

Haluaisit lisätä yhden kaaren solmusta $x$ solmuun $y$ ($1 \le x, y \le n$, $x \ne y$ ja $p_x = 0$, eli voit asettaa $p_x = y$), jotta voisit taputtaa käsiäsi koko verkossa vielä useammin kuin aiemmin. Kaaren lisääminen ei kuitenkaan saa muodostaa verkkoon yhtäkään suunnattua sykliä.

Etsi mikä tahansa tällainen lisättävä kaari kysymällä suurinta mahdollista taputusmäärää enintään $n$:lle solmujen osajoukolle, tai päätä, että tällaisen kaaren lisääminen on mahdotonta.

Syöte

Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 1000$).

Vuorovaikutus

Tehdäksesi kyselyn tulosta yksi rivi muotoa $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, missä $1 \le k \le n$ ja $1 \le u_i \le n$ ovat pareittain eri solmuja valitsemassasi osajoukossa. Lue sitten yksi rivi, joka sisältää yhden kokonaisluvun: suurimman määrän kertoja, jonka voit taputtaa käsiäsi niin, että nappula voi aloittaa jostakin valitsemastasi solmusta ja päätyä johonkin valitsemaasi solmuun. Voit tehdä enintään $n$ kyselyä.

Kun olet selvittänyt kaaren, jonka haluat lisätä, tulosta yksi rivi muotoa $\texttt{! } x \text{ } y$, missä $1 \le x, y \le n$ ovat lisättävän suunnatun kaaren päätepisteet. Jos ratkaisuja on useita, voit tulostaa niistä minkä tahansa.

Jos tällaisen kaaren lisääminen on mahdotonta, tulosta $-1 \text{ -1}$ kaaren päätepisteiden sijaan.

Ratkaisusi on lopetettava suoritus välittömästi vastauksen tulostamisen jälkeen.

Tyhjennä tulostuspuskuri (flush) jokaisen tekemäsi kyselyn jälkeen.

Interaktori ei ole mukautuva; verkko on kiinnitetty etukäteen.

Esimerkki

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Huomautus

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

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.