UVA 11876 – N + NOD (N)

 

Description:

For a number N, first have to calculate  N-1+divisors(N-1) & store it in array (e.g. arr[i]=arr[i-1]+divisors(arr[i-1])).
Make a sequence from 1 to until arr[i] becomes greater than 1000000.  Then you will be given two numbers A & B,  and you will have to find the number of integers from the above sequence which lies within the range [A,B].

Hints = No critical case. Easy problem.

 

Algorithm:

Step 1:
First find the prime numbers from 1 to 1000000 and store them in an array (was not sure about the range, thats why I calculated till 1000000) .
Step 2:
Calculate number of divisors for each numbers from 1 to 1000000 and store divisors in each array. (e.g. divisors of 6 are 1,2,3,6. Total 4 divisors. So divisor[6]=4. )
Step 3: To find the divisors of each number, I took help of prime numbers. There is a good tutorial in lightoj.com to find divisors using primes.  Link is give below:
http://lightoj.com/article_show.php?article=1003

To decrease time complexity,
I used here some tricks. First one is, when finding the number of divisors of a value, I checked if it is a prime or not. If the number is a prime then the divisors of that number is 2. Because prime numbers are divisible by 1 and the number it self only.
If the given number is not prime then I again checked if it is a co-prime. Because we know divisors of co-prime is 3 and they are 1, square root of that number(must be integer value, no fraction) and the number it self. So divisors of co-prime is 3.
If the number doesn’t meet the requirement of being prime, co-prime then I followed the algorithm I mentioned at the beginning of this step.
Number of divisors for 1 t0 5. divisor[1]=1, divisor[2]=2, divisor[3]=2, divisor[4]=3, divisor[5]=2, divisor[6]=4.

Step 4: So, I know the number of divisors of values from 1 to 1000000. Now I will calculate the sequence as described in problem description and will store it in a new array (e.g. num[2]=1+divisor[1], so, num[2] = 2, and num[3]=2+divisor[2], so, num[3] = 4).

Step 5: I will take the input as description. For given A & B, I will do binary search here to find lower bound of A and upper bound of B from num array. (the array which I used to store the sequence of numbers from 1 to 1000000) as problem description.
Step 6: Now I will subtract lower bound from upper bound and will save it in a new variable and again I will subtract 1 from this variable and will print this according to instruction. Why I did subtract 1? To understand this I think you need to know how lower bound and upper bound of binary search works!

I am enclosing the code here. Try not to see my code and try your own. Thanks

 

 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>

#define LL long long
#define L long

using namespace std;

L prime[1234567], mark[12345678],m;

void pr () {
    m=0;
    for (int i=4; i<12345678;i+=2)
        mark[i]=1;

    int N=sqrt(12345678)+1;

    for (int i=3;i<N;i+=2) {

        if (!mark[i]) {

            for (int j=i*i;j<12345678;j=j+i*2) {
                mark[j]=1;
            }
        }
    }

    for (int i=2;i<12345678;i++) {

        if(!mark[i])
            prime[m++]=i;
    }
}

bool checkprime( L a ) {

    L left = 0, right = m-1, mid;

    while ( left<=right ) { 

        mid = (left+right)/2; 

        if(prime[mid]==a) 
            return true; 
        else if (prime[mid]>a)
            right = mid-1;
        else
            left = mid + 1;
    }
    return false;

}

bool chcekcoprime(L a){

    L x = sqrt(a);

    if(checkprime(x) && x*x==a)
        return true;
    else 
       return false;
}

L num[1234567],di[1234567];

void divisors () {


    L c=2,d,e,f,g;
    di[1]=1;

    for (L i=2;i<1234567;i++){
        d = sqrt(i)+1;
        c=1;
        e=i;
        f=1;

        if(checkprime(i))
            c=2;
        else if (chcekcoprime(i))
            c=3;
        else{

            for (L j=0;prime[j]*prime[j]<=e;j++){ 
               f=0; 

               while(e%prime[j]==0){ 

                    f++; 
                    e=e/prime[j]; 

               } 
               c*=(f+1);

            } 

            if (e>1)
            c*=2;
        }

        di[i]=c;
    }

    return ;

}

void nu () {

    num[1]=1;

    for (m=2;m<1234567;m++) { 

            num[m]=num[m-1]+di[num[m-1]]; 

            if(num[m]>1234567)
                break;

    }

    return;


}

L lower (L a) {

    L left = 1, right = m, mid;

    while (left<=right) {

        mid = (left+right)/2;

        if(num[mid]==a){
             right=mid-1; 
             } 
        else if ( num[mid]>a)
            right = mid-1;
        else
            left = mid + 1;

    }

    return right;

}

L upper (L b) {

      L left = 1, right = m, mid;

    while (left<=right) {

        mid = (left+right)/2;

        if(num[mid]==b){ 
          left=mid+1; } 
        else if ( num[mid]>b)
            right = mid-1;
        else
            left = mid + 1;
    }

    return left;


}


