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

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


Timp maxim de execuţie / test:
2.3s
Memorie totala disponibilă / stivă:
16MB / 8MB

Ionică şi Gigel joacă un joc cu N piese numerotate de la 1 la N, care se aşează într-o ordine oarecare pe o tăbliţă, sub forma unui şir. Gigel aşează piesele pe tăbliţă iar Ionică trebuie să ghicească ordinea lor din cât mai puţine întrebări. În cadrul unei întrebări Ionică precizează un număr oarecare de poziţii de pe tablă, unde vrea să cunoască ce piese se află. Ionică va răspunde specificând care este mulţimea valorilor plasate pe acele poziţii, dar nu va preciza pentru fiecare poziţie ce valoare îi corespunde. Poziţiile tablei sunt numerotate de la 1 la N.

Cerinţă

Cunoscându-se numărul N de piese, să se determine o secvenţă cu număr minim de întrebări, necesare pentru identificarea ordinii pieselor pe tablă, indiferent care ar fi aceasta.

Date de intrare

În fişierul game1.in se va găsi pe prima linie numărul natural nenul N.

Date de ieşire

În fişierul game1.out se va scrie pe prima linie un număr K reprezentând numărul minim de întrebări determinat. Următoarele K linii din fişier codifică întrebările. Fiecare întrebare conţine un şir de numere naturale distincte, reprezentând poziţiile vizate în cadrul întrebării curente. Fiecare dintre aceste K linii se termină cu valoarea 0. Numerele în cadrul unei linii sunt separate prin câte un spaţiu.
Problema admite mai multe soluţii. În fişierul de ieşire nu contează ordinea de scriere a poziţiilor în cadrul unei întrebări.

Restricţii

0 < N <= 450000

Exemple

game1.ingame1.outExplicaţii
5 3 2 3 0 4 3 0 5 0 Prima şi a doua întrebare determină sigur valoarea piesei de pe poziţia 3.
Ştiind această valoare şi răspunsul la prima întrebare se poate stabili exact care este piesa de pe poziţia 2.
Analog pe baza răspunsului la întrebarea a doua se poate determina valoarea piesei de pe poziţia 4.
După primele două întrebări rămân indecise piesele de pe prima şi ultima poziţie.
Ultima întrebare stabileşte valoarea piesei situate pe poziţia 5, deci implicit se poate determina şi valoarea piesei de pe prima poziţie.

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor