UVA 948 - Fibonaccimal Base Solution

Problem Statement: Fibonaccimal Base

Explanation

Actually this problem is similar with decimal to binary conversion but in this case you use a fibonacci sequence as a base. First thing to do is generate all fibonacci number less than 100.000.000 and store it in the array size of 50 or less (the 50th number in fibonacci number is 12.586.269.025). After generating the fibonacci sequence, you can backward iterate the array.

• If you found number less than or equal to the input, append string result with "1" and subtract the input.
• else append string with "0".

Source Code

UVA 10783 - Odd Sum Solution

Problem Statement: Odd Sum

Explanation

Each test case consists of 2 integers a and b (0 ≤ a ≤ b ≤ 100). Because the upper bound not so big, this problem can be solved using brute force.

Source Code

UVA 900 - Brick Wall Patterns Solution

Problem Statement: Brick Wall Patterns

Explanation

There's two way to assembly a wall of length n.

• Put one brick in vertical position which gives us f(n-2) different patterns.
• Put two horizontal brick on top of another which gives us f(n-1) different patterns.

Base case f(1) = 1 and f(2) = 2.

Optimization

Before doing the iteration check whether the answer has been found or not.

Source Code

UVA 10055 - Hashmat the Brave Warrior Solution

Problem Statement: Hashmat the Brave Warrior

Explanation

There's a chance that second input greater than the first one. So you must check it before do the operation or you can use Math.abs().

Source Code

SPOJ 31 - MUL Solution

Problem Statement: Fast Multiplication

Explanation

Multiply the given numbers. The numbers to multiply at most 10000 decimal digits each. This problem can be solved easily using Java BigInteger.

Source Code

UVA 10954 - Add All Solution

Problem Statement: Add All

Explanation

This problem can be solved easily by using Java PriorityQueue.

• Insert all input to PriorityQueue and create variable "sum" to store the final result.
• Take 2 item from the queue and store the sum result of those 2 item in variable "temp".
• Add "temp" to "sum.
• Finally insert "temp" back to queue and repeat the process above until there's only 1 item in queue.

Source Code

SPOJ 97 - PARTY Solution

Problem Statement: Party Schedule

Explanation

This problem can be solved using 0-1 knapsack. Read this resource to learn more about 0-1 knapsack.
To find the optimal budget used, you can use backtracking. Traverse the last row and the least value of cost for which we can have the computed maximum fun is our answer for minimum cost.

Source Code

UVA 10300 - Ecological Premium Solution

Problem Statement: Ecological Premium

Explanation

Formula to solve this problem.
paid = (area / numAnimal) * efficiency * numAnimal

This formula can be simplified into.
paid = area * efficiency

Source Code

UVA 621 - Secret Research Solution

Problem Statement: Secret Research

Explanation

Do a digit checking for every case.

Source Code

UVA 11547 - Automatic Answer Solution

Problem Statement: Automatic Answer

Explanation

Just follow the calculation step in output section.

Source Code

UVA 11498 - Division of Nlogonia Solution

Problem Statement: Division of Nlogonia

Explanation

Do coordinate checking to solve this problem. (X, Y) coordinate of residence. (N, M) coordinate of division point.

• If X > N and Y > M, output NE.
• if X > N and Y < M, output SE.
• if X < N and Y > M, output NO.
• if X < N and Y < M, output SO.
• else output divisa.

Source Code

UVA 11364 - Parking Solution

Problem Statement: Parking

Explanation

To solve this problem you need to do this thing:

• Sort the input.
• Sum the distance between x1 > x2, x2 > x3, and so on.
• Then multiply it by 2 (Round-Trip).

Optimization

There's much simpler solution for this problem that does not include sorting. Just calculate the min and max while you read the input. Then find the min - max difference and multiply it by 2.

Source Code

UVA 11172 - Relational Operator Solution

Problem Statement: Relational Operator

Explanation

Simple problem, you can solve it by using multiple IF statement.

Source Code

UVA 11044 - Searching for Nessy Solution

Problem Statement: Searching for Nessy

Explanation

Some critical point from the problem statement:

• One sonar occupies one position in the grid; the sonar beam controls its own cell and the contiguous cells.
• The border cells do not need to be controlled, because Nessy cannot hide there.

Each sonar occupy a 3 x 3 area and because the border cell do not need to be controlled so we must cover an area of (n-2) x (m-2). Number of sonar needed can be calculated as follow

Num of Sonar = Ceil((m-2)/3) * Ceil((n-2)/3).

Source Code

UVA 100 - The 3n +1 problem solution

Problem Statement: The 3n +1 problem

Explanation

Some critical point from the problem statement:

• Determine the maximum cycle length over all numbers between and including both i and j. 
• No operation overflows a 32-bit integer.
• The integers i and j must appear in the output in the same order in which they appeared in the input

