.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » boltz

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 Boltz
boltz


Timp maxim de execuţie/test:
1.2 secunde
Memorie totală disponibilă/stivă:
64MB/4MB

Baieţii de la 8 joacă Boltz. Acest joc are următoarele reguli:

  • se porneşte de la o mulţime P vidă
  • dacă numărul curent este divizibil cu oricare dintre numerele din P, spunem că numărul este BOLTZ
În orice moment al jocului, se poate adăuga un număr în P, cu condiţia ca acest număr să fie putere de număr prim.
Astfel, se definesc doua tipuri de operaţii:
  • 1 x se adaugă x în P
  • 2 x se întreabă dacă x este BOLTZ sau nu

Cerinţă

Se dau M operaţii. Să se raspundă la cele de tip 2.

Date de intrare

Fişierul de intrare boltz.in conţine pe prima linie numerele naturale N şi M. Pe următoarele M linii se vor afla câte două numere, separate prin spaţiu, de forma op x cu semnificaţia de mai sus (se garantează că toate numerele x sunt naturale cuprinse între 1 şi N, inclusiv).

Date de ieşire

Fişierul de ieşire boltz.out va conţine pe fiecare linie răspunsul la câte o întrebare de tip 2, în ordinea corespunzătoare fişierului de intrare. Răspunsul este BOLTZ dacă numărul din întrebare e "boltz" respectiv valoarea numărului, în caz contrar.

Restricţii

  • N, M <= 350 000
  • Pentru 30% din teste N, M <= 5000
  • La operaţiile de tip 1 se garantează că numărul x este putere de număr prim
  • Răspunsul pentru orice operaţie tip 2 va lua în calcul operaţiile de tip 1 care au apărut înaintea sa

Exemplu

boltz.in boltz.out
10 4
2 9
1 3
2 9
2 4
9
BOLTZ
4
stud Ion Petcu
Facultatea de Matematica si Informatică Bucuresti
infooltenia2013@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
Chestionare recomandate
surse trimise | ajutor