% Idee: Phil Labuschagne, Ahto Truu
% Tekst: Ahto Truu

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}

\begin{document}
\begin{ol}{\eio}{\ev 4.12.2025}{\yle}{}
\begin{yl}{5}{Vale kuju 2}{kuju2}{2 sek / 3 sek}{80 punkti}

Levinud ütluste kohaselt ei sobi kandiline punn ümmargusse auku ega ümmargune punn kandilisse auku. Tegelikult muidugi saab ümmarguse punni ruudukujulisse auku panna, kui augu küljepikkus on punni läbimõõdust suurem või sellega võrdne.

Jukul on pika laua sees $N$ ruudukujulist auku. Augud on nummerdatud $1$ kuni $N$ nende suuruste \textbf{kasvavas} järjekorras.

Laua kõrval maas on $M$ ümmargust punni. Punnid on nummerdatud $1$ kuni $M$ nende läbi\-mõõtude \textbf{mittekahanevas} järjekorras.

Aita Jukul leida iga punni jaoks kõige väiksem auk, millesse see mahub, või tuvastada, et see ei mahu ühtegi auku, kasutades selleks võimalikult vähe katseid mingit punni mingisse auku panna.

\suht See on interaktiivne ülesanne, kus programm ei saa ise sisendandmeid lugeda, aga võib testimiskeskkonnale päringuid esitada.

Programmi töö alguses on sisendi esimesel real aukude arv $N$ ja punnide arv $M$ ($1 \le N, M \le 25\,000$).

Seejärel võib programm esitada punnide aukudesse proovimiseks päringuid. Päringu esitamiseks tuleb väljastada rida \\
\verb'?'~$I$~$J$ \\
kus $1 \le I \le M$ on punni ja $1 \le J \le N$ on augu number. Vastus on sisendi järgmisel real. Kui punn number $I$ mahub auku number $J$, on vastus $1$; kui ei mahu, on vastus $0$.

Lõpuks peab programm teatama vastuse. Selleks tuleb väljastada rida \\
\verb'!'~$V_1$~$V_2$~\ldots~$V_M$ \\
kus $V_i$ on vähim selline $j$, et punn number $i$ mahub auku number $j$, või $-1$, kui punn number $i$ ei mahu ühtegi auku. Vastuse teatamise järel peaks programm kohe töö lõpetama.

\nde[0]{3cm}{3cm}

Selles testis on $N = 4$ auku ja $M = 3$ punni.

Programm proovib esimesena punni $1$ auku $1$ ja saab vastuse, et punn mahub auku.

Edasi proovib programm punni $2$ auku $2$ ja saab vastuse, et punn ei mahu auku. Seejärel proovib programm punni $2$ auku $3$ ja saab vastuse, et punn mahub auku.

Lõpuks proovib programm punni $3$ auku $4$ ja saab vastuse, et punn ei mahu auku.

Eelneva põhjal saab programm teatada vastuse ja lõpetab seejärel töö.

\clearpage

\hnd \testideraldi
\begin{xenum0}
  \item (0 punkti) \naitedlyhem
  \item (18 punkti) $M, N \le 100$. Lahendus, mis teeb $Q$ päringut, teenib $\min(1, \frac{P}{Q}) \cdot 100$\;\% testi väärtusest, kus $P = M \cdot N$.
  \item (18 punkti) $M \le 1\,000$. Lahendus, mis teeb $Q$ päringut, teenib $\min(1, \frac{P}{Q}) \cdot 100$\;\% testi väärtusest, kus $P = \frac{100}{99} \cdot M \cdot \log_2(N)$.
  \item (18 punkti) $N \le 1\,000$. Lahendus, mis teeb $Q$ päringut, teenib $\min(1, \frac{P}{Q}) \cdot 100$\;\% testi väärtusest, kus $P = \frac{100}{99} \cdot \log_2(M) \cdot N$.
  \item (26 punkti) Lahendus, mis teeb $Q$ päringut, teenib $\min(1, \frac{P}{Q}) \cdot 100$\;\% testi väärtusest, kus $P = \frac{20}{99} \cdot \min(M, N) \cdot \log_2(\max(M, N))$.
\end{xenum0}

\mrk Et tagada programmi väljastatud andmete testimissüsteemi kohale jõudmine, tuleb iga rea järel väljundpuhver tühjendada:

\begin{tabular}{l|l}
  Programmikeel & Käsk \\
  \hline
  C++ & \verb'cout << ... << endl;' \\
      & või \\
      & \verb'cout << ... << "\n" << flush;' \\
  \hline
  Python & \verb'print(..., flush=True)' \\
         & või \\
         & \verb'sys.stdout.write(...)' \\
         & \verb'sys.stdout.flush()' \\
  \hline
\end{tabular}

\end{yl}
\end{ol}
\end{document}
