UVA 10298 Power Strings

Problem Link
Problem Type : Adhoc, String Processing
Difficulty Level : Easy
Author : Imdad
Run Time: 0.289

UVA 460 Overlapping Rectangles

Problem Link
Problem Type : Geometry, Overlapping Rectangles.
Difficulty Level : Easy
Author : Imdad
Run Time : 0.015

UVA 10589 Area

Problem Link
Problem Type : Geometry, Circle.
Difficulty Level : Easy
Author : Imdad

UVA 12160 Unlock the Lock

Problem Link
Problem Type : BFS.
Difficulty Level : 5(uHUNT)
Author : Imdad.

UVA 1225 Digit Counting

Problem Link
Problem Type : Brute Force.
Difficulty Level : Easy
Author : Imdad

UVA 11198 Dancing Digits

Problem Link
Problem Type : BFS.
Difficulty Level : 5
Run Time : 0.219
Author : Imdad

Briefly problem statement
Its a BFS problem. A special datastructure is used to save the visited states.

UVA 12356 Army Buddies

Problem Link
Problem Type : Data Structure.
Difficulty Level : Moderate 
Author : Imdad

Briefly problem statement
initialization sequence 1 to n, each operation will delete the specified interval, and returns the position of the point is not deleted interval at both ends of the closest, If you do not return an asterisk.

UVA 532 Solution

Problem Link
Problem Type : Single Source Shortest Path on Unweighted Graph (BFS).
Difficulty Level : Easy
Author : Imdad

Briefly problem statement
A 3d maze is given. We have to find out shortest path between a start point and a end point. Simple BFS can do the trick.

UVA 10183 - How Many Fibs? Solution

Problem Link
Problem Type : Linear Search.
Difficulty Level : Easy
Author : Imdad

Briefly problem statement
Two big number <= 10^100 will be given. We have to find out how many Fibonacci numbers are in the range [a,b]. We can easily generate Fibonacci numbers up to 10^100 digits. There are not more 500 Fibonacci numbers containing less than 10^100 digits.

UVA 11136 Hoax or what Solution

Problem Link
Problem Type : Data-structure(STL set)
Difficulty Level : Easy
Author : Imdad

Briefly problem statement
In his problem we have to insert int in sorted list and find out max and min regularly. So balanced binary tree can be a data structure to approach this problem. For this we can use STL set template.

UVA 11417 GCD Solution

Problem Type GCD
Problem Difficulty Easy
Problem Link

Problem Statement

