| Fişierul intrare/ieşire: | anagrame2.in, anagrame2.out | Sursă | Algoritmiada 2019 Runda Finala |
| Autor | Alexandru Petrescu | Adăugată de |  Iordache Ioan-Bogdan •iordache.bogdan |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Anagrame2
Nota. Aceasta problema este interactiva.
Un numar e o anagrama in baza B a altui numar atunci cand exista o reordonare a cifrelor sale in asa fel incat sa fie obtinut celalalt numar si vice-versa. De exemplu, 1230 e o anagrama a lui 1023 dar 3210 nu e o anagrama a lui 123.
Marcel si-a ales un numar preferat in baza B si acum ii plac toate anagramele sale. Vrea sa vi-l impartaseasca si voua, numai ca nu vrea sa fie prea usor, vrea sa va straduiti sa il aflati. El va va raspunde la mai multe intrebari de genul "-Marcel, este acest numar mai mic, egal, sau mai mare, decat numarul tau preferat?". Doar ca Marcel vrea ca acest numar de care intrebati trebuie sa ii placa si lui, adica sa fie o anagrama a numarului sau preferat.
Interactiune
Pentru fiecare test trebuie procesate mai multe situatii. Astfel, prima linie va contine numarul de situatii T. Pentru fiecare situatie, pe prima linie va fi un numar natural B. Pe a doua linie se vor afla B numere, reprezentand de cate ori apare fiecare cifra - incepand cu cifra 0 si terminand cu cifra B - 1 - in numarul preferat al lui Marcel.
Programul vostru are voie sa puna intrebari scriind in standard output, de forma "<anagrama>", adica un sir de caractere.
Pentru fiecare intrebare, interactorul va raspunde in standard input cu un caracter. Acesta poate fi:
- '!', in caz ca intrebarea este invalida (numarul afisat nu este o anagrama a numarului preferat al lui Marcel). Atunci programul trebuie terminat imediat pentru a primi verdictul "Wrong query format", altfel verdictul poate fi unul diferit.
- '<', in caz ca numarul afisat este mai mic decat numarul preferat al lui Marcel
- '=', in caz ca numarul afisat este egal cu numarul preferat al lui Marcel. Atunci programul trebuie sa inceapa procesarea urmatoarei situatii, sau sa se opreasca, in caz ca aceasta a fost ultima
- '>', in caz ca numarul afisat este mai mare decat numarul preferat al lui Marcel
Citirea şi afişarea se vor face cu standard input/output.
După fiecare intrebare trebuie afişat caracterul newline('\n' sau endl).
Încercarea de-a deschide vreun fişier poate duce la o eroare în executarea programului vostru.
Nu uitaţi să daţi flush la bufferul de ieşire, cu cout.flush() sau fflush(stdout). DUPA FIECARE INTREBARE!!!
Interactorul nu este adaptiv. Cu alte cuvinte, Marcel este decis de la inceput care este numarul sau preferat, iar intrebarile nu il pot influenta.
Afisarea unui numar intr-o baza B > 10
Pentru a pune intrebarile, codificarea unei cifre c > 9 se face considerand a <c - 9>-a litera a alfabetului englez. De exemplu, cifra 10 in baza 30 se noteaza cu a, 11 cu b, etc.
Restricţii
- 1 ≤ T ≤ 100
- 2 ≤ B ≤ 30
- 0 ≤ numarul preferat al lui Marcel < B30
- Desigur ca numarul preferat al lui Marcel nu incepe cu cifra 0 decat daca este nul
- Numarul total de anagrame ale numarului preferat al lui Marcel este strict mai mic decat 258.
Punctare
Programul va fi evaluat pe un singur test, cu T situatii. Programul va putea primi puncte doar daca a primit mesajul '=' pentru fiecare situatie din test. Scorul sau va fi calculat in functie de K = numarul maxim de intrebari pe care le-a afisat pentru rezolvarea unei situatii. De exemplu, sa presupunem ca T = 3, pentru prima situatie a pus 5 intrebari, pentru a doua 12, iar pentru a treia 3 intrebari. Atunci K se considera a fi 12. Scorul este:
- 100 de puncte, daca K ≤ 60
- 23 de puncte, daca 60 < K ≤ 900
- 0 puncte, daca 900 < K
Mesaje la evaluare
Interactorul va va oferi informatii legate de performanta programului. Astfel, puteti primi urmatoarele verdicte:
- Too many queries - Intr-una din situatii, ati pus 900 de intrebari si nu ati primit mesajul '='. Daca veti pune si a 901-a intrebare, veti putea primi si alte verdicte, cum ar fi Killed by signal 11, deci va recomandam sa va asigurati ca nu veti pune mai mult de 900 de intrebari indiferent daca primti sau nu raspunsul '=', pentru a primi mesajul interactorului
- Partial score for K = <numar> - Ati primit 25 de puncte, iar K este egal cu numarul precizat
- Perfect score for K = <numar> - Ati primit 100 de puncte, iar K este egal cu numarul precizat
- Wrong query format - Ati pus o intrebare gresita, numarul afisat nu este placut lui Marcel
Feedback
La aceasta problema veti avea full feedback pe unicul test.
Exemplu
| standard input | standard output |
|---|---|
| 2 3 1 1 1 < < < = 12 0 0 0 0 0 0 0 0 0 0 2 1 > < = | 102 120 201 210 baa aab aba |
Explicaţie
Testul contine 2 situatii.
In prima situatie numarul preferat al lui Marcel este 210 in baza B = 3. Fiecare cifra apare o data.
La intrebarile 102, 120 si 201, Marcel raspunde cu '<', deoarece aceste numere sunt mai mici decat 210. La intrebarea 210, Marcel raspunde cu '='.
In a doua situatie numarul preferat al lui Marcel este aba in baza B = 12. Primele 10 cifre nu apar deloc, iar cifra a apare de 2 ori, pe cand cifra b apare o data.
La intrebarea baa, Marcel raspunde cu '>', deoarece acest numar e mai mare decat aba. La intrebarea aab, Marcel raspunde cu '<', deoarece acest numar e mai mic decat aba. La intrebarea aba, Marcel raspunde cu '='.
Pentru prima situatie s-au folosit 4 queryuri. Pentru a doua s-au folosit 3. Deci K = max(4, 3) = 4.
