Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Interactivo
Estadísticas

Beskrivelse

Det finnes en rettet graf med $n$ noder nummerert fra $1$ til $n$. For hver node $1 \le i \le n$ er utgraden til node $i$ høyst én; dermed kan vi beskrive grafen ved hjelp av en tabell $p_i$, der $p_i = 0$ hvis utgraden til node $i$ er null, og ellers $1 \le p_i \le n$, $p_i \ne i$, og det går en rettet kant fra $i$ til $p_i$. Det er ingen rettede sykler i grafen, så fra enhver node $i$ vil stien som dannes ved å gjentatte ganger gå til neste node langs rettede kanter til slutt ende i en node med utgrad null.

Til å begynne med ligger det en trebrikke på en av nodene. Når du klapper i hendene, vil brikken flytte seg til node $p_i$ dersom den står på en node $i$ med $p_i$ ulik null; ellers flytter den seg ikke. Du kan imidlertid overhodet ikke se hvor brikken er — den eneste operasjonen du kan utføre er å velge en delmengde av noder, plassere brikken på en av dine valgte noder, klappe i hendene et visst antall ganger, og observere om brikken ender opp på en av dine valgte noder. Til og med brikkens startposisjon og antallet ganger du klapper i hendene velges av en interaktor: du får bare velge delmengden av noder, og observere det maksimale antallet ganger du kan klappe i hendene slik at brikken kan starte på en av dine valgte noder og ende på en av dine valgte noder.

Du ønsker å legge til én enkelt kant fra $x$ til $y$ ($1 \le x, y \le n$, $x \ne y$ og $p_x = 0$, dvs. at du kan sette $p_x = y$), slik at du kan klappe i hendene enda flere ganger på hele grafen enn før. Likevel må det å legge til kanten ikke skape noen rettede sykler i grafen.

Finn en hvilken som helst slik kant du kan legge til ved å spørre om det maksimale antallet ganger du kan klappe i hendene på høyst $n$ delmengder av noder, eller avgjør at det er umulig å legge til en slik kant.

Inndata

Den første linjen i inndata inneholder et enkelt heltall $n$ ($1 \le n \le 1000$).

Interaksjon

For å stille et spørsmål, skriv ut én enkelt linje på formen $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, der $1 \le k \le n$, og $1 \le u_i \le n$ er parvis forskjellige noder i din valgte delmengde. Les deretter én enkelt linje som inneholder et enkelt heltall: det maksimale antallet ganger du kan klappe i hendene slik at brikken kan starte på en av dine valgte noder og ende på en av dine valgte noder. Du kan stille høyst $n$ spørsmål.

Etter at du har bestemt hvilken kant du vil legge til, skriv ut én enkelt linje på formen $\texttt{! } x \text{ } y$, der $1 \le x, y \le n$ er endepunktene til den rettede kanten du vil legge til. Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.

Hvis det er umulig å legge til en slik kant, skriv ut $-1 \text{ -1}$ i stedet for endepunktene til kanten.

Løsningen din må avsluttes umiddelbart etter at svaret er skrevet ut.

Tøm utdatabufferen (flush) etter hvert spørsmål du stiller.

Interaktoren er ikke adaptiv; grafen er fastsatt på forhånd.

Eksempel

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Merk

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.