Se consideră operația : {1; 2} → {1; 2}, astfel încât 1 = 2, 2 = 1. Operația se extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu 1211212121 =2122121212.
Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere după următoarea regulă de concatenare:
s1 = 1221, s2 = 1221211221121221, … , sk+1 = sk sk sk sk, …, pentru orice număr natural nenul k.

Cerința

Să se scrie un program care pentru un n număr natural nenul cunoscut determină și afișează a n-a cifră a șirului s, astfel încât numărul de pași ai programului să fie proporțional cu log2(n) (complexitate timp logaritmică în funcție de n).

Date de intrare

Fișierul de intrare extindere.in conține pe prima linie numărul natural nenul n.

Date de ieșire

Fișierul de ieșire extindere.out va conține pe prima linie numărul c care reprezintă a n-a cifră a șirului format după regula precizată mai sus.

Restricții și precizări

1 ≤ n ≤ 1.000.000

Exemplu

extindere.in

extindere.out

Explicație

Pentru a afla cifra aflată pe poziția n=18 trebuie efectuate 3 pași de extindere.
Șirul generat este 1221211221121221 2112122112212112 2112122112212112 1221211221121221.
Cifra aflată pe poziția 18 este 1.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema extindere:

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

ifstream f("extindere.in");
ofstream g("extindere.out");

int n;

int main()
{
    f >> n;

    int p = 1;
    while( p * 4 < n )
        p *= 4;

    bool op = 0; /// codific, pentru usurinta cu {0,1}, nu cu {1,2}
    while( n > 4){
        if( n > p && n <= 3*p ) op ^= 1;
        n = (n-1) % p + 1;
        p /= 4;
    }


    if( op ){
        if ( n == 2 || n == 3 ) g << "1\n";
        if ( n == 1 || n == 4 ) g << "2\n";
    }
    else{
        if ( n == 2 || n == 3 ) g << "2\n";
        if ( n == 1 || n == 4 ) g << "1\n";
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2202 extindere

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2202 extindere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2202 extindere