Solution UVA: 701 - The Archeologists’ Dilemma

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss701 - The Archeologists' Dilemma	Accepted	C++11	0.030	0.000	971	3 mins ago

Suggest: (from UVa Problem Solution: 701 - The Archaeologist's Dilemma - 台部落 (twblogs.net))

Let P denotes the prefix, T denotes the # of lost digits. We are searching for N, that the prefix of 2^N is P.

We have an inequlity of

    P*10^T <= 2^N < (P+1)*10^T

thus

    log2(P*10^T) <= log2(2^N) < log2((P+1)*10^T),

which is

    log2(P)+T*log2(10) <= N < log2(P+1)+T*log2(10).

Also, we know that

    P < 10^(T-1),

that is

    T > log10(P)+1.

Then, we can brute force on T and find the minmum N.

#include <bits/stdc++.h>

#define int long long

using namespace std;

int32_t main() {

        ios::sync_with_stdio(0); cin.tie(0);

        int n, p;

        while(cin >> p){

                int T = log10(p) + 2;

               

                for(int t=T; ;t++){

       

                        int l = ceil(log2(p) + t*log2(10));

                        int r = floor(log2(p+1) + t*log2(10));

                        if (l<=r){

                                cout<<l<<"\n";

                                break;

                        }

                }

               

        }

}

Solution UVA: 10176 - Ocean Deep! Make it shallow!!

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10176 - Ocean Deep! - Make it shallow!!	Accepted	Python	0.150	0.000	2677	7 mins ago

Suggest:

Method 1:

- Easy if you know to use python, because python can calc big number

Method 2:
- Else if you want to use C++ to solve, you can use this method:

Input: 1010101#

Explanation:

Read ch = '1', ans = 1.

Read ch = '0', ans = 1 * 2 + 0 = 2.

Read ch = '1', ans = 2 * 2 + 1 = 5.

Read ch = '0', ans = 5 * 2 + 0 = 10.

Read ch = '1', ans = 10 * 2 + 1 = 21.

Read ch = '0', ans = 21 * 2 + 0 = 42.

Read ch = '1', ans = 42 * 2 + 1 = 85.

Read ch = '#', end of the loop.

Note % after reads to avoid big number

Output: NO

Code python use method 1

s=""

while True:

    try:

        s+= input()

    except:

        break

    binary= s.split('#')[0]

    if (len(binary) != len(s)):

        s=""

        print("NO") if int(binary,2)%131071 else print("YES")

Solution UVA: 350 - Pseudo-Random Numbers

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss350 - Pseudo-Random Numbers	Accepted	C++11	0.000	0.000	886	1 mins ago

Suggest: 

-Note a[0] should is (z*l+i)%m not l beacause:

"But be careful: the cycle might not begin with the seed!"

#include<bits/stdc++.h>

using namespace std;

int z, i, m, l, test;

int main(){

        ios::sync_with_stdio(0); cin.tie(0);

        while(cin >> z >> i >> m >> l && z && i && m && l){

                vector<int> a(1,(z*l+i)%m);

                do{

                        a.push_back((z*a.back()+i)%m);

                }while(a[0] != a.back());

                cout<<"Case "<<++test<<": "<<a.size()-1<<"\n";

        }

}

Solution UVA: 10229 - Modular Fibonacci

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10229 - Modular Fibonacci	Accepted	C++11	0.000	0.000	1342	3 mins ago

Suggest:

- Use template An amazing way to calculate 10^18-th fibonacci number using 25 lines of code. - Codeforces

#include<bits/stdc++.h>

using namespace std;

#define long long long

map<long, long> F;

long M;

long f(long n) {

        if (F.count(n)) return F[n];

        long k=n/2;

        if (n%2==0) { // n=2*k

                return F[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % M;

        } else { // n=2*k+1

                return F[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % M;

        }

}

void reset(){

        F.clear();

        F[0]= F[1]= 1%M;

}

main(){

        ios::sync_with_stdio(false); cin.tie(nullptr);

        long n, m;

        while (cin >> n >> m){

                M = pow(2, m);

                reset();

                cout << (n==0 ? 0 : f(n-1)) << "\n";

        }      

}

Solution UVA: 11475 - Extend to Palindrome

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11475 - Extend to Palindrome	Accepted	C++11	0.020	0.000	1559	4 mins ago

Suggest:

-Use the forward hash and reverse hash

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int base= 31, mod= 1000111000;

int f(char x){

    return x-'a'+1;

}

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    string s;

    while(cin >> s){

       

        int l, hash_x= 0, hash_y= 0, base_y= 1;

        for(int i=s.size()-1; i>=0; i--){

           

            hash_x = (hash_x * base + f(s[i]))%mod;

            hash_y = (f(s[i])*base_y + hash_y)%mod;

            base_y= (base*base_y)%mod;

           

            if (hash_x == hash_y) l= i-1;

        }

       

        cout<<s;

        if (l>=0) for(int i=l; i>=0; i--) cout<<s[i];

        cout<<"\n";

    }

}

Solution UVA: 834 - Continued Fractions

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss834 - Continued Fractions	Accepted	C++11	0.000	0.000	2946	1 mins ago

Suggest:

Example 43 19:

- Rule 

43 div 19 = [2;

43 mod 19 = 5

19 div 5 = 3,

19 mod 5 = 4

5 div 4 = 1,

5 mod 4 = 1

4 div 1 = 4]

4 mod 1 = 0 (r < 1 break)

 

- First i code from this rule, then fix WA in uDebug => Accepted

#include<bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int x, y;

    while(cin >> x >> y){

        cout<<"["<<x/y;

        if (x%y) cout<<";";

        do{

            int r= x%y;

            x= y;

            y= r;

           

            if (y) cout<<x/y;

           

            if (r>1 && x%y) cout<<",";

            else{

                cout<<"]\n";

                break;  

            }

        }while(1);

    }

}

Solution UVA: 11526 - H(n)

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11526 - H(n)	Accepted	C++11	0.270	0.020	1461	1 mins ago

Source solution: http://using-c.blogspot.com/

「for n = 10; go along the similar way:

lets say n = 10;
k = 1; sum = 0;
so, 10/1 = 10

k = 2
and 10/2 = 5
so, for all the integer divisions, all i = 6 to 10
will produce n/i = 1; (last denominator)
so, you don't need to calculate for 6 to 10, you have
5x1 + 10/1 = 15; (for k = 1) sum = 15;

k = 3
again 10/3 = 3
so, for all the integer divisions, all i = 4 to 5
will produce n/i = 2; (last denominator)
so, you don't need to calculate for 4 to 5, you have
2x2 + 10/2 = 9; (for k = 2) sum = sum + 9 = 24;

as k is the largest within sqrt(10);
so last we count for k = 3; for 3, one thing here to
note that, 10/3 is also 3,
so, in such cases, we have to consider once, cause
otherwise it will be counted twice.
so, sum = sum + 3 = 27(ans)

for 10, we have the values (imagine RED is not yet
counted, and GREEN is already counted, and BLUE is
the current term)
k = 1; (10) + 5 + 3 + 2 + 2 + (1 + 1 + 1 + 1 + 1)
k = 2; 10 + (5) + 3 + (2 + 2) + 1 + 1 + 1 + 1 + 1
k = 3; 10 + 5 + (3) + 2 + 2 + 1 + 1 + 1 + 1 + 1;
so you see, 3 is to be counted once as it
has no separate counterpart.
if k==n/k then you need to count once;」

#include<bits/stdc++.h>

#define int long long

using namespace std;

int H(int n){

    int res = 0;

    for(int i = 1; i*i <= n; i++){

        int cnt= (n/i) - (n/(i+1));

        if (n/i==i) res += n/i;

            else res += i*cnt+n/i;

    }

    return res;

}

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t; cin >> t;

    while(t--){

        int n;  cin >> n;

        cout<<H(n)<<"\n";      

    }

}

 

