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

Lýsing

Gefinn er stefndur grafur með $n$ hnútum sem eru númeraðir frá $1$ til $n$. Fyrir hvern hnút $1 \le i \le n$ er útgráða hnúts $i$ í mesta lagi einn; því getum við lýst grafinu með fylki $p_i$, þar sem $p_i = 0$ ef útgráða hnúts $i$ er núll, en annars gildir $1 \le p_i \le n$, $p_i \ne i$, og það liggur stefndur leggur frá $i$ til $p_i$. Engar stefndar rásir eru í grafinu, svo frá sérhverjum hnúti $i$ mun vegurinn sem myndast við að færa sig endurtekið á næsta hnút eftir stefndum leggjum að lokum enda í hnúti með útgráðu núll.

Í upphafi er trépeð á einum af hnútunum. Þegar þú klappar saman lófunum færist peðið yfir á hnút $p_i$ ef það er á hnúti $i$ þar sem $p_i$ er ekki núll; annars hreyfist það ekki. Hins vegar getur þú alls ekki séð hvar peðið er — eina aðgerðin sem þú getur framkvæmt er að velja hlutmengi hnúta, setja peðið á einn af völdu hnútunum, klappa saman lófunum nokkrum sinnum og athuga hvort peðið endi á einum af völdu hnútunum þínum. Jafnvel upphafsstaða peðsins og fjöldi klappa eru valin af gagnvirkisforriti (interactor): þú færð aðeins að velja hlutmengi hnúta og sjá mesta fjölda skipta sem þú getur klappað saman lófunum þannig að peðið geti byrjað á einum af völdu hnútunum þínum og endað á einum af völdu hnútunum þínum.

Þú vilt bæta við einum leggi frá $x$ til $y$ ($1 \le x, y \le n$, $x \ne y$ og $p_x = 0$, þ.e. þú mátt setja $p_x = y$), þannig að þú getir klappað saman lófunum ennþá fleiri sinnum á öllu grafinu en áður. Samt sem áður má viðbót leggsins ekki mynda neinar stefndar rásir í grafinu.

Finndu einhvern slíkan legg sem hægt er að bæta við með því að spyrja um mesta fjölda klappa á í mesta lagi $n$ hlutmengjum hnúta, eða skerðu úr um að ómögulegt sé að bæta slíkum leggi við.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $n$ ($1 \le n \le 1000$).

Samskipti

Til að gera fyrirspurn skaltu prenta eina línu á forminu $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, þar sem $1 \le k \le n$, og $1 \le u_i \le n$ eru parvísi ólíkir hnútar í valda hlutmenginu þínu. Lestu síðan eina línu sem inniheldur eina heiltölu: mesta fjölda skipta sem þú getur klappað saman lófunum þannig að peðið geti byrjað á einum af völdu hnútunum þínum og endað á einum af völdu hnútunum þínum. Þú mátt gera í mesta lagi $n$ fyrirspurnir.

Eftir að þú hefur ákvarðað legginn sem þú vilt bæta við skaltu prenta eina línu á forminu $\texttt{! } x \text{ } y$, þar sem $1 \le x, y \le n$ eru endapunktar stefnda leggsins sem þú vilt bæta við. Ef fleiri en ein lausn er til máttu prenta hverja sem er þeirra.

Ef ómögulegt er að bæta slíkum leggi við skaltu prenta $-1 \text{ -1}$ í stað endapunkta leggsins.

Lausnin þín verður að hætta keyrslu strax eftir að svarið hefur verið prentað.

Tæmdu úttaksbiðminnið (flush) eftir hverja fyrirspurn sem þú gerir.

Gagnvirkisforritið er ekki aðlögunarhæft; grafið er ákveðið fyrirfram.

Dæmi

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Athugasemd

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.