Rezolvare completă PbInfo #1645 Fibocel

Toată lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr fibocel (după numele lui) dacă numărul de biţi egali cu 1 din reprezentarea binară a numărului este un număr Fibonacci.

Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.

Cerința

Să se raspundă la Q întrebări de forma: Câte numere fibocel există în intervalul închis [A, B]?

Date de intrare

Fișierul de intrare fibocel.in conține pe prima linie numărul natural Q, iar pe următoarele Q linii se găsesc câte două numere naturale A şi B separate prin exact un spaţiu, reprezentând extremităţile intervalului la care se referă întrebarea.

Date de ieșire

Fișierul de ieșire fibocel.out va conține exact Q numere, câte unul pe o linie, reprezentând răspunsurile la cele Q întrebări, în ordinea în care ele apar în fişierul de intrare.

Restricții și precizări

  • 1 ≤ Q ≤ 50.000
  • 1 ≤ A ≤ B ≤ 1015
  • Şirul Fibonacci se defineşte astfel: \(F_0 =F_1 =1; F_n =F_{n-1} +F_{n-2} \), pentru \(n ≥ 2\)
  • Pentru 40% din teste B ≤ 1.000.000

Exemplul 1

fibocel.in

1
15 16

fibocel.out

1

Explicație

15(10) =1111(2) nu este fibocel (are 4 biţi de 1 iar 4 nu este număr Fibonacci)
16(10) =10000(2) este fibocel (are 1 bit de 1 iar 1 este număr Fibonacci)

Exemplul 2

fibocel.in

7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131

fibocel.out

13
14
76
63
97
421
667

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

#define TuTTy "Cosmin-Mihai Tutunaru"
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#define infile "fibocel.in"
#define outfile "fibocel.out"
#define fMax 131
#define ll long long

using namespace std;

ll pas[fMax][fMax];
vector <int> fibo;

void initiFibo() {
    fibo.push_back(1);
    fibo.push_back(2);

    for (int i = 2; fibo[i-1] + fibo[i-2] < fMax; ++i) {
        fibo.push_back(fibo[i-1] + fibo[i-2]);
    }
}

void initPascal() {
    pas[0][0] = 1;

    for (int i = 1; i < fMax; ++i) {
        for (int j = 0; j < i+1; ++j) {
            pas[i][j] = pas[i-1][j-1] + pas[i-1][j];
        }
    }
}

string binary(ll x) {
    if (!x) {
        return "0";
    }

    string ret = "";

    while (x) {
        int bit = x&1;
        x >>= 1;
        ret = char('0' + bit) + ret;
    }

    return ret;
}

ll query(ll x) {
    string bin = binary(x);
    int l = bin.length();
    ll ret = 0;

    for (size_t f = 0; f < fibo.size() && fibo[f] <= l; ++f) {
        int neededBits = fibo[f];

        for (int i = 0; i < l; ++i) {
            int remainLength = l - i - 1;

            if (bin[i] == '1') {
                if (!neededBits) {
                    ret++;
                    break;
                }

                ret += pas[remainLength][neededBits];
                neededBits--;
            }
        }
    }

    return ret;
}

int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    initiFibo();
    initPascal();

    int q;
    scanf("%d", &q);

    while (q--) {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        printf("%lld\n", query(y+1) - query(x));
    }

    fclose(stdin);
    fclose(stdout);
    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 #1645 Fibocel

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