DragonBallSuper

Goku este pus intr-o situatie SOC: A fost otravit de Dr. Gero si trebuie sa gaseasca un antidot care ii va salva viata. Pentru prepararea antidotului el trebuie sa gaseasca mai intai otrava. El are la dispozitie $N$ sticle, din care exact una este otravita. Pentru a-l ajuta, Krillin s-a facut util si s-a multiplicat de $M$ ori, astfel ca acum Goku poate folosi cei $M$ Krillini pe post de cobai. Goku organizeaza un numar de runde, iar in fiecare runda fiecare Krillin bea dintr-o submultime de sticle. Fiecare Krillin care a baut dintr-o submultime care contine sticla otravita moare si nu mai poate fi folosit de Goku in rundele urmatoare. Tu trebuie sa il ajuti pe Goku sa organizeze rundele, si deoarece el nu stie cate runde mai are de trait, scopul tau este sa determini sticla cu antidot in cat mai putine runde.

Interacțiune

Programul tau va interactiona cu programul comisiei. Trebuie ca la inceputul sursei sa incluzi headerul comisiei dbsuper.h si sa implementezi functia

void solve()

Poti avea si functii auxiliare, dar programul comisiei va apela functia solve pentru a testa solutia ta. Pentru a rezolva problema, comisia iti pune la dispozitie urmatoarele:

void getBottlesAndKrillins(int &nrBottles, int &nrKrillins)

• primesti prin intermediul parametrilor $nrBottles$ si $nrKrillins$ numarul de sticle si de Krillini pe care le are Goku la dispozitie. Aceasta functie se poate apela de oricate ori.

void giveBottleToKrillin(int indexBottle, int indexKrillin)

• dai sticla cu indicele $indexBottle$ acelui Krillin cu indicele $indexKrillin$. Poti apela aceasta functie la inceputul unei runde de oricate ori cu orice combinatie de parametrii care respecta conditiile: $1 \leq indexBottle \leq N$ si $1 \leq indexKrillin \leq M$ si Krillinul cu indicele $indexKrillin$ este inca in viata.

void testKrillins()

• anunti comisia ca ai terminat de stabilit cine din ce sticle bea. Acest apel se face o singura data intr-o runda, dupa ce ai terminat toate apelurile giveBottleToKrillin

void getDeadKrillins(int &P, int index[])

• primesti prin intermediul parametrilor $P$ si $index$, numarul de Krillini morti in aceasta runda, precum si indicii lor pornind de la poziția $0$ din vector. Aceasta functie se apeleaza o singura data dupa testKrillins, si semnifica finalul unei runde.

void revealBottle(int indexBottle)

• trimiti sticla cu indicele $indexBottle$ ca fiind sticla cu antidotul. Acest apel se face o singura data la final, in locul inceperii unei noi runde.

O interactiune de succes consta in: apelul getBottlesAndKrillins, apoi pentru fiecare runda se fac apeluri giveBottleToKrillin urmat de un apel testKrillins si un apel getDeadKrillins. Dupa un numar de $R$ runde se va face apelul final revealBottle.

Punctare

Pentru a primi punctajul maxim pe un test, va trebui ca numarul de runde in care ati gasit solutia sa fie mai mic sau egal cu numarul necesar de runde de care ar fi nevoie in cazul cel mai defavorabil. Adica daca $rounds[i]$ este numarul de runde pe care l-ar gasi programul tau daca sticla otravita are indicele $i$, atunci strategia ta trebuie sa minimizeze valoarea $max(round[i] \ | \ 1 \leq i \leq nrBottles)$.

Restricții si precizări

• $1 \leq \ nrBottles \ \leq 125 \ 000$;
• $1 \leq \ nrKrillins \ \leq 16$;
• Atentie! Sursa ta nu va avea o functie main
• Atentie! Nerespectarea modului de interactiune va duce la un punctaj nul
• Atentie! Pentru un test functia solve va fi apelata de mai multe ori.
• Atentie! Noul sezon Dragon Ball Super o să înceapă în Iulie $2015$

Exemplu

Grader : solve()
Concurent : getBottlesAndKrillins (N, M)
Grader : $N = 2, M = 1$
Concurent : giveBottleToKrillin(1, 1)
Concurent : testKrillins()
Concurent : getDeadKrillins(P, index)
Grader : $P = 0, index = []$
Concurent : revealBottle(2)

Explicație

Determinam $N$ si $M$ initial, apoi dam prima sticla singurului Krillin. Apoi anuntam comisia ca am terminat de stabilit cine din ce bea, si cerem sa vedem Krilinii morti. Vedem ca Krillin-ul testat nu este mort, deci a doua sticla este cea otravita.