SPOH 7405. Delicious Pancakes (PANCAKES)

http://www.spoj.com/problems/PANCAKES/

  This is a very good implementation task where the implementation is not very hard but we need to be extra careful while doing it. First of all there is a case where the needed ingredients are more than the ones we have, in that case the answer is 1 0 which means by taking the first recipe we weren't able to cook any pancakes. Then , for doing the calculations I recommend avoiding floats do it with integers, Initially while reading the input data increase the given ingredients which have have 10 times so that when it comes to dividing the ingredients on one another for finding the number of pancakes the problem with that 10 will be solved. Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

1706. Queens, Knights and Pawns

http://www.spoj.com/problems/QKP/

 This task is a good task of implementation, there is not much to explain here you need to keep an array fill the given figures and then loop over the array, whenever you find a figure in there you need to check all the cells that figure can attack, for knight its simple you need to check only 8 cells , for the queen I suggest writing a recursive function which will start from a certain cell and move in a certain direction. Here is how it will look like
void rec( int x, int y, int px, int py)
where px and py show the number which we after being added to x and y will give you the position of the next cell for example px=1 and py=1 will lead you to south east. Check the source code for a better understanding

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 4452. Simple Arithmetics II

http://www.spoj.com/problems/ARITH2/

This is another great implementation task. There is not much to say but I will try to give a few tips. First of all I suggest finding the numbers first and storing them somewhere then proceed to the operations. Here is how we do that, we loop over the string, whenever we see a digit we make another loop until we see the end of that number, then we turn the found area into an integer and store it somewhere. After making those steps no its time to loop over the string again this time looking for the arithmetic operations. Check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 902. Hangover

Here is the problem statement
http://www.spoj.com/problems/HANGOVER/

 Just because the constraints are 5.2>N>0.02 this task can be solved with a simplem implementation. Just loop from 2 and add to our current legth the 1/i (i is our current loop value)/ If we reached the value print the index and exit.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 2149. Baised Standings

Here is the problem statement
http://www.spoj.com/problems/BAISED/

Th task is a simple calculation. We need to get only the numbers. (We can ignore the names, they are just made to ruin our code and fill them with strings :D ) . Now we get all the numbers and sort them. And then calculate the difference between the I th element and I  and add it to our answer. This way the so called "badnes" will be minimal.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 96. Shopping

Here is the problem statement
http://www.spoj.com/problems/SHOP/

I suggest a way which is not fast enough( you won't be the first in the best solutions field :) ) but works great. This is done by a simple BFS ( you can find information about BFS here) but in a different way (without queue). Initially we keep an array which we will call ans (the array of answers) and the field ans[x][y] will show the minimum cost of getting to the point (x,y) . Initially all the elements are equal to infinity ( to a very larg number which we will call INF). We give our start point the value of 0. Then we loop over our array N*M times ( this is the worst case) and every time we loop we check if the current point we are on is not equal to INF we check its neighbours and update the value if necessary. Then we output the value of ans[x2][y2] where (x2,y2) is the destination point).

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 13043. The Mirror of Galadriel

Here is the problem statement.
http://www.spoj.com/problems/AMR12D/

The problem is very simple if observed correctly. You only need to check if the given string is palindrome or not. Here is why. The palindrome is a string which if reversed will be the same string. Let's try to prove the reversed point. If the string contains all the reversed substrings of his own that eans that he is a palindrome. which is very easy to prove by just taking the string himself as a substring :D . The reversed of himself can exist in himself if he reads from the left and right the same way .

       DOWNLOAD THE FREE SOURCE CODE 

SPOJ 10232. Distinct Primes

This task can be done using a simple implementation . Just find all the primes, for numbers buy multiplying 3 primes and then for each numbed found , multpily it again with the same primes we used from the beginning, and then when we got a list, we can sort it and we are ready to read the input and output the asnwer right away. But first for doing this we need to make sure that for n=1000 the number needed won't be too great. 

The primes are 2,3,5,7,11,13,17,19,23,29,31,37.41 Our initial numebrs are going to be made by multiplying 3 different primes. It is not hard to notice that the 1000 th number is not going to be formed with a greater number then 41. So we can be sure that a simple  brute force solution will pas the time limit easily.

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 10565. Alice Sieve

Just take a piece of paper and a pan and try to do that on a few examples. Its is not hard to notice that for even Ns the answer is N/2 and for odd Ns the answer is (N+1)/2.

TRICK FOR  SOLVING THIS TYPE OF TASKS

If the task has a very little input (one or two numbers) and has a little output and the constraints are very high, it is simple to understand that there is a special trick for that,we need to input the numbers and by using a formulas or some relationsships output the result right away. 

 The trick is the following.Write a simple bruto force solution and output the asnwer for N from 1 to 100 or 1000 ( choose the amount appropriately) and they you will be able to notice the special trick.

    DOWNLOAD THE FULL SOURCE CODE

  

SPOJ 2148. Candy III

This is the problem statement

http://www.spoj.com/problems/CANDY3/

This problem is increadibly easy. You may think that this is a big integer problem (where you have to calculate the sum of numbers using arrays because the numbers won;t fit in the 64 bit integer) but don't worry C++ 's long long (__int64) can hold the answer. We need to calculate the sum of all elements and check if it is divisible on N or no. I am pretty sure that the input can be kept in 64 bit integer and we don't need to calculate the actual sum of numbers. Instead we can calculate the sum of remainders which we get when dividing the current element of N.If the final number is divisible on N output "YES" else output "NO"

   

   

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 2123. CANDY I

Here is the problem statement
http://www.spoj.com/problems/CANDY/

The answer is -1 when the sum of all candies is not divisible on N. We know that every pack must contain sum/N which means that we need to loop over every pack and check for the difference between sum/N and the current number of candies in the current pack. But after this we will get answer 2 times more because of this . Consider a simple test case of N=2 and a[1]=1 and a[2]=7
so every pack must contain (1+7)/2 =4  our program will calculate the number of candies which will be removed from the second pack and added to the first and also the number of candies that the 1 st pack must get which gives a total of answer which is 2 times more than the actual answer,

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 4300 Rectangles

Here is the problem statement
http://www.spoj.com/problems/AE00/

Note that the constraints are N<=10000 which means that N^2 probably won't pass. The task ask us to find the number of rectangles which we can build using up to N cubes. I mentioned "up to" because we can have some cubes unused. We can describe the task i a different way.Find the number of distinct pairs i and j the multiplication of which is less or equal than N. Now we can loop through N elements in a double loop and check if the multiplication is less or equal than N and also check if we have already seen that answer. The clever way of doing this is using 2 loops in this way.
for( i=1;i<=N;i++)
   for(j=1;j<=N/i;j++)
(because we know that if we have the first side of our rectangle the second side must be less than N/side1.

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 10239 Between the Mountains

Here is the problem statement
http://www.spoj.com/problems/ACPC11B/

This task is a very simple task. The constraints are enough to write a simple brute force solution and get accepted. Just loop over both of arrays , calculate the distance between every pair and update the answer.

   DOWNLOAD THE FULL SOURCE CODE 

SPOJ 7975. Tri Graphs

Here is the problem statement
http://www.spoj.com/problems/ACPC10D/

  This task can be solved with creating a graph out of our array and use BFS to solve it but there is a better way. We can use dynamic programming to solve this. Create an 2 dimensional array. Let's name that array b.
b[i][j] will show the minimum number of points we will have to collect in order to reach i-th row and j-th column. We now that b[1][1]=a[1][1]. Now we can just loop over our input array and for every element a[i][j] we update the value of b[i+1][j],b[i+1][j+1],b[i][j+1]. (All the values of array b equal to infinty from the beginning).

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 42. Adding Reversed Numbers

Here is the problem statement
http://www.spoj.com/problems/ADDREV/

This task is a simple implementation task. Juts keep the number in an array digit by digit so that you can calculate the reversed number easily. The numbers are small so this means that we won't have to do the long number sum.

DOWNLOAD THE FULL SOURCE CODE

SPOJ 10676. 0110SS

Here is the problem statement.

http://www.spoj.com/problems/IWGBS/

For solving this kind of problems we need  to have a bit of noticing skills. Try to calculate the answer for n=1,2,3,4 by hand and you will easily notice the drill in here.Create a simple tree which will show the answer.

The tree shows the ways of creating numbers

When the length is 1 we can have 0 and 1 on our first position. When we are trying to form the sequence of length 2 we need to use the sequences we had already created and add 1 or 0 (if possible) to the end of the sequence. Obviously this is a problem of dynamic programming. Here is the table of answers from 1 to 4

1-2

2-3

3-5

4-8

We can easily notice that a[n]=a[n-1]+a[n-2]

The only problem we have in our task is the problem of constraints. N<=10000 obviously for N=10000 our answer will not fit in int64 I can say more the answer for N=10000 s 2009 digits long. We need to implement the long arithmetics. You can find information about that here.

DOWNLOAD THE FULL SOURCE CODE

SPOJ 7974. What’s Next

This is the problem statement
http://www.spoj.com/problems/ACPC10A/

The task itself is a very easy task. A very simple implementation just check if the difference between the first two equals to the difference between the second two elements. There is a little part to take care of. when one element equals to 0 we might end up dividing on 0 when we are checking if the progression is geometrical. Use this pseudocode

if(a2-a1==a3-a2)
print "arithemitc"
else
print "gemoetric"
Don't check for geometric progression

       FULL SOURCE CODE

SPOJ 8351. KOSARK

This task is a simple implementation task. You only need to keep track of the events and check which team is on lead and add you answer accordingly. The only challenge here might be the input and the output because we are getting the input in MM:SS format and we should output in this format as well. In C++ the input will be easy to read. cin>>int>>int>>char>>int; will give us what we need. If we read the number in format 02 C++ will understand it as 2 and 00 as 0. The other part is very easy. Just keep the current time and check if at the current event one team has more points than the other add to the answer the time of event minus current time.

DOWNLOAD THE FULL SOURCE CODE