Dato je kompletno binarno stablo dubine H. U listove se mogu upisivati vrednosti 0 ili 1. Ostali čvorovi izračunavaju svoju vrednost na osnovu vrednosti njihove dece. Čvor uzima vrednost 0 ako oba njegova deteta imaju vrednost 1. U suprotnom, čvor uzima vrednost 1. Profesor Đurić i Veliki štrumf igraju sledeću igru. Na početku igre, vrednosti čvorova nisu poznate. U svakom potezu, Veliki štrumf pita za vrednost nekog lista, a profesor Đurić određuje proizvoljnu vrednost (0 ili 1). Cilj Velikog štrumfa je da što pre utvrdi vrednost u korenu stabla, a cilj profesora Đurića je da se odigra što više poteza.

Profesor Đurić je dobio informaciju da postoji strategija njegove igre koja će naterati Velikog štrumfa da pita za vrednosti svih listova pre nego što sa sigurnošću može utvrditi vrednost korena. Međutim, on nije saznao i samu strategiju. Pomozite profesoru Đuriću i napravite program koji će igrati umesto njega i omogućiti mu da štrumfuje u letnjem hladu smejući se Velikom štrumfu.

Vaš program mora uključiti biblioteku vstrumf.h u slučaju C/C++ programa, odnosno vstrumf.tpu u slučaju Pascal programa, u kojima je Veliki štrumf implementirao svoju strategiju. Ove biblioteke sadrže sledeće funkcije:

vstrumf.h
int pocniIgru();
int pitajVelikogStrumfa(int vrednost);

vstrumf.tpu
function pocniIgru: integer;
function pitajVelikogStrumfa(vrednost: integer): integer;

Funkcija pocniIgru() vraća vrednost H, koja predstavlja dubinu stabla (dužina puta od korena do lista). Vaš program mora prvo pozvati ovu funkciju. Funkcija pitajVelikogStrumfa() služi za odigravanje jednog poteza. Ona vraća pitanje Velikog štrumfa, i to je redni broj lista za čiju vrednost je on zainteresovan. Listovi su numerisani brojevima od 1 do 2^H sleva nadesno. Funkicija vraća vrednost -1 ako je Veliki štrumf odredio vrednost u korenu, i tada se igra završava (svi naknadni pozivi su irelevantni). Vi prosleđujete funkciji odgovor profesora Đurića, i to je vrednost koju ste odredili za list za koji je Veliki štrumf prethodno pitao (u prethodnom pozivu). Ta vrednost je nebitna pri prvom pozivu funkcije, s obzirom da Veliki štrumf još nije postavio nijedno pitanje. Tipičan scenario igre je sledeći. Vaš program poziva funkciju pocniIgru() i saznaje dubinu stabla H. Zatim, vaš program poziva funkciju pitajVelikogStrumfa(), pri čemu prosleđuje vrednost 0 ili 1 proizvoljno (pri prvom pozivu ova vrednost se ignoriše), a kao povratnu informaciju dobija redni broj lista za čiju vrednost je zainteresovan Veliki štrumf. Vaš program nadalje poziva funkciju pitajVelikogStrumfa() sve dok se kao povratna vrednost ne pojavi -1. Pri svakom pozivu, prosleđujete odogovor na prethodno pitanje Velikog štrumfa, a dobijate njegovo naredno pitanje. Veliki štrumf nikada ne vara, tj. ne završava igru pre nego što je apsolutno siguran da zna vrednost u korenu stabla. Takođe, on nikada neće dvaput pitati za vrednost istog lista. Veliki šrumf će vam, poznat po svojoj pravednosti, dodeliti tačan broj poena koji ste osvojili. Očigledno, broj odigranih poteza jednak je broju poziva funkcije pitajVelikogStrumfa() do onog poziva koji vraća vrednost -1.

Način bodovanja:

Ukoliko vaš program natera Velikog štrumfa da pita za vrednosti svih listova, osvajate maksimum poena na tom test primeru. U suprotnom, možete osvojiti maksimalno 60% poena na tom primeru, srazmerno broju poteza koji je odigran. Dakle, ako je N broj svih listova, a igra se završi posle N-1 otkrivenih vrednosti, osvajate 60% poena na tom test primeru. Ukoliko se igra završi posle X otkrivenih vrednosti, osvajate (X/(N-1))*60% poena na test primeru, pri čemu se zaokruživanje vrši na prvi ceo broj ne manji od izračunate vrednosti.

Ograničenja:

• 1 ≤ H ≤ 15
• Vremensko ograničenje za izvršavanje programa je 1 s. Igra mora biti završena u ovom vremenskom periodu, uključujući i rad biblioteke.
• Memorijsko ograničenje za izvršavanje programa je 32 MB.

Napomene:

• Osim komunikacije sa bibliotekom, vaš program ne sme vršiti druge ulazno/izlazne operacije, kao što je, recimo, upisivanje ili čitanje iz datoteke. U suprotnom, Veliki štrumf vas diskvalifikuje iz igre.
• Vaš program sme proslediti funkciji pitajVelikogStrumfa() samo vrednosti 0 ili 1. U suprotnom, igra se prekida i Veliki štrumf vam ne dodeljuje poene na tom test primeru.
• Ukoliko vaš program pozove funkciju pitajVelikogStrumfa() pre poziva funkcije pocniIgru() ili nakon završetka igre (tj. nakon povratne vrednosti -1), kršite pravila igre i ne dobijate poene.
• Ako se program uspešno okonča, onda ćete u radnom folderu moći da vidite izlaznu datoteku u kojoj ćete videti koliko poena ste osvojili u tom izvršavanju programa.

Primer 1:

Objašnjenje:

U ovom primeru, Veliki štrumf ne može odrediti vrednost u korenu stabla pre nego što pita i za poslednji list. Program osvaja maksimum bodova na ovom primeru.

Primer 2:

Objašnjenje:

U ovom primeru, Veliki štrumf sa sigurnošću određuje vrednost u korenu nakon samo dve poznate vrednosti. Program osvaja (2/7)*60% = 17.14% bodova na ovom primeru.

/*
ZADATAK: igra
JEZIK: c
*/
#include <math.h>
#include "vstrumf.h"

#define kapacitet 4000000 //65537

int h, n, br_listova;
int stablo[kapacitet];  // stablo[1] je koren, deca cvora k su na lokacijama 2*k i 2*k+1, roditelj cvor k je na lokaciji k/2
                    // element je -1 ako je cvor neodredjen, 0 ili 1 ako je odredjen

int odrediVrednost(int poz)
{
    int k = poz + br_listova - 1, k1, k2;
    int v1 = 1;
    int odredjeno = 1;
    int nebitno = 0;

    while ((k > 1) && odredjeno && !nebitno)
    {
        k1 = k;
        k = k / 2;
        if (stablo[k] > -1)
            nebitno = 1;
        else
        {
            if (k1 == 2 * k)
                k2 = k1 + 1;
            else
                k2 = k1 - 1;
            if (stablo[k2] > -1)
            {
                v1 = 1 - v1;
                if (k == 1)
                    nebitno = 1;
            }
            else
                odredjeno = 0;
        }
    }
    if (!nebitno)
        if (!odredjeno)
            stablo[k1] = 1;
    return v1;
}

int main()
{
    int i, poz;

    h = pocniIgru();
    br_listova = pow(2.0, h);
    n = 2 * br_listova - 1;
    for (i = 1; i <= n; i++)
        stablo[i] = -1;

    poz = pitajVelikogStrumfa(0);
    while (poz > -1)
        poz = pitajVelikogStrumfa(odrediVrednost(poz));

    return 0;
}