Solution UVA: 496 - Simply Subsets

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss496 - Simply Subsets	Accepted	C++11	0.000	0.000	1444	47 secs ago

Suggest: O(nlogn)

- Not need math just only SET data struct

- Compare length of vector (a, b) and set (ab) to get result 

#include<bits/stdc++.h>

#define int long long

using namespace std;

string s;

vector<int> f(){

    s+=" ";

    string x="";    

    vector<int> a;

    for(int i=0; s[i]; i++){

        if (s[i]==' '){

            a.push_back(stoll(x));

            x="";

        }

        else x+=s[i];

    }

    return a;

}

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    while(getline(cin, s)){

        vector<int> a, b;

        a= f();

        getline(cin, s);

        b= f();

       

        set<int> ab;

        for(auto x:a) ab.insert(x);

        for(auto x:b) ab.insert(x);

       

        int la=a.size(), lb= b.size(), lab= ab.size();

        if (la == lab && lb == lab) cout<<"A equals B";

        else

        if (la == lab && lb < lab) cout<<"B is a proper subset of A";

        else

        if (lb == lab && la < lab) cout<<"A is a proper subset of B";

        else

        if (lb + la == lab) cout<<"A and B are disjoint";

        else

        if (lb + la > lab) cout<<"I'm confused!";

        cout<<"\n";        

    }  

}

Solution UVA: 443 - Humble Numbers

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss443 - Humble Numbers	Accepted	C++11	0.000	0.000	945	1 mins ago

Suggest:

- Use set data struct to create humble numbers 

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n;

string s;  

set<int> humble;

vector<int> a(1,0);

int last = 2000000000;

void f(int x, int n){

    if (x*n <= last) humble.insert(x*n);    

}

void f1(){

    humble.insert(1);  

    for(auto x:humble) f(x,2), f(x,3), f(x,5), f(x,7);

    for(auto x:humble) a.push_back(x);

}

void f2(){

    while(cin >> n && n){

       

        s="th";

        if(n%100>10 && n%100<20) s="th";

        else if (n%10==1) s="st";

        else if (n%10==2) s="nd";

        else if (n%10==3) s="rd";

       

        cout<<"The "<<n<<s<<" humble number is "<<a[n]<<".\n";

    }

}

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    f1();

    f2();

}