Suntuubi-palvelussa käytetään evästeitä. Palvelua käyttämällä hyväksyt evästeiden käytön. Lue lisää. OK

#include <fstream>
using namespace std;

// Datatähti 2009 - Task 3
//
// Dynamic programming solution with O(b) = log(b)
//
// Note: low[N][0] = Number of 0-N bit solutions, which are less/equal to   x (up to N bits), last bit 0
//       low[N][1] = Number of 0-N bit solutions, which are less/equal to   x (up to N bits), last bit 1
//       hig[N][0] = Number of 0-N bit solutions, which are larger     than x (up to N bits), last bit 0
//       hig[N][1] = Number of 0-N bit solutions, which are larger     than x (up to N bits), last bit 1
//
// Source by Gorath
//
long long int algorithm(long long int x) {
    int i;
    long long int low[65][2] = {{0}}, hig[65][2] = {{0}};

    // Algoritmi
    low[0][0]=1;
    hig[0][0]=hig[0][1]=low[0][1]=0;
    for(i=1;x;i++,x=x>>1) {
        if (x&1) {
            low[i][0] = low[i-1][0] + low[i-1][1] + hig[i-1][0] + hig[i-1][1];
            low[i][1] = low[i-1][0];
            hig[i][0] = 0;
            hig[i][1] = hig[i-1][0];
        } else {
            low[i][0] = low[i-1][0] + low[i-1][1];
            low[i][1] = 0;
            hig[i][0] = hig[i-1][0] + hig[i-1][1];
            hig[i][1] = low[i-1][0] + hig[i-1][0];
        }
    }

    return low[i-1][0]+low[i-1][1];
}

int main() {
    long long int a, b;
    ifstream in("profalg.in");
    ofstream out("profalg.out");
   
    // Lue tiedot
    in >> a >> b;

    // Kirjoita vastaus ja sulje tiedostot
    out << algorithm(b) - algorithm(a-1);

    in.close();
    out.close();

    return 0;
}


©2019 layout9 - suntuubi.com