ACM Problem Solution

Solution technique of 10684- The jckpot

noreply@blogger.com (Shaishab Roy) — Mon, 04 Sep 2017 18:13:00 +0000

Problem Description
source: https://uva.onlinejudge.org/external/106/10684.html

Solving Technique:

This is a maximum subarray summation related problem. We have to find the maximum subarray from a one-dimensional array and sum-up all values of sub array then we will get the patterns of consecutive wins that will give maximum benefit and elaborate a win-win strategy.

Using Kadane’s algorithm we can solve in O(n) time.

Kadane’s Algorithm:

Initialize:
    sum = 0
    maxSum = 0

Loop for each element of the array
   sum += array[i]
   if(sum < 0)
     sum = 0
   if(maxSum < sum)
     maxSum = sum
return maxSum

In this algorithm, if the sum of array elements become 0 or negative then we should set the sum to zero. That means we didn’t want to take any previous elements and we will be finding the next sequence. If we keep negative sum then we will never have the correct answer.

Example:

5
12 -4 -10 4 9

In this example sum up from the first element to -10 we got -2 and then if we add 4, 9 to the current sum -2 the max value is 11. But we could get a better result by discarding all previous sums since 12, -4 and -10 produces a negative sum -2. So we discard all previous sums till -10 then adding 4, 9 and we get the max value of 13.

Solution of 10684- The jckpot

noreply@blogger.com (Shaishab Roy) — Mon, 04 Sep 2017 17:56:00 +0000

Problem description:
source: https://uva.onlinejudge.org/external/106/10684.html

As Manuel wants to get rich faster and without too much work, he decided to make a career in gambling. Initially, he plans to study the gains and losses of players, so that, he can identify patterns of consecutive wins and elaborate a win-win strategy. But Manuel, as smart as he thinks he is, does not know how to program computers. So he hired you to write programs that will assist him in elaborating his strategy.

Your first task is to write a program that identifies the maximum possible gain out of a sequence of bets. A bet is an amount of money and is either winning (and this is recorded as a positive value), or losing (and this is recorded as a negative value).

Input

The input set consists of a positive number N ≤ 10000, that gives the length of the sequence, followed by N integers. Each bet is an integer greater than 0 and less than 1000. The input is terminated with N = 0.

Output

For each given input set, the output will echo a line with the corresponding solution. If the sequence shows no possibility to win money, then the output is the message ‘Losing streak.’

Sample input

5
12 -4
-3 -4
9
0

Sample output

The maximum winning streak is 18.

Solution:

#include<stdio.h>
using namespace std;
static int inputSequence[10002];
int main() {
    static int n, i, sum, maxGain;

    while((scanf("%d", &n))== 1) {
        if(n == 0) {
            break;
        }
        sum =0;
        maxGain = 0;
        for(i=0; i < n; i++) {
            scanf("%d", &inputSequence[i]);
            sum += inputSequence[i];
            if(sum < 0) {
                sum = 0;
            }
            if(sum > maxGain) {
                maxGain = sum;
            }
        }
        if(maxGain > 0) {
            printf("The maximum winning streak is %d.\n", maxGain);
        } else {
            printf("Losing streak.\n");
        }
    }
    return 0;
}

Solution technique of UVA problem 727 Equqtion

noreply@blogger.com (Shaishab Roy) — Thu, 24 Aug 2017 11:04:00 +0000

Problem description:

Write a program that changes an infix expression to a postfix expression according to the following specifications.

Input condition:

The infix expression to be converted is in the input file in the format of one character per line, with a maximum of 50 lines in the file. For example, (3+2)*5 would be in the form: ( 3 + 2 ) * 5
The input starts with an integer on a line by itself indicating the number of test cases. Several infix expressions follows, preceded by a blank line.
The program will only be designed to handle the binary operators +, -, *, /.
The operands will be one digit numerals.
The operators * and / have the highest priority. The operators + and - have the lowest priority. Operators at the same precedence level associate from left to right. Parentheses act as grouping symbols that over-ride the operator priorities.
Each testcase will be an expression with valid syntax

Expected uotput:

The output file will have each postfix expression all on one line. Print a blank line between different expressions.

Sample Input

(

)

Sample Output

32+5*

Solution Technique

This is a simple problem. You can solve this problem by using stack. Just follow this stapes.

Get input for test case.
Get input expression that need to change infix to postfix N.B: When you will give input expression follow that one character per line or more. When get empty line then input is complete
Read the expression from left to right or top to bottom
if input character is opening bracket or operator then push into stack.
if input character is digit then print this character.
if input character is closing bracket then print operator from stack and pop this operator until get opening bracket.
pop this opening bracket from stack. N.B: Do not need to insert closing bracket into stack and check next character.
. This process running until all input are checked.

UVA solution 727 Equation

noreply@blogger.com (Shaishab Roy) — Wed, 23 Aug 2017 17:47:00 +0000

Problem description:
source: https://uva.onlinejudge.org/external/7/727.html

Write a program that changes an infix expression to a postfix expression according to the following specifications.

Input condition:

The infix expression to be converted is in the input file in the format of one character per line, with a maximum of 50 lines in the file. For example, (3+2)*5 would be in the form: ( 3 + 2 ) * 5
The input starts with an integer on a line by itself indicating the number of test cases. Several infix expressions follows, preceded by a blank line.
The program will only be designed to handle the binary operators +, -, *, /.
The operands will be one digit numerals.
The operators * and / have the highest priority. The operators + and - have the lowest priority. Operators at the same precedence level associate from left to right. Parentheses act as grouping symbols that over-ride the operator priorities.
Each testcase will be an expression with valid syntax

Expected uotput:

The output file will have each postfix expression all on one line. Print a blank line between different expressions.

Sample Input

(

)

Sample Output

32+5*

Solution:

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cctype>
#include <cstdio>
#include<stack>
#include<algorithm>
using namespace std;

int main()
{
    int t, j, i, len,k, length;
    char expr[100];
    char ch[5];
    scanf("%d\n",&t);
    for(j=1;j<=t;j++)
    {
        stack<char> expstack;
        expstack.push('(');
        k=0;
        while(gets(ch))
        {
            len=strlen(ch);
            if (len==0)
                break ;
            else
                expr[k++]=ch[0];
        }
        expr[k++]=')';
        length=k;
        if(j>1)
            printf("\n");
        for(i=0;i<length;i++)
        {
            if(expr[i]=='('|| expr[i]=='+' || expr[i]=='-' || expr[i]=='*' || expr[i]=='/')
            {
                if((expr[i]=='+' || expr[i]=='-') && (expstack.top()=='*' || expstack.top()=='/' || expstack.top()=='+' || expstack.top()=='-'))
                {
                    while(expstack.top()=='*' || expstack.top()=='/' || expstack.top()=='+' || expstack.top()=='-')
                    {
                        printf("%c",expstack.top());
                        expstack.pop();
                    }
                    expstack.push(expr[i]);
                }
                else if((expr[i]=='*' || expr[i]=='/') &&(expstack.top()=='*' || expstack.top()=='/'))
                {
                        printf("%c",expstack.top());
                        expstack.pop();
                        expstack.push(expr[i]);
                }
                else
                    expstack.push(expr[i]);
           }
           else if(expr[i]==')')
           {
               while(expstack.top()!='(')
                    {
                        printf("%c",expstack.top());
                        expstack.pop();
                    }
                    expstack.pop();
           }
           else
            printf("%c",expr[i]);
        }
        while(!expstack.empty())
        {
            printf("%c",expstack.top());
            expstack.pop();
        }
            printf("\n");
    }
    return 0;
}

Solution of 10127 - Ones

noreply@blogger.com (Shaishab Roy) — Tue, 22 Aug 2017 17:26:00 +0000

Problem description:
source: https://uva.onlinejudge.org/external/101/10127.html

Given any integer 0 ≤ n ≤ 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1’s. How many digits are in the smallest such a multiple of n?

Input

A fle of integers at one integer per line.

Output

Each output line gives the smallest integer x > 0 such that p = ∑x i=0 -1 1 × 10i = a × b, where a is the corresponding input integer, and b is an integer greater than zero.

Sample Input

37
9901

Sample Output

36
12

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
    int input,k,one,dividend;
    while(scanf("%d",&input)==1)
    {
        dividend=1;
        one=1;
        if(input==0)
            printf("0\n");
        else
        {
            do{
                if(dividend<input)
                {
                    dividend=(dividend*10)+1;
                    one+=1;
                }
                k=dividend%input;
                if(k!=0)
                    dividend=k;
            }while(k!=0);
            printf("%d\n",one);
        }

    }
    return 0;
}

Solution of 12895 - Armstrong Number

noreply@blogger.com (Shaishab Roy) — Sun, 08 Nov 2015 10:36:00 +0000

Problem description
source: https://uva.onlinejudge.org/external/128/12895.html

Input

The first line of input is an integer, T that determines the number of test cases. Each of the next T lines contain a positive integer N, where N ≤ 1000000000.

Output

For each line of input, there will be one line of output. If N is an Armstrong number print ‘Armstrong’, otherwise print ‘Not Armstrong’ (without the quotes).

Sample Input

3
153
2732
54748

Sample Output

Armstrong
Not Armstrong
Armstrong

Solution:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

using namespace std;

int main() {
    int i, t, n, ArmN, ArmNumbuer, digit;
    while(scanf("%d",&t)==1) {
        for(i=0; i<t; i++) {
            scanf("%d", &ArmN);
            ArmNumbuer = ArmN;
            n = 0;
            while(ArmN > 0) {
                ArmN /= 10;
                n+=1;
            }
            ArmN = ArmNumbuer;
            while(ArmN > 0) {
                digit = ArmN % 10;
                ArmN /= 10;
                ArmNumbuer -= pow(digit, n);
            }
            if(ArmNumbuer == 0)
                printf("Armstrong\n");
            else
                printf("Not Armstrong\n");
        }
    }
    return 0;
}

Algorithm of 12608 - Garbage Collection

noreply@blogger.com (Shaishab Roy) — Sun, 12 Oct 2014 19:01:00 +0000

Problem Description Link
Algorithm

This is a simple problem this problem you can solve easily . To solve this problem you must remember 3 conditions.

Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either

is full or
cannot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
there are no more pick up points left

when you return to dump you need 2 time distance.

For example

3 3

1 2

2 2

3 1

In this example the truck can load 3 ton and 3 points .

First step :

Go to point 1 take garbage then go to point 2 but don’t take garbage because of overload weight so go back to dump and empties its contents . distance for one time=2

Second step:

Again go to point 2 and take garbage then go to point 3 and take garbage because no over load

So distance for one way for second stapes= 3 and return to dump

So total one way distance for all stapes= 2+3 =5

Each time need back to dump so total distance= 5*2 =10

So 10 is final result.

e.g. this is not allowed: get a portion of garbage at some point until truck is full and come back for the rest and same operation perform when truck is full.

12608 - Garbage Collection

noreply@blogger.com (Shaishab Roy) — Sun, 12 Oct 2014 18:49:00 +0000

Problem Descriptin
source:https://uva.onlinejudge.org/external/126/12608.html

is full or
cannnot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
there are no more pick up points left

The pick up run ends when the truck returns to the dump after the case #3. In the case where both rule #1 and rule #3 apply, we consider only the latter one (the run is over). Also note that there are no partial pick ups (e.g. this is not allowed: get a portion of garbage at some point until truck is full and come back for the rest).
Given the weight limit that truck can carry and the list of pick up points with garbage weights, what is the distance that the truck will cover following the rules above?

Input

Input starts with an integer T on the first line, the number of test cases. Each case starts with the line with two integers W and N, the weight limit and the number of pick up points, respectively.
Then N lines follow, each containing integers xi and wi , the distance from the dump and the weight of the garbage at the pick up point respectively.
Constraints are as given: 1 ≤ W ≤ 1000, 1 ≤ N ≤ 1000, 0 < xi ≤ 100, 000, 1 ≤ wi ≤ W. Distances are distinct and given in order, i.e. for each i < j, xi < xj .

Output

For each test case output an integer on a line — the distance covered by the garbage truck.

Sample Input

3
2 2
1 1
2 2
6 3
1 1
2 2
3 3
3 3
1 2
2 2
3 1

Sample Output

8
6
10

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    long long int w,n,t,i,j,di,wt,cwt,tdi;
    scanf("%lld",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%lld %lld",&w,&n);
        cwt=0;tdi=0;
        for(j=1;j<=n;j++)
        {
            scanf("%lld %lld",&di,&wt);
            if((cwt+wt)>w)
            {
                tdi+=di;
                cwt=0;
            }
            if((cwt+wt)==w)
            {
                tdi+=di;
                cwt=0;
                di=0;
            }
            else
                cwt+=wt;
        }
        tdi+=di;
        printf("%lld\n",tdi*2);
    }
    return 0;

}

Solution of 12578 - 10:6:2

noreply@blogger.com (Shaishab Roy) — Wed, 16 Jul 2014 18:40:00 +0000

Problem Description
source: https://uva.onlinejudge.org/external/125/12578.html

The national flag of Bangladesh is bottle green in color and rectangular in size with the length (L) to width ratio of 10:6. It bears a red circle on the background of green. It maintains the length (L) to radius ratio of 5:1 (If the length is 10 then width should be 6 and radius should be 2). The color in the background represents the greenery of Bangladesh while the red circle symbolizes the rising sun and the sacrifice of lives in our freedom fight.

Input

First line of input will contain the number of test cases, T ≤ 100. Then there follows T lines, each containing a positive integer L ≤ 1000, representing length of the flag.

Output

For each test case output is a line with two space separated real numbers containing exactly two digits after decimal point. Two numbers represent the area of red and green portion respectively. Note: Pi is considered to be arccos(−1).

Sample Input

1
10

Sample Output

12.57 47.43

Solution :

#include <algorithm>
#include <cstdio>
#include <cmath>
#include<stdio.h>
#define PI acos(-1)
using namespace std;

int main()
{
    int t,i;
    double l,w,r,areac, arearec;
    while(scanf("%d",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%lf",&l);
            r=l/5;
            w=(l*6)/10;
            areac=PI*r*r;
            arearec=(l*w)-areac;
            printf("%.2lf %.2lf\n",areac,arearec);
        }
    }
    return 0;
}

Algorithm of 12405 - Scarecrow

noreply@blogger.com (Shaishab Roy) — Mon, 07 Jul 2014 17:25:00 +0000

Problem Description Link
Algorithm:
This is a easy problem just you get a string
scan each character until length of string
if character is '.' then replace the next character by '#' and
increase the counter value and set position=position+2;
some input/output:

6
4
#.#.
5
#.#.#
5
#..#.
11
...##....##
5
#####
11
...........
o/p:
Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 3
Case 5: 0
Case 6: 4

Solution of 12405 - Scarecrow

noreply@blogger.com (Shaishab Roy) — Mon, 07 Jul 2014 17:19:00 +0000

Problem Description
source: https://uva.onlinejudge.org/external/124/12405.html

Taso owns a very long field. He plans to grow different types of crops in the upcoming growing season. The area, however, is full of crows and Taso fears that they might feed on most of the crops. For this reason, he has decided to place some scarecrows at different locations of the field.

The field can be modeled as a 1×N grid. Some parts of the field are infertile and that means you cannot grow any crops on them. A scarecrow, when placed on a spot, covers the cell to its immediate left and right along with the cell it is on.

