Zadatak: Igra sa Džokerom - Rešenje i objašnjenje

U ovoj igri korisnici pokušavaju da pronađu skriveni interval [L, R] koji je Džoker odabrao. Džoker daje broj N (gde je 5 ≤ N ≤ 1000) i čuva dva broja L i R u tajnosti (0 ≤ L ≤ R ≤ N−1).

Pravila igre

• Korisnik može da postavi pitanje tako što Džokeru pošalje niz a₀, a₁, …, aₙ₋₁.
• Džoker zatim vraća nasumično ili minimum ili maksimum elemenata unutar segmenta [L, R].
• Džoker prihvata svako rešenje (L', R') koje zadovoljava: |L − L'| + |R − R'| ≤ 1.

Cilj je pronaći što preciznije (L', R') koristeći što manje pitanja (query poziva).

---

Vrati se na tekst zadatka: Joker, vrati se na stranicu sa zadatkom Joker .

Takmičarsko okruženje vs. lokalna simulacija

U takmičarskom sistemu (npr. na onlajn platformi) funkcijequery() i answer() već su definisane od strane sistema — učesnik implementira isključivo:

void solve(int N);

Sistem zatim sam poziva query(a) i proverava rezultat answer(L, R).

U lokalnom okruženju (na sopstvenom računaru) potrebno je samostalno napraviti simulaciju Džokera, odnosno implementirati i funkcije query() i answer() da bi se testiralo rešenje.

---

Ideja rešenja

Pošto Džoker nasumično vraća minimum ili maksimum, nije moguće direktno znati gde je interval [L, R]. Međutim, ponavljanjem više upita sa različitim nizovima i analizom rezultata možemo proceniti u kom delu niza se nalazi interval.

Postoji više mogućih pristupa:

• Rekurzivno sužavanje opsega (slično binarnoj pretrazi)
• Stohastičko ispitivanje – više ponavljanja radi stabilnijeg rezultata
• Iterativno sužavanje bez rekurzije (deterministički pristup)

---

Edukativno rešenje (lokalna simulacija)

Sledeći kod implementira potpunu simulaciju: uključuje generisanje tajnog intervala, funkcije query(), answer() i rekurzivnu funkciju search_interval() koja postepeno sužava opseg dok ne pronađe rešenje.

#include <bits/stdc++.h>
using namespace std;

// --- Simulacija Džokera (lokalna verzija) ---
int L_secret, R_secret;

// Funkcija query – vraća nasumično minimum ili maksimum na segmentu [L,R]
int query(vector<int> a) {
    vector<int> segment(a.begin() + L_secret, a.begin() + R_secret + 1);
    if (rand() % 2 == 0)
        return *min_element(segment.begin(), segment.end());
    else
        return *max_element(segment.begin(), segment.end());
}

// Funkcija answer – proverava tačnost rešenja
void answer(int L, int R) {
    double greska = abs(L - L_secret) + abs(R - R_secret);
    cout << "Greška: " << greska << endl;
    if (greska <= 1)
        cout << "✅ Correct!  (Tajni interval je [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << "❌ Wrong!    (Tajni interval je [" << L_secret << ", " << R_secret << "])\n";
}

// --- Rekurzivna pretraga intervala ---
pair<int, int> search_interval(int l, int r, int N) {
    if (r - l <= 1)
        return {l, r};

    int mid = (l + r) / 2;
    vector<int> a(N);
    iota(a.begin(), a.end(), 1);

    int leftScore = 0, rightScore = 0;
    for (int i = 0; i < 5; i++) {
        int res = query(a);
        if (res <= a[mid]) leftScore++;
        else rightScore++;
    }

    if (leftScore >= rightScore)
        return search_interval(l, mid, N);
    else
        return search_interval(mid, r, N);
}

// --- Glavna funkcija solve (kao u takmičarskom okruženju) ---
void solve(int N) {
    pair<int, int> result = search_interval(0, N - 1, N);
    answer(result.first, result.second);
}

// --- Lokalni main za testiranje ---
int main() {
    srand(time(0));
    int N;
    cout << "Unesi N (5 ≤ N ≤ 1000): ";
    cin >> N;

    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "□ (DEBUG) Tajni interval: [" << L_secret << ", " << R_secret << "]\n";
    solve(N);
    return 0;
}