int main() {
 //   freopen( "in.txt","r",stdin );

    pr ();
    divisors();
    nu();

    int n;

    L A,B;

    scanf ("%d",&n);

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

        scanf ("%ld %ld",&A,&B);

        L lo=lower(A), up = upper (B);

        printf ("Case %d: %ld\n",i,up-lo-1);

    }

    return 0;
}



Advertisements

UVA 573 The Snail

Link: https://uva.onlinejudge.org/external/5/573.pdf

Algorithm:
Simple! Just follow the instructions. Check this line carefully “If the fatigue factor drops the snail’s climbing distance below zero, the snail does not climb at all that day. ” in input section. Because of this I suffered for a while.

 

 

//https://uva.onlinejudge.org/external/5/573.pdf
//Don't copy my code. Try your own.
//Runtime: 0.000s
//Code Begins

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

#define sc scanf
#define pr printf
#define rt return
#define LL long long
#define L long

using namespace std;

int main(){
	
	//freopen("input.txt","r",stdin);
	
	double H,D,U,F,x;
	
	while(sc("%lf %lf %lf %lf",&H,&U,&D,&F)==4){
		
		if(H==0)
			break;
			
		x=(U/100)*F;

		
		double h=0;
		for(int i=1;;i++){
			

			h=h+U;

			if(h>H){
				pr("success on day %d\n",i);
				break;
			}
			else if(h<0){
				pr("failure on day %d\n",i);
				break;				
				}
			h-=D;

			if(h<0){
				pr("failure on day %d\n",i);
				break;				
			}

			U=U-x;
			if(U<0)
				U=0;
			}
			
		
		}
	
	return 0;
}
//Code Ends

UVA 11223 – O: dah dah dah!

Problem Link: https://uva.onlinejudge.org/external/112/11223.pdf

Algorithm:
Separate each word from the main line and assign them in a new string/char-array. Then compare the word with each character’s word given in the question’s description.

//Runtime 0.000s
//Code Begins



#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

#define sc scanf
#define pr printf
#define LL long long 
#define L long
#define cm strcmp

using namespace std;


void fun(char s[]){
	
	if(cm(s,".-")==0)
		pr("A");
	else if(cm(s,"-...")==0)
		pr("B");
	else if(cm(s,"-.-.")==0)
		pr("C");
	else if(cm(s,"-..")==0)
		pr("D");
	else if(cm(s,".")==0)
		pr("E");
	else if(cm(s,"..-.")==0)
		pr("F");
	else if(cm(s,"--.")==0)
		pr("G");
	else if(cm(s,"....")==0)
		pr("H");
	else if(cm(s,"..")==0)
		pr("I");
	else if(cm(s,".---")==0)
		pr("J");
	else if(cm(s,"-.-")==0)
		pr("K");
	else if(cm(s,".-..")==0)
		pr("L");
	else if(cm(s,"--")==0)
		pr("M");
	else if(cm(s,"-.")==0)
		pr("N");
	else if(cm(s,"---")==0)
		pr("O");
	else if(cm(s,".--.")==0)
		pr("P");
	else if(cm(s,"--.-")==0)
		pr("Q");
	else if(cm(s,".-.")==0)
		pr("R");
	else if(cm(s,"...")==0)
		pr("S");
	else if(cm(s,"-")==0)
		pr("T");
	else if(cm(s,"..-")==0)
		pr("U");
	else if(cm(s,"...-")==0)
		pr("V");
	else if(cm(s,".--")==0)
		pr("W");
	else if(cm(s,"-..-")==0)
		pr("X");
	else if(cm(s,"-.--")==0)
		pr("Y");
	else if(cm(s,"--..")==0)
		pr("Z");
	else if(cm(s,"-----")==0)
		pr("0");
	else if(cm(s,".----")==0)
		pr("1");
	else if(cm(s,"..---")==0)
		pr("2");
	else if(cm(s,"...--")==0)
		pr("3");
	else if(cm(s,"....-")==0)
		pr("4");
	else if(cm(s,".....")==0)
		pr("5");
	else if(cm(s,"-....")==0)
		pr("6");
	else if(cm(s,"--...")==0)
		pr("7");
	else if(cm(s,"---..")==0)
		pr("8");
	else if(cm(s,"----.")==0)
		pr("9");
	else if(cm(s,".-.-.-")==0)
		pr(".");
	else if(cm(s,"--..--")==0)
		pr(",");
	else if(cm(s,"..--..")==0)
		pr("?");
	else if(cm(s,".----.")==0)
		pr("'");
	else if(cm(s,"-.-.--")==0)
		pr("!");
	else if(cm(s,"-..-.")==0)
		pr("/");
	else if(cm(s,"-.--.")==0)
		pr("(");
	else if(cm(s,"-.--.-")==0)
		pr(")");
	else if(cm(s,".-...")==0)
		pr("&");
	else if(cm(s,"---...")==0)
		pr(":");
	else if(cm(s,"-.-.-.")==0)
		pr(";");
	else if(cm(s,"-...-")==0)
		pr("=");
	else if(cm(s,".-.-.")==0)
		pr("+");
	else if(cm(s,"-....-")==0)
		pr("-");
	else if(cm(s,"..--.-")==0)
		pr("_");
	else if(cm(s,".-..-.")==0)
		pr("\"");
	else if(cm(s,".--.-.")==0)
		pr("@");
	
	
	}