Given the description of the field, what is the minimum number of scarecrows that needs to be placed so that all the useful section of the field is covered? Useful section refers to cells where crops can be grown.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases. Each case starts with a line containing an integer N (0 < N < 100). The next line contains N characters that describe the field. A dot (.) indicates a crop-growing spot and a hash (#) indicates an infertile region.

Output

For each case, output the case number first followed by the number of scarecrows that need to be placed.

Sample Input

2
10
..#..##...
13
..#..##....#.

Sample Output

Case 1: 3
Case 2: 4

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    int i,j,len,t,count;
    char ch[105];
    while(scanf("%d",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%d",&len);
               scanf("%s",&ch);

            count=0;
            for(j=0;j<len;j++)
            {
                if(ch[j]=='.')
                {
                    ch[j+1]='#';
                    count+=1;
                    j+=2;
                }
            }
            printf("Case %d: %d\n",i,count);
        }
    }
    return 0;
}

Algorithm of 11933 - Splitting Numbers

noreply@blogger.com (Shaishab Roy) — Sun, 06 Jul 2014 17:41:00 +0000

Problem Description Link
Algorithm:

This is a simple problem the operation of splitting a binary number n into two numbers a(n), b(n) .

you need to convert decimal to binary format for a given number and from that binary format create two numbers

a(n) and b(n). To build first value a(n) need to choice 1^st 1 ,3^rd 1, 5^th 1,..... so on same position of original binary format other position fii by the value 0.

To build second value b(n) need to choice 2^nd 1 ,4^th 1, 6^th 1,..... so on same position of original binary format other position fill by the value 0.

for example

n=13

binary format

3 2 1 0 index

1(3^rd 1)

1 (1^st 1)

For a(n)

1(2^nd 1)

For b(n)

So a= 9 and b=4

Solution of 11933 - Splitting Numbers

noreply@blogger.com (Shaishab Roy) — Sun, 06 Jul 2014 17:34:00 +0000

Problem Description
source:https://uva.onlinejudge.org/external/119/11933.html

We define the operation of splitting a binary number n into two numbers a(n), b(n) as follows. Let 0 ≤ i1 < i2 < . . . < ik be the indices of the bits (with the least significant bit having index 0) in n that are 1. Then the indices of the bits of a(n) that are 1 are i1, i3, i5, . . . and the indices of the bits of b(n) that are 1 are i2, i4, i6, . . .
For example, if n is 110110101 in binary then, again in binary, we have a = 010010001 and b = 100100100.

Input

Each test case consists of a single integer n between 1 and 231 − 1 written in standard decimal (base 10) format on a single line. Input is terminated by a line containing ‘0’ which should not be processed.

Output

The output for each test case consists of a single line, containing the integers a(n) and b(n) separated by a single space. Both a(n) and b(n) should be written in decimal format.

Sample Input

25 5000 1000000 2000000000 2147483647 0

Sample Output

17 8 4360 640 671808 328192 1378124800 621875200 1431655765 715827882

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    int n,even,temp1,c,sum;
    while(scanf("%d",&n)==1)
    {
        if(n==0)
            break;
        temp1=n;
        c=0;even=0;sum=0;
        while(temp1!=0)
        {
            if(temp1%2==1)
            {
                even++;
                if(even%2==1)
                {
                    sum+=pow(2,c);
                }
            }
            temp1/=2;
            c++;
        }
        printf("%d %d\n",sum,n-sum);
    }
    return 0;
}

Solution of 11559 - Event Planning

noreply@blogger.com (Shaishab Roy) — Sun, 06 Jul 2014 16:00:00 +0000

Problelm description
source: http://uva.onlinejudge.org/external/115/11559.html

As you didn’t show up to the yearly general meeting of the Nordic Club of Pin Collectors, you were unanimously elected to organize this years excursion to Pin City. You are free to choose from a number of weekends this autumn, and have to find a suitable hotel to stay at, preferably as cheap as possible. You have some constraints: The total cost of the trip must be within budget, of course. All participants must stay at the same hotel, to avoid last years catastrophe, where some members got lost in the city, never being seen again.

Input

The input file contains several test cases, each of them as described below. The first line of input consists of four integers: 1 ≤ N ≤ 200, the number of participants, 1 ≤ B ≤ 500000, the budget, 1 ≤ H ≤ 18, the number of hotels to consider, and 1 ≤ W ≤ 13, the number of weeks you can choose between. Then follow two lines for each of the H hotels. The first gives 1 ≤ p ≤ 10000, the price for one person staying the weekend at the hotel. The second contains W integers, 0 ≤ a ≤ 1000, giving the number of available beds for each weekend at the hotel.

Output

For each test case, write to the output the minimum cost of the stay for your group, or “stay home” if nothing can be found within the budget, on a line by itself.

Sample Input

3 1000 2 3
200
0 2 2
300
27 3 20
5 2000 2 4
300
4 3 0 4
450
7 8 0 13

Sample Output

900
stay home

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    long long int nPerson,budget,hotel,week,price,sit,i,j,flag,cost,tempCost,get;
    //freopen("in.txt","r",stdin);
    while(scanf("%lld %lld %lld %lld",&nPerson, &budget, &hotel, &week)==4)
    {
      cost=500005;get=0;
        for(i=1;i<=hotel;i++)
        {
            flag=0;
            scanf("%lld",&price);
            for(j=1;j<=week;j++)
            {
                scanf("%lld",&sit);
                if(sit>=nPerson)
                    flag=1;
            }
            tempCost=price*nPerson;
            if(flag==1 && tempCost<=budget && cost>tempCost)
            {
                cost=tempCost;
                get=1;
            }
        }
        if(get==1)
            printf("%lld\n",cost);
        else
            printf("stay home\n");
    }
    return 0;
}