Prednost: lako razumljiv i vizuelno edukativan kod koji pokazuje kako se „emulira“ interaktivni zadatak lokalno.
Nedostatak: algoritam nije najefikasniji, jer koristi jednostavnu binarnu pretragu i slučajne odgovore Džokera mogu uticati na tačnost.

---

Drugo rešenje — probabilistički pristup

Sledeći primer prikazuje jednostavniji okvir koji se koristi u takmičarskim rešenjima. Ideja je da se ponavljanjem više upita proveri stabilnost kandidata (da li se u proseku dobija očekivani odgovor).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Ovo je "stub" funkcija — u stvarnom sistemu bi se pozivala funkcija query(a)
int send_query(const vector<int>& a) {
    return 0; // simulacija
}

bool verify_candidate(int l, int r, int K) {
    int ok = 0;
    for (int t = 0; t < K; ++t) {
        vector<int> a;
        int res = send_query(a);
        if (false) ++ok; // placeholder
    }
    return ok * 2 > K;
}

int main() {
    vector<pair<int,int>> candidates;
    int K = 5;
    for (auto [l, r] : candidates) {
        if (verify_candidate(l, r, K)) {
            cout << "Pronađen kandidat: " << l << " " << r << "\n";
            break;
        }
    }
    return 0;
}

Ovo rešenje pokazuje osnovni okvir probabilističke pretrage: ne daje tačno rešenje, ali objašnjava kako se može implementirati logika provere više kandidata kroz ponovljene upite.

---

Zaključak

Ovaj zadatak je tipičan primer interaktivnog problema — traži kombinaciju logike, verovatnoće i pažljivog planiranja upita. U edukativne svrhe, gornja simulacija korisniku omogućava da vidi kako Džoker „razmišlja” i da nauči kako da razvije efikasniji algoritam pre nego što rešenje preda na zvaničnoj platformi.

Napredna ideja – binarna pretraga uz višestruke probe

U ovom delu objašnjavamo napredniji pristup rešavanju zadatka „Igra sa Džokerom“. Ideja je da se kombinuje binarna pretraga i ponavljanje upita kako bi se smanjio uticaj nasumičnih odgovora Džokera.

Ideja algoritma

• Džoker vraća MIN ili MAX, ali mi ne znamo koji.
• Da bismo smanjili uticaj nasumičnosti, ponavljamo isti upit više puta (M puta).
• Kroz posebno konstruisane nizove a možemo odrediti:
  • ➤ da li je ceo segment levo od određene tačke (R ≤ k),
  • ➤ desno od nje (L > k),
  • ➤ ili ga presijeca (L ≤ k < R).

Ove informacije nam omogućavaju da binarnom pretragom pronađemo L i R sa malom greškom.

---

Implementacija algoritma

#include <bits/stdc++.h>
using namespace std;

/*
   ============================================
   □ SIMULACIJA DŽOKERA (za lokalno testiranje)
   ============================================

   U stvarnom interaktivnom zadatku, funkcije `query` i `answer`
   bi bile obezbeđene od strane sistema (judge-a),
   a programer implementira samo funkciju `solve(int N)`.

   Ovde ih simuliramo da bismo testirali algoritam lokalno.
*/

// Tajni interval (nepoznat igraču)
int L_secret, R_secret;

// query(a): vraća NASUMIČNO minimum ili maksimum iz segmenta [L_secret, R_secret]
int query(vector<int> a) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = L_secret; i <= R_secret; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    // nasumično vraća ili min ili max
    return (rand() % 2 == 0) ? mn : mx;
}

// answer(L, R): proverava tačnost
void answer(int L, int R) {
    int greska = abs(L - L_secret) + abs(R - R_secret);
    cout << "\n□ Odgovor: (" << L << ", " << R << ")";
    if (greska <= 1)
        cout << " ✅ Tačno! (Pravi interval: [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << " ❌ Pogrešno! (Pravi interval: [" << L_secret << ", " << R_secret << "])\n";
}

/*
   ============================================
   □ ALGORITAM – BINARNA PRETRAGA SA PROBAMA
   ============================================

   Ideja:
   - Džoker vraća MIN ili MAX, ali mi ne znamo koji.
   - Da bismo smanjili uticaj nasumičnosti, ponavljamo isti upit M puta.
   - Kroz posebno konstruisane nizove "a" određujemo:
        ➤ da li je ceo segment levo od određene tačke (R ≤ k),
        ➤ desno od nje (L > k),
        ➤ ili ga presijeca (L ≤ k < R).

   Ove informacije nam omogućavaju da binarnom pretragom
   pronađemo L i R sa malom greškom.
*/

