Just another WordPress.com site

Solution Procedure :

         1 . A simple brute force approach is preferable for this problem .

         2 . Pre-calculation saves time .

Code :

#include<iostream>
using namespace std;

int main()
{
    int i,j,k,test,array[50000+1][3]={0},d;

    for(i=0;i*i<=50000;i++)
      for(j=i;i*i+j*j<=50000;j++)
          for(k=j;i*i+j*j+k*k<=50000;k++)
          {
             d = i*i+j*j+k*k;
             if(!array[d][0] && !array[d][1] && !array[d][2]){
                array[d][0]=i;
                array[d][1]=j;
                array[d][2]=k;
            }
         }

    cin>>test;
    for(i=1;i<=test;i++)
    {
         cin>>d;
         if( !array[d][0] && !array[d][1] && !array[d][2] )
            cout<<-1<<endl;
        else
            cout<<array[d][0]<<‘ ‘<<array[d][1]<<‘ ‘<<array[d][2]<<endl;
    }
    return 0;
}

 

Another Code:

 

#include<stdio.h>
#include<math.h>

#define MAX 50000

long A[MAX+7][3];
char Find[ MAX+7];

void Calc( void)
{
    long i,j,k,Sum =0;

    long Limit =(long)sqrt( MAX);
    for( i=0;i<=Limit;i++){
        Sum +=i*i;
        for( j=i;j<=Limit;j++){
            Sum +=j*j;
            for( k=j;k<=Limit;k++){
                Sum +=k*k;

                if( Sum>MAX){
                    Sum -=k*k;
                    break;
                }
                
                if( !Find[Sum]){
                    A[Sum][0] =i;
                    A[Sum][1] =j;
                    A[Sum][2] =k;
                    Find[Sum] =1;
                }
                Sum -=k*k;
            }
            if( Sum >MAX){
                Sum -=j*j;
                break;
            }
            else Sum -=j*j;
        }
        Sum -=i*i;
    }
}

int main( void)
{
    long N,Icase;

    scanf(“%ld”,&Icase);
    Calc();
    while( Icase–){
        scanf(“%ld”,&N);
        if( Find[N]) printf(“%ld %ld %ld\n”,A[N][0],A[N][1],A[N][2]);
        else printf(“-1\n”);
    }

    return 0;
}
        

Problem Statement :

      Go to This link http://uva.onlinejudge.org/external/101/10176.html

 

Discussion for Solution :

        1. As it is a part of Problem no 10551 you may see that post in this link: https://acmproblemsolver.wordpress.com/2012/08/07/solution-of-acm-uva-10551-basic-remains/

 

—————————————————————————————————————————————————————–

 

Code:

 #include<cmath>
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;

