Question

Numere Binare

Câte numere binare există între 1 şi N? Un număr este considerat binar dacă reprezentarea lui în baza 10 este formată doar din cifre de 1 şi / sau de 0.

Date de intrare
Fişierul de intrare nrbin.in conţine numărul natural N.

Date de ieşire
Fişierul de ieşire nrbin.out conţine un singur număr natural, reprezentând numărul de numere binare din intervalul [1, N].

Restricţii
1 ≤ N ≤ 1.000.000.000
Limita de timp e 0,1 s, iar cu solutia mea iau 55 de puncte cu time limiti excedeed!
http://varena.ro/problema/nrbin

Answer 1

Numerele care vor fi binare, sint numere naturale consecutive:
(1)2=(1)10
(10)2=(2)10
(11)2=(3)10
(100)2=(4)10
...
(1000000000)2=(512)10

Deci putem sa facem doar un for pina la 512 (Voi pune 513 ca sa nu fie nici o problema) , si sa transformam numerele din 10 in 2, astfel daca numarul transformat e mai mare decit n, atunci afisam cite numere au fost si returnam 0.


#include <bits/stdc++.h>

using namespace std;

ifstream fin("nrbin.in");
ofstream fout("nrbin.out");

int n;

int dtoz(int z);

int main()
{

    fin >> n;

    int k=0;
    for(int i=1;i<=513;i++)
    {
        if(dtoz(i)>n)
        {
            fout << k;
            return 0;
        }
        else k++;
    }

    return 0;

}

int dtoz(int z)
{
    int d=0,k=1;

    while(z!=0)
    {
        d+=(z%2)*k;
        k*=10;
        z/=2;
    }
    return d;
}