int main(){
	
	
	char s[2010];
	
	char x[2010];
	
	int n,p;
	sc("%d",&n);
	cin.ignore();
	for(int i=1;i<=n;i++){
		
		if(i>1)
			pr("\n");
		gets(s);

		pr("Message #%d\n",i);
		for(int j=0;s[j]!='\0';){
			if(s[j]!=32){
				p=0;
				for(;s[j]!='\0';j++){
					if(s[j]==32){
						j++;
						break;
					}
					else{
					x[p++]=s[j];
					}
				}
				x[p]='\0';
				fun(x);
				
				
				}
				else{
				pr("%c",s[j]);
				j++;
				}
			
			
			}
			pr("\n");
			
		
		
		
		
		}
	
	return 0;
}

//Code Ends

UVA 10107 What is the Median?

UVA 10107 What is the Median?

 

Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers. Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}. If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4 !

Input
The input file consists of series of integers X(0<=X<2^31) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces.

Output
For each input print the current value of the median.

Sample Input
1
3
4
60
70
50
2

Sample Output
1
2
3
3
4
27
4

 

//https://uva.onlinejudge.org/external/101/10107.pdf
//Runtime:  0.720s
//Code Begins
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

int main(){

    vector< int > v;


    int x,c=0;
    while(cin >> x){
        v.push_back(x);
        sort(v.begin(),v.end());
        if(c%2==0){
            int mid=(0+c)/2;
            cout << v[mid] << endl;
        }
        else{
            int mid=(0+c)/2;
            int min=mid+1;
            int val=(v[mid]+v[min])/2;
            cout << val << endl;
        }
        c++;

    }


    return 0;
}
//Code Ends


UVA 11879 – Multiple of 17

11879 – Multiple of 17

Problem Link: https://uva.onlinejudge.org/external/118/11879.pdf

Algorithm: This problem is quite easy. In this, there will be a number which is greater at most 100 digits. So, Its not possible to store it in “long long int” in c++.
We will write a program which will take input a string. If the string contains only 0 then the program will be break, otherwise it will enter in another loop. Before entering I will declare two integer variables ‘reminder’ and ‘i’. I will initialize the reminder variable to 0;

 

	char s[110];
	
	while(scanf("%s",s)){
		
		if(strcmp(s,"0")==0)
			break;
			
		int i, reminder=0;
                //code goes here
        }


Then there will be loop which will start from the beginning of string to the end. It will be look like-



for(i=0;s[i]!='\0';i++){
    //code goes here
}

Now I will multiply the reminder by 10 and sum it with the current digit of the string(due to string case you need to subtract 48 from the current character and it will be count as digit in integer). again I will find the reminder of the previous reminder diving by 17  and will store it in reminder variable. This process continues until the loop ends.

				reminder=reminder*10+(s[i]-48);
				reminder=reminder%17;

After the loop ends my program will check whether the reminder variable is zero or not. If it is zero that means the big number(string) is multiple of 17 else it not.

if it is multiple of 17 then my program will print 1 , if this is not multiple of 17 then the program will print 0.

if(reminder==0)
			printf("1\n");
		else
			printf("0\n");

Now all the steps are done. Now lets combine all the codes in one place.

//Problem Link: https://uva.onlinejudge.org/external/118/11879.pdf
//Code Begins
//RUNTIME: 0.00s

#include<cstdio>
#include<cstring>

using namespace std;

int main(){
	
	char s[110];
	
	while(scanf("%s",s)){
		
		if(strcmp(s,"0")==0)
			break;
			
		int reminder=0;
		for(int i=0;s[i]!='\0';i++){
				reminder=reminder*10+(s[i]-48);
				reminder=reminder%17;

			}
			
		if(reminder==0)
			printf("1\n");
		else
			printf("0\n");
		
		}
	
	return 0;
}
//Code Ends

414 – Machined Surfaces

Problem Link: https://uva.onlinejudge.org/external/4/414.pdf

 

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int main(){

    int t,i,j;
    while(1){
        scanf("%d%*c",&t);

        if(t==0)
            break;

        char a[t][25];
        for(i=0;i<t;i++)
            gets(a[i]);

        int b[t];
        for(i=0;i<t;i++)
            b[i]=0;

        for(i=0;i<t;i++){
            for(j=0;j<25;j++){
                if(a[i][j]!='X')
                    b[i]++;
            }
        }

        sort(b,b+t);
        int x=b[0];
        for(i=0;i<t;i++)
            b[i]=b[i]-x;

        int sum=0;
        for(i=0;i<t;i++)
            sum=sum+b[i];

        printf("%d\n",sum);


    }

    return 0;
}