There's a possibility that j > i. So you must check it before processing further.

Optimization

Everytime you do the 3n + 1 operation, the result always an even integer. So everytime you do 3n + 1 operation you have to do n/2 operation as well. This two operation can be combined in one if statement then increment the cycle length by 2.

Source Code

SPOJ 91 - TWOSQRS Solution

Difficulty: Easy
Problem: Two squares or not two squares

Given integer n decide if it is possible to represent it as a sum of two squares of integers.

Input

First line of input contains one integer c <= 100 - number of test cases. Then c lines follow, each of them consisting of exactly one integer 0 <= n <= 10^12.

Output

For each test case output Yes if it is possible to represent given number as a sum of two squares and No if it is not possible.

Example

Input:
10
1
2
7
14
49
9
17
76
2888
27

Output:
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No

Explanation

There's multiple way to solve this problem such as prime factorization, Fermat's Theorem, and brute force approach. In brute force approach, you can solve this problem by trying all possible sum of squares between 0 up to square of n.

Source Code

SPOJ 32 - NHAY Solution

Difficulty: Easy
Problem: A Needle in the Haystack

Write a program that finds all occurences of a given pattern in a given input string. This is often referred to as finding a needle in a haystack.

The program has to detect all occurences of the needle in the haystack. It should take the needle and the haystack as input, and output the positions of each occurence, as shown below. The suggested implementation is the KMP algorithm, but this is not a requirement. However, a naive approach will probably exceed the time limit, whereas other algorithms are more complicated... The choice is yours.

Input

The input consists of a number of test cases. Each test case is composed of three lines, containing:

• the length of the needle,
• the needle itself,
• the haystack.

The length of the needle is only limited by the memory available to your program, so do not make any assumptions - instead, read the length and allocate memory as needed. The haystack is not limited in size, which implies that your program should not read the whole haystack at once. The KMP algorithm is stream-based, i.e. it processes the haystack character by character, so this is not a problem.

The test cases come one after another, each occupying three lines, with no additional space or line breaks in between.

Output

For each test case your program should output all positions of the needle's occurences within the haystack. If a match is found, the output should contain the position of the first character of the match. Characters in the haystack are numbered starting with zero.

For a given test case, the positions output should be sorted in ascending order, and each of these should be printed in a separate line. For two different test cases, the positions should be separated by an empty line.

Example

Sample input:
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo

Sample output:
2
4

3
9
15
21

Explanation

In this problem you need to find the number of string occurence and print the first index from every occurence. Brute force approach can be used to solve this problem.

There's also an algorithm that commonly used for string checking Knuth-Morris-Pratt Algorithm

Source Code

This is the solution using brute force approach.

SPOJ 39 - PIGBANK Solution

Diffiulty: Easy
Problem: Piggy-Bank

Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.

But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it's weight in grams.

Output

Print exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.".

Example

Sample Input:

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Sample output:

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

Explanation

This problem can be solved by using 1 dimensional array with the size of W (F - E) bottom up approach. Complexity O(W * N).

Source Code

SPOJ 54 - JULKA Solution

Difficulty: Easy
Problem Link: JULKA

Julka surprised her teacher at preschool by solving the following riddle:

Klaudia and Natalia have 10 apples together, but Klaudia has two apples more than Natalia. How many apples does each of he girls have?

Julka said without thinking: Klaudia has 6 apples and Natalia 4 apples. The teacher tried to check if Julka's answer wasn't accidental and repeated the riddle every time increasing the numbers. Every time Julka answered correctly. The surprised teacher wanted to continue questioning Julka, but with big numbers she could't solve the riddle fast enough herself. Help the teacher and write a program which will give her the right answers.

Task

Write a program which

• reads from standard input the number of apples the girls have together and how many more apples Klaudia has,
• counts the number of apples belonging to Klaudia and the number of apples belonging to Natalia,
• writes the outcome to standard output

Input

Ten test cases (given one under another, you have to process all!). Every test case consists of two lines. The first line says how many apples both girls have together. The second line says how many more apples Klaudia has. Both numbers are positive integers. It is known that both girls have no more than 10100 (1 and 100 zeros) apples together. As you can see apples can be very small.

Output

For every test case your program should output two lines. The first line should contain the number of apples belonging to Klaudia. The second line should contain the number of apples belonging to Natalia.

Example

Input:
10
2
[and 9 test cases more]

Output:
6
4
[and 9 test cases more]

Explanation

This problem categorized as easy problem cause the solution pretty straightforward.

• Subtract the different value (second input) from total value (first input).
• Store the subtract result in temp variable.
• Klaudia's apple = temp + different value (second input).
• Natalia's apple = temp.

The hard part from this problem is dealing with a big input constraint 10100 . But this problem can be solved easily by using Java BigInteger.

Source Code