SPOJ 12323. Minimum Knight Moves!!!

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

 There are lots of ways to solve this, BFS recursion, DFS dynamic. I suggest using thee BFS (If you need more info on BFS go here) approach, it is simpler to understand but harder to implement. Just keep a queue and push the coordinates of the first cell to it, every time you take out an element check all of the 8 neighbors that cell has and add them to the queue , also don't forget to mark all the visited cells so that you won't have to visit them again and again.Check out the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1419. A Game with Numbers

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

This problem is a very interesting one. For solving the tasks like this we need to determine what actually means " the best strategy". So here is what I am telling you, if there is one digit present on the board the winner is the first player for sure, because he will just subtract that digit fro itself and get 0. If the current number is 10 and it is now the turn of the second player the first player would still win right? So if we want to win we need to make a situation where the number 10 will be on the board and it will be the second player's turn,  consider the number 11,12,13,14,15,16,17,18,19 in all of those cases the first player would take out the last digit leaving the number 10 to the second player which is a complete defeat. The same goes for every number, to conclude the best strategy is to subtract the last digit from the number so that we can leave a number which is divisible by 10 to the other player and when he makes a move (he can't turn the number divisible by 10 into another number divisible by 10 because the maximum number ho might be able to subtract is 9) and we will do it again and again until he will be down to the number 10 which is a lose. And of course it is clear that if we have a number divisible by 10 from the beginning that means that we will lose it.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1841. Prime Path

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

   We will solve this with BFS( if you need some more info about BFS go here). First of all we need to find all the prime numbers up to 10000 we can do this easily with the sieve of Eratostenes( for more info about the sieve of Eratostenes go here). We will keep a queue where we will add the number which we have already created , the numbers are always 4 digit which makes our job easier. Now we need to replace all the digits with a different digit from 0 to 9 (be careful while replacing the first digit you might end up replacing the first digit with 0 :) ). Every time when we take out the current number from our queue we need to separate his 4 digits and then keep replacing and combing the digits back to form other numbers, then with the help of the found prime numbers we can check if the number is prime or not, and also don't forget to mark every number you get so that your program won't process the same numbers all over again. Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3934. Recaman’s Sequence

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

This task can be solved easily with the help of C++ STL map (for more info about using map go here). The problem could have been done easier if there wasn't the requirement for the numbers being distinct we could have solved it easily but we need to keep the numbers distinct, this is where C++ STL map template helps us, in every step when we are calculating the current element we need to push it in the map and mark it as true. It is impossible to do with the old fashioned method, keeping a big boolean array and mark every number in it because the numbers are very big no computer would be able to hold an array of elements that big.

       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 1710. Two Ends

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

   For solving this task have a look at this tutorial where you will find the full explanation and also the source code.

       DOWNLOAD THE FULL SOURCE CODE

game 1: 2 players second player takes the maximum of 2 ends

The Problem

  

   We have a line of things to take. Each thing has a value , 2 players are playing each of them is taking either the first element or the last , we are the first one, the second player takes the maximum of the first and last. How many points we can score if we play the best way?

Solution

   We will solve this using the dynamic programming. We have an array A[N][N] where A[i][j] shows the answer for a segment of the given items from i to j. Suppose the name of the given array is a. So initially A[i][i]=a[i] because form i to i there is only one element and we will take that and end the game. Then, every A[i][i+1] equals to max(a[i], and a[i+1]) because when there are 2 elements we would rather take the biggest and then the second one will take the last and the game will end. Now, suppose we have an answer for A[i][j] and we want to find A[i][j+1] in other words when we have already found for a segment from i to j now when the j+1th element is added what will the answer be? When the new element a[j+1] is added we have 2 options

1. Take the new added element and then the second player will take the biggest from a[i] and a[j] and we will have to play our best for either for a segment i+1 to j or for a segment i to j-1 both we have calculated previously.

2. We can take the i the element and then the second player will take the bigger from a[i+1] and a[j+1] and then like in the previous option we will add already calculated answer.

There is a task on SPOJ which requires the knowledge of this, you might want to try this and here is  the full source code.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1798. Assistance Required

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

 I suggest solving this task with precomputation. We can write a simple solution which can find the numbers for us and write those numbers in am output file in the way so that we can use them in our source file. Here is my solution with C++ with the process of counting the numbers and also the main source code.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1027. Fool The Police

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

This task is an exact duplicate of the task FISHER
http://www.spoj.com/problems/FISHER/
If you want to see the explanation and the solution go here where you will find the solution and explanation for FISHER and the full source code.

       DOWNLOAD THE FULL SOURCE CODE 

SPOJ 101. Fishmonger

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

 This task is possible to solve with both dynamic and recursive approach. Here I will present you the recursive one. We can have an obvious DFS(you can find more info about DFS here approach, start with the 1st and take every single path, I am not sure whether the simple DG We can use some optimizations to reduce the time. Our DFS should have 3 parameters: N,M,T. N shows the node we are currently in , T shows the time it took us to reach the current node, and M shows the money we paid so far. Here are some optimizations you should do. We also have 2 parameters ansT and ansM which show the answer ansT stands for time and ansM stands for money.
1. Marking the node we already visited, (of course don't forget to unmark it after the recursive call).  
2. If the current money we have already paid is bigger then the answer we have got previously then here is no need in continuing our recursion because we are not going to get a better answer.
3. If the time which we have spent is greater then the given maximum time we need to break our recursion immediately.
 Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE