Cerința

Goe este un copil drăgălaș, dar tare leneș. Nu îi place nici să scrie, nici să numere. Cu greu a fost convins de mama sa să învețe cifrele, dar de scris tot nu poate să le scrie pe toate. Nu îi plac cifrele 2, 4, 5 și 7, iar cifra 6 o încurcă cu 9 și invers. Și asta nu este tot. Când mama sa îi dă să copieze numere, pentru a exersa scrierea cifrelor, el le scrie în oglindă, adică scrie cifrele în ordinea inversă. De exemplu, numărul 138 va fi scris de Goe 831.

Mama lui Goe scrie în fiecare zi, în ordine crescătoare, câte 9 numere naturale, sărind însă peste orice număr divizibil cu 10, ca în Figura 1. Goe copiază zilnic aceste numere. Din păcate, el nu își îndreaptă niciuna dintre greșeli: copiază numerele scriindu-le oglindite, nu scrie numerele care conţin cifrele 2, 4, 5 și 7 și înlocuieşte, în continuare cifra 6 cu 9 și invers (vezi Figura 2).

Date de intrare

Fişierul goe.in conţine o singură linie pe care sunt scrise trei numere naturale k, p și n, separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieșire goe.out va conține trei linii:

a. Pe prima linie, se va scrie numărul de numere scrise de Goe în primele k zile;
b. Al p-lea palindrom scris corect de Goe;
c. Pe a treia linie, se va scrie cel mai mare număr scris de Goe în primele n zile.

Restricții și precizări

1≤ k ≤ 100000
1≤ p ≤ 750
1≤ n ≤ 32000000
un număr este palindrom dacă este egal cu oglinditul său (ex: 22, 373 etc.)

Exemplu

goe.in

5 8 3

goe.out

15
111
91

Explicație

15 numere a scris Goe în primele 5 zile.
Primele 8 palindroame scrise corect de Goe sunt: 1, 3, 8, 11, 33, 88, 101, 111.
Cel mai mare număr scris de Goe în primele 3 zile este 91.

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 Goe:

// Solutie optimizata
// Propusa de: elev Vintila Valentin (100p)

#include <fstream>
#include <cmath>

using namespace std;

int main()
{
    long i, j, d;
    int v[11] = {};

    long k, p, n; ifstream fin("goe.in");
    fin >> k >> p >> n; fin.close();


    ofstream fout("goe.out");

    // Primele 40 de puncte (cerinta a):
    long nrn = 0;

    // Goe scrie 5 sau 0 numere intr-una din zile.
    // Este suficient sa verificam daca in componenta indicelui
    // zilei respective apare una din cifrele 2, 4, 5, 7.
    // Rezultatul final este de 5 ori mai mare.

    for(i = 1; i <= k; ++i)
    {
        for(j = i - 1; j; j /= 10)
            if(j % 10 == 2 || j % 10 == 4 || j % 10 == 5 || j % 10 == 7)
                break;
        if(j == 0) nrn += 5;
    }
    (fout << nrn).put('\n');


    // Urmatoarele 30 de puncte (cerinta b):

    nrn = 1; d = 3; // d = nr de palindroame de nrn cifre
    while(p > d) { p -= d; ++nrn;
                   if(nrn % 2) d *= 4; }

    // d este modificat o data la 2 pasi, intrucat numarul de
    // palindroame este acelasi pentru o lungime de 2*k si 2*k+1

    // p retine al catelea numar de nrn cifre trebuie determinat.
    // In c construim palindromul, dar in baza 4, pentru a face o 
    // bijectie intre baza 4 si o baza cu cifrele 0,1,3,8 (singurele
    // cifre cu care se pot construi palindroamele)

    v[1] = i = 1; v[nrn] = 1; d /= 3; --p;
    while(d)
    {
        v[i] = v[nrn - i + 1] = v[i] + p / d;
        p %= d; d /= 4; ++i;
    }

    // Trecem numarul din baza 4 in scrierea necesara, afisandu-l
    // in acelasi timp (cod optimizat)

    for(i = 1; i <= nrn; ++i)
        fout << ((v[i] == 2) ? 3 : ((v[i] == 3) ? 8 : v[i]));
    fout.put('\n');


    // Ultimele 30 de puncte (cerinta c):

    i = nrn = log10(n) + 1;
    do { v[i] = n % 10; --i; } while(n /= 10);
    i = 1;

    if(v[1] == 1)
        do ++i; while(i <= nrn && v[i] == 0);

    if(i == nrn + 1)
        for(i = 1; i <= nrn; ++i) fout.put('9');
    else
    {
        fout.put('9');

        if(v[i] > 1 && i < nrn && v[i + 1] < 6 ||
           v[i] == 1 && v[i + 1] < 6 || v[i] != 9)
        {
            --v[i];
            if(v[i] == 2 || v[i] == 4 || v[i]== 5 || v[i] == 7) --v[i];
            if(v[i] == 4) v[i]=3;
        }

        for(++i; i <= nrn; ++i) v[i] = 9;
        --i; do
        {
            if(v[i] == 6) v[i] = 9;
            fout.put(v[i] + '0');
        } while(--i);
    }

    // Final: inchidem fisierul de iesire.

    fout.close();
    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 #2518 Goe

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2518 Goe 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 #2518 Goe