ACM Problem Solution

Solution technique of 10684- The jckpot

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:

Solution of 10684- The jckpot

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).

Solution technique of UVA problem 727 Equqtion

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

UVA solution 727 Equation

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

Solution of 10127 - Ones

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

Solution of 12895 - Armstrong Number

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.

Algorithm of 12608 - Garbage Collection

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

12608 - Garbage Collection

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

Solution of 12578 - 10:6:2

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

Algorithm of 12405 - Scarecrow

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:

Solution of 12405 - Scarecrow

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.

Algorithm of 11933 - Splitting Numbers

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

Solution of 11933 - Splitting Numbers

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.

Solution of 11559 - Event Planning

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.

Algorithm of 11407 - Squares

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

Solution of 11407 - Squares

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.

Solution of 11219 - How old are you?

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.

Solution of 12403 - Save Setu

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

Algorithm of 11526 - H(n)

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

Solution of 11526 - H(n)

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; 
}