// Broj ponavljanja po upitu (povećava tačnost)
const int M = 25;

// Pomoćna funkcija – testira položaj R granice u odnosu na indeks k
int probe_R(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i <= k ? 0 : 1); // 0 do k, 1 nakon k

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;  // svi 0 → ceo segment je levo (R ≤ k)
    if (zeros == 0) return -1;  // svi 1 → segment je desno (L > k)
    return 0;                   // mešano → segment "seče" k
}

// Pomoćna funkcija – testira položaj L granice u odnosu na indeks k
int probe_L(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i >= k ? 0 : 1); // 0 od k naviše, 1 pre toga

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;   // svi 0 → L ≥ k
    if (zeros == 0) return -1;   // svi 1 → R < k
    return 0;                    // mešano → L < k ≤ R
}

// Pronalazi R pomoću binarne pretrage
int findR(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        int p = probe_R(N, mid);
        if (p == +1) r = mid;    // segment je levo → R ≤ mid
        else l = mid + 1;        // segment desno → R > mid
    }
    return l;
}

// Pronalazi L pomoću binarne pretrage
int findL(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        int p = probe_L(N, mid);
        if (p == +1) l = mid;    // segment je desno → L ≥ mid
        else r = mid - 1;        // segment levo → L < mid
    }
    return l;
}

/*
   ============================================
   □ FUNKCIJA KOJU TREBA IMPLEMENTIRATI (solve)
   ============================================

   - Ova funkcija bi bila jedina koju sistem (judge)
     direktno poziva u interaktivnom zadatku.
   - U ovom lokalnom testu mi simuliramo `query()` i `answer()`.
*/
void solve(int N) {
    cout << "\n□ Početak traženja intervala...\n";

    // prvo tražimo R, zatim L
    int R = findR(N);
    int L = findL(N);

    cout << "➡️  Pronađeno: L = " << L << ", R = " << R << endl;
    answer(L, R);
}

/*
   ============================================
   □ MAIN (lokalni test)
   ============================================
   Ovde inicijalizujemo nasumičan tajni interval i pozivamo solve().
*/

int main() {
    srand(time(0));
    int N;

    cout << "Unesi N (5 ≤ N ≤ 1000): ";
    cin >> N;

    // nasumično postavljamo tajni interval [L_secret, R_secret]
    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "□ (DEBUG) Tajni interval: [" << L_secret << ", " << R_secret << "]\n";

    solve(N);
    return 0;
}

---

Objašnjenje algoritma

Korak	Objašnjenje
1.	Pravimo niz a koji ima dve vrednosti (0 i 1) — to je „senzor“ za levo/desno od granice.
2.	Funkcija query(a) vraća min ili max iz segmenta [L, R], ali nasumično — zato radimo više ponavljanja (M) i posmatramo obrazac rezultata.
3.	Ako su svi rezultati 0 → ceo segment unutar nula → R ≤ k.
4.	Ako su svi rezultati 1 → ceo segment desno → L > k.
5.	Ako ima i 0 i 1 → segment se „seče“ u k → L ≤ k < R.
6.	Binarna pretraga omogućava da precizno pronađemo R (gde prestaju nule) i L (gde počinju nule).
7.	Na kraju pozivamo answer(L, R) — uspeh ako je greška ≤ 1.

Prednosti pristupa

• Robusan — ne zavisi od nasumičnosti jednog upita (ponavljanja smanjuju šum).
• Efikasan — složenost O(log N × M), što je vrlo brzo i za N ≤ 1000.
• Jasna logika — koristi čistu binarnu pretragu po indeksima.

Ideja algoritma – binarna pretraga sa ponavljanjem upita

Ovaj pristup koristi kombinaciju binarnog pretraživanja i ponovljenih upita kako bi se smanjio efekat nasumičnih odgovora Džokera (koji vraća min ili max po volji).

• Džoker vraća MIN ili MAX, ali ne znamo koji.
• Da bismo smanjili uticaj nasumičnosti, isti upit ponavljamo više puta (M).
• Posebno konstruisani nizovi a omogućavaju da odredimo:
  • da li je segment potpuno levo od tačke (R ≤ k),
  • potpuno desno od nje (L > k),
  • ili da je presijeca (L ≤ k < R).