Algorithm of 11407 - Squares

noreply@blogger.com (Shaishab Roy) — Thu, 13 Mar 2014 20:31:00 +0000

Problem Description Link
Algorithm:

This is a simple problem to solve this problem you can pre generate the number of minimum terms for all integer from 1 to 10000 and get input and check from array how many term needed and print the value.

Process:

For any positive integer N , N = a12 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.

For example you know minimum term of 1,2,3,4 and based on this value calculate others 5 to 10000 value term

1 2 3 4 5 6 7 8 9 10

For 5

S=sqrt(5)=2

Way 2²+1²=5 so 2 term

And 1²+2²=5 so 2 term

Min value=2

Loop from ( s=2 to 1)

array[5- 2*2]+1=2 because 2²=4 and (5-1)=1we know term of 1=1 so 2² is 1 term and for 1 need 1 term so total term=(1+1)=2

array[5- 1*1]+1=2 because 1²=1+1²we know term of 1=1 so 2² is 1 term and for 1 need 1 term so total term=(1+1)=2

so array[5]=2;

For 10

S=sqrt(10)=3

Loop from (3 to 1)

Array[10-3*3]+1=2

Array[10-2*2]+1=4

Array[10-1*1]+1=2 so min =2 so array[10]=2

Solution of 11407 - Squares

noreply@blogger.com (Shaishab Roy) — Thu, 13 Mar 2014 20:20:00 +0000

Problem Description
source: http://uva.onlinejudge.org/external/114/11407.html

For any positive integer N, N = a 2 1 + a 2 2 + . . . + a 2 n that is, any positive integer can be represented as sum of squares of other numbers. Your task is to print the smallest ‘n’ such that N = a 2 1 + a 2 2 + . . . + a 2 n.

Input

The first line of the input will contain an integer ‘t’ which indicates the number of test cases to follow. Each test case will contain a single integer ‘N’ (1 ≤ N ≤ 10000) on a line by itself.

Output

Print an integer which represents the smallest ‘n’ such that N = a 2 1 + a 2 2 + . . . + a 2 n.

Explanation for sample test cases:
5 → number of test cases
1 = 12 (1 term)
2 = 12 + 12 (2 terms)
3 = 12 + 12 + 12 (3 terms)
4 = 22 (1 term)
50 = 52 + 52 (2 terms)

Sample Input

5 1 2 3 4 50

Sample Output

1 2 3 1

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
    int i,j,t,n,s,value[10005],c,minValue;
    value[1]=1;value[2]=2;value[3]=3;value[4]=1;
    for(i=5;i<10001;i++)
    {
        s=sqrt(i);
        c=1000;
        for(j=s;j>0;j--)
        {
            minValue=value[i-(j*j)]+1;
            if(c>minValue)
                c=minValue;
        }
        value[i]=c;
    }
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%d",&n);
            printf("%d\n",value[n]);
        }
    }
    return 0;
}

Solution of 11219 - How old are you?

noreply@blogger.com (Shaishab Roy) — Wed, 20 Nov 2013 14:16:00 +0000

Problem Description
source:http://uva.onlinejudge.org/external/112/11219.html

- Here are the filled form. - Thank you. Let me check... hum... OK, OK, OK... Wait, how old are you? - 20. Did I forget to fill it?
- No. It says here that you’ll be born next month! The year is wrong...
- Oh... Sorry!

The process is going to be automatic and to avoid some human errors there will be a calculated field that informs the age based in the current date and the birth date given. This is your task, calculate the age, or say if there’s something wrong.

Input The first line of input gives the number of cases, T (1 ≤ T ≤ 200). T test cases follow. Each test case starts with a blank line, then you will have 2 lines corresponding to the current date and the birth date, respectively. The dates are in the format DD/MM/Y Y Y Y , where DD is the day, MM the month and Y Y Y Y the year. All dates will be valid.

Output

The output is comprised of one line for each input data set and should be as follow (quotes for clarifying only):
‘Case #N: AGE’, where N is the number of the current test case and AGE is one of the 3 following options:
• ‘Invalid birth date’, if the calculated age is impossible (still going to be born).
• ‘Check birth date’, if the calculated age is more than 130.
• the calculated age (years old only), otherwise.
• If the two dates are the same, the output should be ‘0’.

Sample Input

4 01/01/2007
10/02/2007

09/06/2007
28/02/1871

12/11/2007
01/01/1984

28/02/2005
29/02/2004

Sample Output

Case #1: Invalid birth date
Case #2: Check birth date
Case #3: 23
Case #4: 0

Solution

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    int t,day,month,year,cDay,cMonth,cYear,i,age;
    while(scanf("%d",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%d/%d/%d",&cDay,&cMonth,&cYear);
            scanf("%d/%d/%d",&day,&month,&year);
            if(cDay<day)
                month+=1;
            if(cMonth<month)
                year+=1;
            age=cYear-year;
            if(age<0)
                printf("Case #%d: Invalid birth date\n",i);
            else if(age>130)
                printf("Case #%d: Check birth date\n",i);
            else
                printf("Case #%d: %d\n",i,age);
        }
    }
    return 0;
}

Solution of 12403 - Save Setu

noreply@blogger.com (Shaishab Roy) — Sat, 09 Nov 2013 14:26:00 +0000

Problem Description
source: https://uva.onlinejudge.org/external/124/p12403.html

Rahaduzzaman Setu, (Roll - 12) of 13th batch, CSE, University of Dhaka is tremendously ill. He has been suffering from Multi Drug Resistant TB for a long time. Now, his left lung is damaged and beyond repair. No medicine is working on his body to ease his pain. It is urgent to operate on his left lung so that the disease doesn’t spread to his right lung. It can either be removed through surgery or transplanted. He comes from a modest family and it is difficult and impossible for them to bare his medical expenses anymore. Because of the money needed (12 million BDT) to transplant, it is his family’s decision to go with the surgery (3 million BDT). We must help them financially by raising money. But we must not be confined with that amount only to do the surgery. We must go for the Transplant. Our target will be to collect as much as possible to help our friend. If anyone wants to contribute now, please send me your contribution or contact me. Please contribute as much as you can to save a life that you saw every week for the first two years of your University life. Please contribute as per your abilities. Our combined effort may save a life. For more information, consult the link below

https://supportsetu.com/

However, in this problem, you have to build a software that can calculate the donations. Initially the total amount of money is 0 and in each time, two types of operations will be there. 1) ‘donate K’ (100 ≤ K ≤ 105 ), then you have to add K to the account. 2) ‘report’, report all the money currently in the account.

Input

The first line of input will contain T (1 ≤ T ≤ 100) denoting the number of operations. Then there will be T lines each containing two types of operations as given. You may assume that the input follows the restrictions above.

Output

For each ‘report’ operation, print the total amount of money in the account.

Sample Input

4
donate 1000
report
donate 500
report

Sample Output

1000
1500

Solution

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
int main()
{
    long long int total,k,t,i;
    char str1[50];
    //freopen("in.txt","r",stdin);
    while(scanf("%lld",&t)==1)
    {
        total=0;
        for(i=1;i<=t;i++)
        {
            scanf("%s",&str1);
            if(strcmp(str1,"donate")==0)
            {
                scanf("%lld",&k);
                total+=k;
            }
            else
                printf("%lld\n",total);
        }
    }
    return 0;
}

Algorithm of 11526 - H(n)

noreply@blogger.com (Shaishab Roy) — Sat, 09 Nov 2013 12:13:00 +0000

Problem Description Link
Algorithm
The problem is not difficult but we need to consider the problem of time limit exceeded, e.g. we are computing n/n, n/n-1, .....there are so many ones and twos,... these can be computed in one step. We can observe the number of 1, 2, 3.....the number of j is n/j - n/(j+1). so when the number is small and many, we use the n/j - n/(j+1) method. for numbers big and few, just use the original method. We can set the break point at sqrt(n). Do not repeat the values around sqrt(n). Try to avoid division by 0 and sqrt of negative numbers.

Example:
if n=5 series is 5/1 + 5/2 + 5/3 + 5/4 + 5/5
    then sqrt(5)=2 need loop two times
    5/1-5/2=3 means 1 get 3 times, so SUM=3*1=3
    5/2-5/3=1 means 2 get 1 times, so SUM=3+2*1=5
    so last 4 (3+1) steps complete from the series ,so now we nedd calculate first 1 step
    5/1=5 , so SUM=5+5=10
if n=10 series is 10/1 + 10/2 + 10/3 + 10/4 + 10/5+.... +10/10
    then sqrt(10)=3 need loop two times
    10/1-10/2=5 means 1 get 5 times, so SUM=5*1=5
    10/2-10/3=2 means 2 get 2 times, so SUM=5+2*2=9
    10/3-10/4=1 means 3 get 1 time, so SUM=9+3*1=12
    so last 8(5+2+1) steps complete from the series ,so now we nedd calculate first 2 step

    10/1=10 , so SUM=12+10=22
    10/2=5 , so SUM=22+5=27

Solution of 11526 - H(n)

noreply@blogger.com (Shaishab Roy) — Sat, 09 Nov 2013 12:05:00 +0000

Problem Description
source: https://uva.onlinejudge.org/external/115/11526.html

What is the value this simple C++ function will return?

long long H(int n){ 
    long long res = 0;
    for( int i = 1; i <= n; i=i+1 ){
        res = (res + n/i);
    } 
    return res; 
}

Input

The first line of input is an integer T (T ≤ 1000) that indicates the number of test cases. Each of the next T line will contain a single signed 32 bit integer n.

Output

For each test case, output will be a single line containing H(n).

Sample Input

2 5 10

Sample Output

10 27

Solution

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
    long long int n,sum,i,j,k,rootn,loop1,loop2,t,noOfj;
    //freopen("input.txt","r",stdin);
    while(scanf("%lld",&t)==1)
    {
        for(k=1;k<=t;k++)
        {
            scanf("%lld",&n);
            loop1=0;
            loop2=0;
            sum=0;
            rootn=sqrt(n);
            for(j=1;j<=rootn;j++)
            {
                noOfj=(n/j)-(n/(j+1));
                loop1+=noOfj;
                sum+=noOfj*j;
            }
            loop2=n-loop1;
            for(i=1;i<=loop2;i++)
            {
                sum+=n/i;
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}

Solution of 10523 - Very Easy !!!

noreply@blogger.com (Shaishab Roy) — Tue, 05 Nov 2013 20:52:00 +0000

Problem Description
source:https://uva.onlinejudge.org/external/105/10523.html

Most of the times, the students of Computer Science & Engineering of BUET deal with bogus, tough and very complex formulae. That is why, sometimes, even for a easy problem they think very hard and make the problem much complex to solve. But, the team members of the team “BUET PESSIMISTIC” are the only exceptions. Just like the opposite manner, they treat every hard problem as easy and so cannot do well in any contest. Today, they try to solve a series but fail for treating it as hard. Let them help.

Input

Just try to determine the answer for the following series ∑ N i=1 iAi You are given the value of integers N and A (1 ≤ N ≤ 150, 0 ≤ A ≤ 15).

Output

each line of the input, your correct program should output the integer value of the sum in separate lines for each pair of values of N and A

Sample Input

3 3 4 4

Sample Output

102 1252

Solution

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
void Multiply();
void MultiplyWithI(int value1);
void Addition();
int lena,lenb,lenResult,lenResult1,lenSum,result[1000],result1[1000],sum[1000],carry,temp,f;
char a[1000],b[1000],c[10];

int main()
{
    int n,i,j;
    //freopen("in.txt","r",stdin);
    while(scanf("%d%s",&n,&b)==2)
    {
        lenSum=0;
        lena=1;
        lenb=strlen(b);
        a[0]='1';
        for(j=1;j<=n;j++)
        {
            Multiply();
            lena=strlen(a);
            MultiplyWithI(j);
            Addition();
        }
        if(strcmp(b,"0")==0)
            printf("0");
        else
        {
            for(i=f;i>=1;i--)
            {
                printf("%d",sum[i]);
            }
        }

        printf("\n");
        memset(a,'\0',sizeof(a));
        memset(b,'\0',sizeof(b));
        memset(c,'\0',sizeof(c));
        memset(result,0,sizeof(result));
        memset(result1,0,sizeof(result1));
        memset(sum,0,sizeof(sum));
    }
    return 0;
}

void Multiply()
{

    int i,j,k,m=0,l;
    k=0;
        for(i=lenb-1;i>=0;i--)
        {
            k+=1;
            l=k-1;
            carry=0;
            for(j=lena-1;j>=0;j--)
            {
                l+=1;
                if(i==lenb-1)
                    temp=(b[i]-48)*(a[j]-48)+carry;
                else
                    temp=(b[i]-48)*(a[j]-48)+result[l]+carry;
                result[l]=temp%10;
                carry=temp/10;
            }
            if(carry>0)
            {
                l+=1;
                result[l]=carry;
            }
        }
        lenResult=l;
        for(i=l;i>=1;i--)
        {
            a[m++]=result[i]+48;
        }
}

void MultiplyWithI(int value1)
{
    int i,j,k,m=0,x=0,lenc,l;
    k=0;
    while(value1!=0)
    {
        c[x++]=(value1%10)+48;
        value1/=10;
    }
    lenc=strlen(c);
        for(i=0;i<=lenc-1;i++)
        {
            k+=1;
            l=k-1;
            carry=0;
            for(j=1;j<=lenResult;j++)
            {
                l+=1;
                if(i==0)
                    temp=(c[i]-48)*result[j]+carry;
                else
                    temp=(c[i]-48)*result[j]+result1[l]+carry;
                result1[l]=temp%10;
                carry=temp/10;
            }
            if(carry>0)
            {
                l+=1;
                result1[l]=carry;
            }
        }
        lenResult1=l;
}
void Addition()
{
    int i,max1,tem,k=0;
    max1=lenSum;
    if(lenResult1>lenSum)
        max1=lenResult1;
    carry=0;
    for(i=1;i<=max1;i++)
    {
     tem=sum[i]+result1[i]+carry;
     k+=1;
     sum[k]=tem%10;
     carry=tem/10;
    }
    if(carry>0)
    {
        k+=1;
        sum[k]=carry;
    }
    lenSum=k;
    f=k;
    memset(result1,0,sizeof(result1));
}

Solution of 10324 - Zeros and Ones

noreply@blogger.com (Shaishab Roy) — Tue, 05 Nov 2013 20:36:00 +0000

Problem Description
source:https://uva.onlinejudge.org/external/103/10324.html

Given a string of 0’s and 1’s up to 1000000 characters long and indices i and j, you are to answer a question whether all characters between position min(i, j) and position max(i, j) (inclusive) are the same.

Input

There are multiple cases on input. The first line of each case gives a string of 0’s and 1’s. The next line contains a positive integer n giving the number of queries for this case. The next n lines contain queries, one per line. Each query is given by two non-negative integers, i and j. For each query, you are to print ‘Yes’ if all characters in the string between position min(i, j) and position max(i, j) are the same, and ‘No’ otherwise.

Output

Each case on output should start with a heading as in the sample below. The input ends with an empty string that is a line containing only the new line character, this string should not be processed. The input may also with end of file. So keep check for both.

Sample Input

0000011111
3
0 5
4 2
5 9
01010101010101010101010101111111111111111111111111111111111110000000000000000
5
4 4
25 60
1 3
62 76
24 62
1
1
0 0

Sample Output

Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
No
Yes
No
Case 3:
Yes

Solution

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
int main()
{
    register long int i,j,n,a,b,ma,mi,get,c=0;
    char input[1000005];
    //freopen("in.txt","r",stdin);
    while(scanf("%s",input)==1)
    {
        cin>>n;
        c+=1;
        printf("Case %ld:\n",c);
        for(i=1;i<=n;i++)
        {
            cin>>a>>b;
            ma=max(a,b);
            mi=min(a,b);
            get=0;
            for(j=mi+1;j<=ma;j++)
            {
                if(input[j]==input[j-1])
                {
                    continue;
                }
                else
                {
                    get=1;
                    break;
                }
            }
            if(get==1)
                printf("No\n");
            else
                printf("Yes\n");
        }
        memset(input,'\0',sizeof(input));
    }
    return 0;
}

Algorithm of 10127 - Ones

noreply@blogger.com (Shaishab Roy) — Mon, 04 Nov 2013 20:56:00 +0000

Problem Description Link
Algorithm

This is a very simple but tricky problem. If you want to calculate the sequence of one by increasing ONE, then two things can be happened.

1) If your data type is even long double (in C it is the highest data type), it can not hold the sequence and because of overflow you will get WA.
2) If your data type is string then you will get "time limit exceeded". To avoid these problems we need to follow a trick here.

The Algorithm

input (it will be the input of the problem)
dividend=1
one=1 (in this variable finally we get how many one will be in the sequence)

do {
  if dividend < input
    append a '1'. (this the way -> dividend= dividend *10+1)
    one = one + 1
  k = dividend mod input ( k is a variable )
do this until k = 0, otherwise dividend = k and repeat everything
}

Example

Let the input is 3
At first dividend = 1 and one = 1

Now,
3 | 1 | but here dividend < input so, append a '1'
one = one + 1 = 2
3 | 11| 3
     9
   -----
   2
Now, k = 2, so, dividend =k;
again,

3 | 2 | but here dividend < input so append a '1'
one = one + 1 = 3

3 | 21| 7
    21
  -----
     x

So the output is variable 'one' which contains the value 3

Basically, this problem is a reverse version of dividing a series of '1's with dividend. In the example above. The step by step of dividing "111" with "3" is like this:

3 |111| 37
    9   => the same '9' that we see above
-----
    21
    21 => the same '21' that we see above
   ----
     x

So, basically we just simulate this division but without spanning out the actual string of '1's.

Algorithm of 713 - Adding Reversed Numbers

noreply@blogger.com (Shaishab Roy) — Fri, 01 Nov 2013 20:51:00 +0000

Problem Description Link
Algorithm
This is the simple string related problem. You can solve easily using your defined string adding function. you need first
reverse the string that you entered and add two string. after adding print the result reveser order. You must
Omit any leading zeros in the output.
You no need reverse the inputs if you adding atart from left most. but you nee create same length two string by insert 0.
For Example:
a=4358
b=754
length not same so create same length add 0 in b at right most
b=7540
now add
a=4358
b=7540
-----------
r=1998 this is the result

if a=305 and b= 794

add
a=305
b=794
---------------
r= 0001 so you need avoid all leftmost 0 s, so 1 is the result.

Solution of 713 - Adding Reversed Numbers

noreply@blogger.com (Shaishab Roy) — Fri, 01 Nov 2013 20:47:00 +0000

Problem Description
source: https://uva.onlinejudge.org/external/7/713.html

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.

ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

Input

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add. Numbers will be at most 200 characters long.

Output

For each case, print exactly one line containing only one integer — the reversed sum of two reversed numbers. Omit any leading zeros in the output.

Sample Input

3
24 1
4358 754
305 794

Sample Output

34
1998
1

Solution

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
void Addition(int length);
 char str1[250],str2[250],result[250];
 int len3;
 int main()
 {
     int i,j,len1,len2,t,k,difr;
     //freopen("in.txt","r",stdin);
     while(scanf("%d",&t)==1)
     {
         for(k=1;k<=t;k++)
         {
             scanf("%s %s",&str1,&str2);
             len3=0;
             len1=strlen(str1);
             len2=strlen(str2);
             if(len1>len2)
             {
                 difr=(len1-len2)+len2;
                 for(i=len2;i<difr;i++)
                    str2[i]='0';
                Addition(len1);
             }
             else
             {
                 difr=(len2-len1)+len1;
                 for(i=len1;i<difr;i++)
                    str1[i]='0';
                Addition(len2);
             }
             i=1;
             while(result[i]=='0')
             {
                 i++;
             }
             for(j=i;j<=len3;j++)
                printf("%c",result[j]);
             printf("\n");
             memset(str1,'\0',sizeof(str1));
             memset(str2,'\0',sizeof(str2));
             memset(result,'\0',sizeof(result));
         }
     }
     return 0;
 }
void Addition(int length)
{
    int i,tem,carry=0;
    len3=0;
    for(i=0;i<length;i++)
    {
     tem=(str1[i]-48)+(str2[i]-48)+carry;
     len3+=1;
     result[len3]=((tem%10)+48);
     carry=tem/10;
    }
    if(carry>0)
    {
        len3+=1;
        result[len3]=carry+48;
    }
}