Here GCD(i,j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

G=0; for(i=1;i<N;i++) for(j=i+1;j<=N;j++) {     G+=GCD(i,j); } /*Here GCD() is a function that finds the greatest common divisor of the two input numbers*/

UVA 11408 - Count DePrimes Solution

Problem Statement
 A number is called a DePrime if the sum of its prime factors is a prime number.

Given a and b count the number of DePrimes xi such that axib .

Input 

Each line contains a and b in the format ``a b ". 2a5000000 . ab5000000 .

Input is terminated by a line containing `0'.

Output 

Each line should contain the number of DePrimes for the corresponding test case.

UVA 11110 Equidivisions Solution

Problem Statement

An equidivision of an n x n square array of cells is a partition of the n² cells in the array in exactly n sets, each one with n contiguous cells. Two cells are contiguous when they have a common side.

A good equidivision is composed of contiguous regions. The figures show a good and a wrong equidivision for a 5x5 square:

       

Note that in the second example the cells labeled with 4 describe three non-contiguous regions and cells labeled with 5 describe two non-contiguous regions. You must write a program that evaluates if an equidivision of the cells in a square array is good or not.

UVA 11094 Continents Solution

Mijid the Great is the king of Dodars territory. He likes to travel between the cities in his territory and actually, you can never see him in the same city as where he was the day before. Therefore, he captured all territories of his continent! In spite of this fact, he has seen all cities of his territory so far and wants to capture another continent in order to have some choices to travel into new cities. Now, having the world map, he needs your help to find the biggest continent except the one in which he resides.

Maps are given as M x N tables, filled with at most two different letters denoting land and water regions. A continent is a set of connected land regions which is completely surrounded by water regions or the end of map. Two regions are assumed to be connected if they have an edge in common. The coordinates of top left region is (0,0) and bottom right region (M-1,N-1). Region with coordinates (x,N-1) should be assumed to  have a common edge with region (x,0) for every x between 0 and M-1 (inclusive).

UVA 10161 Ant on a Chessboard Solution

Problem Statement : 

 

Background

  One day, an ant called Alice came to an M*M chessboard. She wanted to go around all the grids. So she began to walk along the chessboard according to this way: (you can assume that her speed is one grid per second)

  At the first second, Alice was standing at (1,1). Firstly she went up for a grid, then a grid to the right, a grid downward. After that, she went a grid to the right, then two grids upward, and then two grids to the left…in a word, the path was like a snake.

  For example, her first 25 seconds went like this:

  ( the numbers in the grids stands for the time when she went into the grids)

25	24	23	22	21
10	11	12	13	20
9	8	7	14	19
2	3	6	15	18
1	4	5	16	17

5

4

3

2

1

1          2          3           4           5

At the 8^th second , she was at (2,3), and at 20^th second, she was at (5,4).

Your task is to decide where she was at a given time.

(you can assume that M is large enough)

UVA 11995 I Can Guess the Data Structure! Solution

Problem Statement :

There is a bag-like data structure, supporting two operations:

1 x

Throw an element x into the bag.

2

Take out an element from the bag.

Given a sequence of operations with return values, you're going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine!

UVA 11900 Boiled Eggs Solution

Problem Type Adhoc

Problem Difficulty Easy 

Problemset

Three of the trouble-makers went to Malaysia this year. A rest house was booked for them. Unlike other rest houses, this rest house was like a normal duplex house. So, it had a kitchen. And the trouble-makers were given all the ingredients to cook, but they had to cook themselves.

None of them had any previous cooking experience, but they became very excited and planned to cook so many delicious foods! Ideas were coming from their minds like rains from clouds. So, they went to the super market and bought a lot of extra ingredients for their great recipes. For example, they bought 20 eggs. The excited trouble-makers returned to the rest house and found that the gas stove was not connected to the gas cylinder. So, they became very sad, because it was not possible for them to connect such complex thing. And so many foods were about to be rotten. But luckily, they found the microwave oven working. So, they tried to boil all the eggs using the microwave oven (may be, first time in history)! And they succeeded to boil the eggs!

Now they have n eggs and a bowl. They put some eggs in the bowl with some water. And after that they put the bowl into the oven to boil the eggs. It's risky to put more thanP eggs in the bowl and the bowl can carry at most Q gm of eggs. It takes 12 minutes to boil a bowl of eggs. Now you are given the weight of the eggs in gm, and the trouble-makers have exactly 12 minutes in their hand. You have to find the maximum number of eggs they can boil without taking any risk.

UVA 10427 Naughty Sleepy Boys Solution

Problem Statement

Hasan and Tanveer are two naughty boys of the class. They spent most of their class time playing `Tic Tac Toe' whenever they get a chance to sit in back bench. But their teacher doesn't think that playing cross and naught is a way of making a class enjoyable. So, whenever she sees them playing she brings them to the front seat and makes them hear what she says. And you know listening to the teacher is not as enjoyable as playing `Tic Tac Toe'. So, within a couple of minutes, their eyes become dizzy and they fall into sleep resting their heads on the table. The teacher notices that and exclaims, ``You two naughty boys! Come over here.'' and she gives them some problem to solve which is lengthy and cumbersome. They try all the time not to get caught by the teacher while playing, or, for the least, not to get sleepy. But, pity for them, they hardly escapes the eagle eye of the teacher. Now, they are again caught red handed, brought to front bench, and as you know the usual case, they become sleepy. (poor Hasan and Tanveer! Couldn't the teacher be a little bit sympathetic to them?) This time the teacher is very angry and gives them a problem which is really too much for them. She asks them if she writes down the numbers from 1 to 1000 one after another what will be the 1000-th digit. You see what a tough problem for two little boys. Alam and Dalim start thinking that if they write down all the numbers like 1234567891011121314 ... ... it will take many hours for them. Moreover, the answer will possibly be incorrect because they can easily lose track of the numbers written. So, they are trying to find out a way to fool the teacher with the right answer. Can you find a way out for them?

UVA 10282 Babelfish Solution

Problem Type : Data Structure(STL-<map>) 
Problem Difficulty : Easy.

You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.

Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters. Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".

UVA 11111 Generalized Matrioshkas Solution

Problem Type :STL stack
Problem Difficulty : Easy
Problem Statement 

Vladimir worked for years making matrioshkas, those nesting dolls that certainly represent truly Russian craft. A matrioshka is a doll that may be opened in two halves, so that one finds another doll inside. Then this doll may be opened to find another one inside it. This can be repeated several times, till a final doll -that cannot be opened- is reached.

Recently, Vladimir realized that the idea of nesting dolls might be generalized to nesting toys. Indeed, he has designed toys that contain toys but in a more general sense. One of these toys may be opened in two halves and it may have more than one toy inside it. That is the new feature that Vladimir wants to introduce in his new line of toys.