Ove informacije koristimo u binarnoj pretrazi da postepeno suzimo opseg i pronađemo granice L i R.

#include <bits/stdc++.h>
using namespace std;

/*
   ============================================
   □ SIMULACIJA DŽOKERA (za lokalno testiranje)
   ============================================

   U stvarnom interaktivnom zadatku, funkcije `query` i `answer`
   bi bile obezbeđene od strane sistema (judge-a),
   a programer implementira samo funkciju `solve(int N)`.

   Ovde ih simuliramo da bismo testirali algoritam lokalno.
*/

// Tajni interval (nepoznat igraču)
int L_secret, R_secret;

// query(a): vraća NASUMIČNO minimum ili maksimum iz segmenta [L_secret, R_secret]
int query(vector<int> a) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = L_secret; i <= R_secret; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    // nasumično vraća ili min ili max
    return (rand() % 2 == 0) ? mn : mx;
}

// answer(L, R): proverava tačnost
void answer(int L, int R) {
    int greska = abs(L - L_secret) + abs(R - R_secret);
    cout << "\n□ Odgovor: (" << L << ", " << R << ")";
    if (greska <= 1)
        cout << " ✅ Tačno! (Pravi interval: [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << " ❌ Pogrešno! (Pravi interval: [" << L_secret << ", " << R_secret << "])\n";
}

/*
   ============================================
   □ ALGORITAM – BINARNA PRETRAGA SA PROBAMA
   ============================================

   Ideja:
   - Džoker vraća MIN ili MAX, ali mi ne znamo koji.
   - Da bismo smanjili uticaj nasumičnosti, ponavljamo isti upit M puta.
   - Kroz posebno konstruisane nizove "a" određujemo:
        ➤ da li je ceo segment levo od određene tačke (R ≤ k),
        ➤ desno od nje (L > k),
        ➤ ili ga presijeca (L ≤ k < R).

   Ove informacije nam omogućavaju da binarnom pretragom
   pronađemo L i R sa malom greškom.
*/

// Broj ponavljanja po upitu (povećava tačnost)
const int M = 25;

// Testira položaj R granice u odnosu na indeks k
int probe_R(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i <= k ? 0 : 1);

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;  // svi 0 → segment levo (R ≤ k)
    if (zeros == 0) return -1;  // svi 1 → segment desno (L > k)
    return 0;                   // mešano → seče k
}

// Testira položaj L granice u odnosu na indeks k
int probe_L(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i >= k ? 0 : 1);

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;   // svi 0 → L ≥ k
    if (zeros == 0) return -1;   // svi 1 → R < k
    return 0;                    // mešano → L < k ≤ R
}

// Pronalazi R binarnom pretragom
int findR(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        int p = probe_R(N, mid);
        if (p == +1) r = mid;
        else l = mid + 1;
    }
    return l;
}

// Pronalazi L binarnom pretragom
int findL(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        int p = probe_L(N, mid);
        if (p == +1) l = mid;
        else r = mid - 1;
    }
    return l;
}

// Funkcija koju sistem poziva u interaktivnom okruženju
void solve(int N) {
    cout << "\n□ Početak traženja intervala...\n";
    int R = findR(N);
    int L = findL(N);
    cout << "➡️  Pronađeno: L = " << L << ", R = " << R << endl;
    answer(L, R);
}

// Lokalni test
int main() {
    srand(time(0));
    int N;
    cout << "Unesi N (5 ≤ N ≤ 1000): ";
    cin >> N;

    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "□ (DEBUG) Tajni interval: [" << L_secret << ", " << R_secret << "]\n";
    solve(N);
    return 0;
}
  

□ Objašnjenje algoritma

Korak	Objašnjenje
1.	Pravimo niz a sa vrednostima 0 i 1 — služi kao „senzor“ za granice.
2.	query(a) vraća min ili max nasumično, zato ponavljamo više puta (M).
3.	Ako su svi rezultati 0 → ceo segment unutar nula → R ≤ k.
4.	Ako su svi 1 → segment desno → L > k.
5.	Ako ima i 0 i 1 → segment „seče“ k.
6.	Binarna pretraga određuje tačke gde prelaz nastaje i nalazi L i R.
7.	Na kraju se poziva answer(L, R) — tačno ako je greška ≤ 1.

Prednosti ovog pristupa

• Robustan — smanjuje uticaj slučajnosti ponavljanjem upita.
• Efikasan — složenost O(log N × M), što je vrlo brzo za N ≤ 1000.
• Didaktički jasan — lepo demonstrira princip binarne pretrage i smanjenja šuma.