int main()
{
    char ch;
    int i,s,R=131071;
    while(1)
    {
        string p=””;
        for(i=0;;i++)
        {
            if(scanf(” %c”,&ch)==EOF)
                return 0;
            else if( ch ==’#’)
                break;
            else
                p+=ch;
        }
        s=0;
        for (int i=0;i<p.length(); i++)
        {
            s *= 2;
            s += p.at(i)-‘0’;
            s %= R;
        }
        if(!s)
            cout<<“YES”<<endl;
        else
            cout<<“NO”<<endl;
    }
    return 0;
}

 

Problem Statement :

Go To This statement :http://uva.onlinejudge.org/external/105/10551.html

Discussion for solution :

1. take p and m as string

2. Convert m into decimal

3. Simulate the modulo step by step using the following algorithm:

s = 0;
for (i=n; i>=0; i–) {
s *= b;
s += An;
s %= R;
}

4 .Final ans is s.

5 .Convert s into b base number

6 . critical cases :

10 1 1  ( answer 0 )
2 1 1  ( answer 0 )

——————————————————————————————————————————————————–

Code :

#include<cmath>
#include<iostream>
#include<string>
using namespace std;

long int any_base_to_decimal(int b,string  a)
{
int power=0,no;
long int gap,n=0;
for(int i=a.length()-1;i>=0;–i)
{
gap=long(pow(b,power));
no=a.at(i)-‘0′;
n+=no*gap;
++power;
}
return n;
}

void decimal_to_any_base(int b,long int n)
{
string main_string=””,another_string=””;
char ch;
ch = n%b+’0′;
main_string+=ch;
n/=b;
while( n != 0 )
{
ch = n%b+’0’;
main_string+=ch;
n/=b;
}
for(int i=main_string.length()-1;i>=0;–i)
another_string+=main_string.at(i);

cout<<another_string<<endl;
}

int main()
{
string p,m;
int b;
long int s,R;
while(1)
{
cin>>b;
if(b==0)
break;

cin>>p>>m;
R = any_base_to_decimal(b,m);
s=0;
for (int i=0;i<p.length(); i++)
{
s *= b;
s += p.at(i)-‘0’;
s %= R;
}
decimal_to_any_base(b,s);
}
return 0;
}

Let g(n) denote the number of calls for fib(n)

Then clearly
          g(n) = g(n-1) + g(n-2) + 1

Base cases:
         g(0) = 1
         g(1) = 1

formula:

      dd[m]=(dd[m-1]+dd[m-2]+1)%b;

 

Code:

    #include <cstdio>
#include<iostream>
using namespace std;

long dd[1000000];

int main()
{
    long long n;
    long b,m;
    long cases=0;

    while(1)
    {
        scanf(“%lld%ld”,&n,&b);
        if(!n && !b) break;
        cases++;

        dd[0]=1;
        dd[1]=1;
        for(m=2;m<1000000;m++)
        {
            dd[m]=(dd[m-1]+dd[m-2]+1)%b;
            if(dd[m]==1 && dd[m-1]==1)
                break;
        }
        m–;
        cout<<m<<endl;
        printf(“Case %ld: %lld %ld %ld\n”,cases,n,b,dd[n%m]);
    }
    return 0;
}

Topics: http://uva.onlinejudge.org/external/102/10299.html
Reference: http://kos74185foracm.blogspot.com/2011/07/10299-relatives.html

The solution, if one is less than the number of n and n coprime, this number can not have the same prime factor with n.
Assume that n = 90 = 2 * 32 * 5, 90 quality factor have 2, 3, 5, the number of this question can not have a quality factor of these three.

We can use the exclusion principle obtained is less than n have the same qualitative factor and n the number of number:
(Number divisible by 2 + can be divisible by the number of + can be divisible by the number)     – (Can be 2,3 divisible by the number of + both 3,5 divisible by the number of + the number to be divisible by 2, 5)  + Can be 2,3,5 divisible by the number of

N = 90, for example, have a common factor and n the number of total:
(45 + 30 + 18) – (15 + 6 + 9) + 3 = 66 and

we are looking for the number of coprime with 90, 90 – 66 = 24.

We can simplify the above equation to derive a general formula:

Therefore less than n and coprime with n the number of number as follows:

Simple Discussion on Solution :

e.g. 9, We know 1, 2, 4, 5, 7, 8, Answer is 6.

And we found just 3 then (9%3) will true.
We got 9/3 = 3.
If you see the blog I linked to, he write that Answer = 9*(1-1/3), so 9*2/3 = 6.
And My code is 9*(1-1/3) => 9*(3/3-1/3) => 9/3*(3-1) => 3*(3-2).
so got that 3*(3-1) = 2.
1000000000 is the question require for.. N <= 1000000000
And we calculate that the prime number <= sqrt(1000000000) have 3401.
So we know that if has n that (n%prime[0...3401]) always false, that n is prime number.
if n >= prime[3401] and n is prime
then n%prime[0...3401]==0 not be true
So that n is not equal 1.
e.g. 2147483647 <= Just a example, not for this question
We got that 2147483647*(1-1/2147483647), so it's 2147483646.

#include <stdio.h>

1 int prime[3401] ={2},top=1;
2 void sieve();
3
4 int main()
5 {
6         sieve();
7         int n;
8         while(scanf("%d",&n)==1 && n)
9         {
10                 int soln = n;
11                 if(n == 1)
12                 {
13                         puts("0");
14                         continue;
15                 }
16                 for(int i=0;i<top && n >=prime[i];i++)
17                 {
18                         if(n%prime[i] == 0)
19                         {
20                                 while(n%prime[i] == 0)
21                                         n /= prime[i];
22
23                                 soln /= prime[i];
24                                 soln *= prime[i]-1;
25
26                         }
27                 }
28                 if(n != 1) soln/=n, soln*=(n-1);
29                 printf("%d\n",soln);
30         }
31 }
32 void sieve()
33 {
34         for(int i=3; i*i <= 1000000000 ; i+=2)
35         {
36                 int judge =1;
37                 for(int j=2;j*j <= i ;j++)
38                 {
39                         if(i%j == 0)
40                                 judge =0;
41                 }
42                 if(judge)
43                         prime[top++] = i;
44         }
45 }

Solution Of ACM UVA 594

You need to swap bits!

The input is an integer N, convert this to 32-bit integer. You have to swap 8 bits of Least Significant Bit to Most Significant Bit. Partition them into this:

X1 X2 X3 X4

Where X1,2,3, & 4 is 8-bit from the complete 32-bit integer.
Then you need to swap it so the position is like this:

X4 X3 X2 X1

So, use bitwise manipulation

<< Shift Left
>> Shift Right
& bitwise And

Another Procedure :

       If you are familiar with union then you can solve this very easily . Take a glance at the following code .

Code :

#include<iostream>
#include<cstdio>
using namespace std;

union
{
int Num;
char ch[4];
} A,B;

int main()
{
long int N;
while( scanf(“%d”,&A.Num)==1 )
{
B.ch[0]=A.ch[3];
B.ch[1]=A.ch[2];
B.ch[2]=A.ch[1];
B.ch[3]=A.ch[0];

printf(“%d converts to %d\n”,A.Num,B.Num);
}
return 0;
}

Explanation

One solution is to extract each byte of the solution using masks, shift each byte appropriately, and finally using a bitwise OR to merge the bytes back to one. Essentially just reverse the bytes of a 32-bit signed integer.

11111111 00000000 10101010 01010101

becomes

01010101 10101010 00000000 11111111

Input

0
123456789
-123456789
1
16777216
20034556
-1
-2
-65536

 Output

0 converts to 0
123456789 converts to 365779719
-123456789 converts to -349002504
1 converts to 16777216
16777216 converts to 1
20034556 converts to -55365375
-1 converts to -1
-2 converts to -16777217
-65536 converts to 65535
 সুলতান আহমেদ সাগর এই সমাধানটি করেছেন ।
Theory Difficulty easy
Coding Difficulty: easy
Algorithms Used: math
Solution Description: Use the Sieve of Eratosthenes to generate all the primes up to 1,000,000. For each input, check whether each prime divides it.

You don’t need to do an O(sqrt(n)) check. O(n) will do fine.

#include<iostream>
#include<cmath>
using namespace std;

#define max 1000000
int a[max];

void seieve()
{
long long int i,j,imax,jmax;
for(i=0;i<=max;i++) a[i]=1;
imax=sqrt(max)+1;
for(i=2;i<=imax;i++)
{
jmax=(max/i)+1;
if(a[i]==1)
{
for(j=2;j<=jmax;j++)
{
if(i*j<=max) a[i*j]=0;
}
}
}
}

int main()
{
seieve();
long long int i,N,temp,prime=0;
while(cin>>N && N!=0)
{
temp=N;
for(i=2;i<=N;i++)
if(N%i==0 && a[i])
{
++prime;
N/=i;
}

cout<<temp<<” : “<<prime<<endl;
prime=0;
}

return 0;
}