Stohastički pristup rešavanju – „probabilistički detektiv“

Ovaj pristup ne koristi eksplicitnu binarnu pretragu, već se oslanja na ponovljene nasumične eksperimente da bi statistički procenio položaj tajnog intervala [L, R].

Ideja je da generišemo više slučajnih nizova a i posmatramo rezultate funkcije query(a) — koja nasumično vraća min ili max iz segmenta. Ako posmatramo dovoljan broj rezultata, možemo zaključiti gde se interval verovatno nalazi.

Ključne ideje

• Umesto sistematskog sužavanja kao kod binarne pretrage, koristimo više nasumičnih upita i analiziramo raspodelu odgovora.
• Često pojavljivanje istog minimuma ili maksimuma ukazuje na to da je segment obuhvatio tu poziciju.
• Na osnovu statistike po indeksima procenjujemo najverovatnije granice L i R.

#include <bits/stdc++.h>
using namespace std;

// ============================================
// □ SIMULACIJA DŽOKERA (kao i ranije)
// ============================================
int L_secret, R_secret;

int query(vector<int> a) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = L_secret; i <= R_secret; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    return (rand() % 2 == 0) ? mn : mx;
}

void answer(int L, int R) {
    int greska = abs(L - L_secret) + abs(R - R_secret);
    cout << "\n□ Odgovor: (" << L << ", " << R << ")";
    if (greska <= 1)
        cout << " ✅ Tačno! (Pravi interval: [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << " ❌ Pogrešno! (Pravi interval: [" << L_secret << ", " << R_secret << "])\n";
}

// ============================================
// □ STOHASTIČKI PRISTUP
// ============================================
// Ideja: posmatramo koje pozicije u nizu najčešće doprinose ekstremnim vrednostima.
// To nam daje statističku procenu gde se interval [L, R] nalazi.

void solve(int N) {
    const int T = 300; // broj eksperimenata
    vector<int> score(N, 0);

    for (int t = 0; t < T; ++t) {
        vector<int> a(N);
        for (int i = 0; i < N; ++i)
            a[i] = rand() % 1000; // nasumične vrednosti

        int res = query(a);
        // Beležimo koje pozicije imaju vrednosti bliske rezultatu
        for (int i = 0; i < N; ++i) {
            if (a[i] == res)
                score[i]++;  // povećaj „verovatnoću pripadnosti segmentu“
        }
    }

    // Pronalazimo najduži uzastopni niz pozicija sa velikim score-om
    int threshold = *max_element(score.begin(), score.end()) * 0.7;
    int bestL = 0, bestR = 0, L = -1;

    for (int i = 0; i < N; ++i) {
        if (score[i] >= threshold) {
            if (L == -1) L = i;
            bestR = i;
        } else if (L != -1) {
            if (bestR - L > bestR - bestL)
                bestL = L;
            L = -1;
        }
    }

    answer(bestL, bestR);
}

// ============================================
// □ MAIN (lokalno testiranje)
// ============================================
int main() {
    srand(time(0));
    int N;
    cout << "Unesi N (5 ≤ N ≤ 1000): ";
    cin >> N;

    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "□ (DEBUG) Tajni interval: [" << L_secret << ", " << R_secret << "]\n";
    solve(N);
    return 0;
}
  

□ Objašnjenje pristupa

Korak	Objašnjenje
1.	Generiše se više nasumičnih nizova (T eksperimenata).
2.	Za svaki niz, Džoker vraća min ili max iz segmenta [L, R].
3.	Za indekse čije su vrednosti jednake rezultatu povećava se brojač score[i].
4.	Posle mnogo ponavljanja, najveće score vrednosti se grupišu u regionu [L, R].
5.	Pronalazimo uzastopni interval gde je score iznad praga (npr. 70% maksimuma).
6.	Taj region smatramo procenom tajnog segmenta, pa ga prosleđujemo u answer().

✅ Prednosti i mane

• Prednosti: jednostavan za implementaciju, robustan na nasumičnost, intuitivan.
• Mane: zahteva mnogo upita (O(N × T)), manje efikasan za velike N.

Ovaj pristup je koristan kada ne možemo da kontrolišemo nasumičnost Džokerovih odgovora ili kada želimo da prikažemo statistički način zaključivanja — korisno za edukativne svrhe.