ACM 1219. Symbolic Sequence

  Here is a stupid but acceptable solution for you.

  Output a random letter 1000000 times and stop the program. It has a high success probability. If you failed from the first try ( which you probably won't) , try one more time.

       FULL SOURCE CODE

ACM 1731. Dill / Укроп

  If all of the pairs from the second pile have a difference which can't be covered by any difference between any pair from the first pile, then we found a solution. If we take the first pile consisting of all elements from 1 to n and the second pile: a set of elements where each differs from the previous one by (n+1) starting from a number bigger than n, all the requirements will be met.

       FULL SOURCE CODE

ACM 1510. Order / Порядок

 This task is very easy to solve with the help of map data structure. Make a map of 2 integer on integer and after reading number increase the corresponding map[X] by 1. Then loop over all the elements and check for the index which has the maximum value.

       FULL SOURCE CODE

ACM 1296. Hyperjump / Гиперпереход

  The negative numbers make us think "what should I do if on the way of collecting the sum I saw a negative number, should I collect it and continue or should I stop collecting right there?". Here is the answer, if after collecting the negative number your current sum is more than 0 you should keep collecting because you might get a better result (don't forget to update the maximum value of the final answer every time).

       FULL SOURCE CODE

ACM 1180. Stone Game / Игра с камушками

  Here is the one crucial thing we need to notice and understand,  that if the starting position is divisible by 3 then the position is a losing position for the starter, in all other cases the starter can win. Here is how it happens. All the powers of two have remainders 1 and 2 when divided on 3 obviously. The optimal strategy would be the following : "At every step leave your opponent in a divisible by 3 position". The smallest non negative number divisible by 3 is 0 and if the starter get's to 0 that would only mean that the second player picked the last stones left. The steps are as follow. If you are in a divisible by 3 position after, you make a move for sure your opponent will not be in a position divisible by 3 (it will have a remainder of 1 or 2 when divided on 3) and after that he can take some number of stones which will leave you in a divisible by 3 position again, this process will continue until he picks the last 1 or last 2 stones. When we begin on a non divisble by 3 position we just need to make the move of our opponent and leave him in a divisible by 3 position which will get him a defeat.

       FULL SOURCE CODE

ACM 1404. Easy to Hack! / Легко взломать!

 We need to implement the reverse process in order to solve this task, Suppose we have the array of new characters where each character is written as a number. For every sum[i] the real char in that spot will be sum[i]-sum[i-1] .We just need to loop over and recover the initial string, every s[i]=a[i]-a[i-1], and in the end s[0]=s[0]-5. Also, during this process we need to check for the subtraction not get lower than 0, in that case just add 26 to the negative result to turn it into positive.

  

        FULL SOURCE CODE

 

ACM 1161. Stripies

We need to consider a little thing here, that the lost will be greater if we square root the biggest ones. We just need to get the biggest 2 numbers, calculate the new number and get the new 2 biggest from the new pile until there is only one left. 

       FULL SOURCE CODE

ACM 1786. Sandro's Biography / Биография Сандро

Here is a simple solution to this task. There is an interval with the length  6 (the length of the word "Sandro" which we need to turn into "Sandro" and it is easy to calculate the amount we need to pay, if the corresponding chars are equal than no money, if they are equal have different cases then 5 , if they have the same case but are not equal than it is still 5 and when they have different cases and are not equal then the money is 10 for that single char. We can consider all the intervals, calculate the amount for each interval and take the minimum. 

       FULL SOURCE CODE

ACM 1796. Amusement Park / Парк аттракционов

   First of all, if buying X tickets we do not have enough money then for buying more than X tickets we won't have enough money too. Secondly, If after buying X tickets , we can buy some more tickets with the remaining money, then after buying some number of tickets less than X we will still have enough money to buy more tickets. All of these means that the answer is an interval of numbers. Obviously the upper bound is the total number of money divided on the cost of the ticket. If we had one note missing than it wouldn't be enough so if we consider the possibility of all the possible number of tickets after considering each of the 6 notes lost and take the maximum of those numbers we will the lower bound of our interval.

       FULL SOURCE CODE

ACM 1048. Superlong Sums / Сверхдлинные суммы

 For handling large numbers (so-called bigInt s ) we need to operate with them digit by digit like we used to do from our early grades. Sum up the last digits, if the result is greater than 9 then keep the "1 in mind" and write down 9 and after processing the next pair of digits add the 1 (if kept in mind from the previous step) and do the same for all the digits and save the result up in an array. Also you should use fast input/ output methods to makre sure that your code gets accepted.

       FULL SOURCE CODE

ACM 1021. Sacrament of the Sum / Таинство суммы

  We will use binary search for this one. Suppose our first array (called A) is sorted in ascending order. For a number x, if x+A[i] is greater than 10000 we can say for sure that for all I>i, x+A[I] will > 10000 which means for every B[i] we need to take initial segment 1..n check for the middle element and see if the sum of the element from B and the middle element of A is greater than 10000 then we should check for the segment 1...mid else mid...n. Check the source code for a better understanding.

       FULL SOURCE CODE

ACM 1026. Questions and Answers / Вопросы и ответы

 We only need to input the numbers, sort them out and output every A[i] for query i.

       FULL SOURCE CODE

ACM 1194. Handshakes / Рукопожатия

  This task is actually very funny. If we have initial number of N and everyone is going to separate until there is one left or a couple left which means that all the possible handshakes are going to take place, which means if there are N people there will be ((N-1)*N)/2 handshakes (sum of numbers form 1 to N-1) but considering that there are couples which don't give handshakes to one another which means we should subtract the number of couples from our answer.

       FULL SOURCE CODE

ACM 1935. Tears of Drowned / Слёзы утопленников

  Here is what we need to understand, If there are 2 neighboring skins, then between there should be max(a[i],a[i+1]). Now, considering A[0] and A[N+1] equal to 0 it is the sum of maximums of all pairs I and I+1. Also for obtaining the smallest number we need to sort them out.

       FULL SOURCE CODE

ACM 1224. Spiral / Спираль

 After examining the task on some samples we can understand the following, if initially we are facing right, then until the next time we will face right is the time when we will be considering a board of Size N-2,M-2 and on this process we did 4 turns. So, the answer would be , generally speaking (N/2)*4. But here is one more thing, when we are down to 1 then we are not making any turns if N gets 1, but if N gets 1 we are making only one more turn , which means that if (N<=M) answer is 2*N-2 otherwise it is 2*M-2+1 which is 2*M-1.

       FULL SOURCE CODE 

ACM 1131. Copying / Копирование

  First of all the rate of copying is 1, then after the next move the rate will be 2*1, and then 2*2*1, until the rate reaches K. If the rate is constant then the answer is N/K and +1 if N is not fully divisible on K. You need to implement the process of the rate growth and decrease the number of remaining computers, and then add N/K to the final answer ( +1 if N is not fully divisible on K).

       FULL SOURCE CODE

ACM 2005. Taxi for Programmers / Такси для программистов

  The first point is always 1 and the last point is always 5. Then we need to take all the permutations of numbers (2,3,4) where the 3rd number is not on the last place and check for the best answer.

       FULL SOURCE CODE

ACM 1146. Maximum Sum

  Here is how we will solve it, first of all we need a helping array of already calculated sums, let's call it sum where sum[i][j] shows the sum of elements of the i-th row from 1 to j. Now we will fix some interval  from 1 to N for the columns, and another interval from 1 to N to all the rows. In other words, if we have an interval of [C1,C2] for columns and [R1,R2] for rows then we need to calculate the sum of a square which has top left coordinates of [R1,C1] and bottom right coordinates [R2,C2]. In the process update the value of the final answer if necessary.

       FULL SOURCE CODE

ACM 1712. Cipher Grille / Шифровальная решётка

Obviously we need to output all the characters where 'X' lies in the corresponding cell, and rotate the field. We need to those steps 4 times, but the hardest part here is rotation.
Have a look at the following 4x4 table.
1234
5678
90ab
cdef
If we rotate it we get
c951
d062
ea73
fb84

As you can see, every Ith row became N-i+1 the column ( if numerate from 1). or A[i][j]=A*[j][N-i+1];

       FULL SOURCE CODE

ACM 2011. Long Statement / Длинное условие

First of all sort all the numbers, then our goal is to check the number of different permutations , if that numbers exceeds 5 then the answer is Yes. If you are using C++ you can easily handle everything with the next_permutation function in the library "algorithm" , if not then read about getting the next permutation of a sequence here.

       FULL SOURCE CODE 

ACM 1502. Domino Dots / Точки домино

  If we sort the domino figures by one side we will get the following set, 0/0 0/1 0/2...... 0/N, 1/1 ,1/2,....., N-1/N-1,  N-1/N,  N/N
so if the first number is M then the other number can be from M to N. The sum of numbers from 1 to K equals K*(K+1)/2. For calculating sum of numbers from M to N we need to take N*(N+1)/2 - (M-1)*M/2.  So for all the dominoes which have the first number of M we will have answer of N*(N+1)/2 - (M-1)*M/2 + (N-M+1)*M.

       FULL SOURCE CODE

ACM 1073. Square Country / Квадратная страна

 We will keep an array of answers DP[N] where DP[i] shows the answer for i. We also would like to keep a list of squares up to 60000. The algorithm pretty much looks like the algorithm of the knapsack problem except here we keep the number of elements. Initially all the numbers equal to infinity (to a very big number) now starting form 0, if we are on a current element I then we need to check for all the I+ squares and check if we can update the answers, in other words DP[I+squares]=min(DP[i+square], DP[i]+1);

       FULL SOURCE CODE 

ACM 2002. Test Task / Тестовое задание

   All you need to do, is to implement the registration process carefully, if you are using C++ I recommend using C++ STL map which will help you a lot in this case. check the source code for a good understanding.

       FULL SOURCE CODE

ACM 1792. Hamming Code / Код Хэмминга

 The problem just needs basic implementation, write a function that checks if the current sequence is correct, then switch every single element and call the function each time to see is the new sequence correct or not. When found a correct sequence, output and exit.

       FULL SOURCE CODE

ACM 1457. Heating Main / Теплотрасса

 The task wants us to calculate the mean of all the numbers SUM/N.

       FULL SOURCE CODE

SPOJ 27. Sorting Bank Accounts (SBANK)

  Here is what simple things you can do to handle everything easily. Input the entire line as one string, obviously if one of those string is smaller than the other one it means that it should come earlier. Now, you can just sort the entire array using C++ sort which works very then easily check for the copies by comparing each one to the next and output the answer.

       FULL SOURCE CODE

SPOJ 2716. Maximal Quadrilateral Area (QUADAREA)

The area of the cyclic quadrilateral is sqrt ( (m-a)*(m-b)*(m-c)*(m-d)) where m is the half of the sum of all the sides. The rest is clear, input and output using the formula.

       FULL SOURCE CODE

SPOJ 297. Aggressive cows (AGGRCOW)

  First of all we need to sort all the given stall positions. Then we can do a very good trick, we can try finding the solution from the solution set. Take the maximum and minimum number which can be the answer. We can write a function which checks if the current number satisfies the task requirements in O(n) time. Then we can take the maximum and minimum possible answer, and with binary search get to the final answer. Check for the middle, if the middle answer is OK then we can check the middle of that middle and the maximum value. And so on, until we are down to 2 or 1 answers which we can check manually.

       FULL SOURCE CODE

SPOJ 302. Count on Cantor (CANTON)

 First we need to figure out the pattern by which the numbers are numerated. This is the pattern but it is kind of reversed, have a look.
http://en.wikipedia.org/wiki/File:Diagonal_argument.svg

The first turn is right then diagonally down, and then when reached the edge it goes down by one and then diagonally up, and the same thing again. Now we need to correctly implement it, you can just make a function which goes from one number to another by a specified direction and changes it whenever necessary, check the source code for a good understanding.

       FULL SOURCE CODE

SPOJ 328. Bishops (BISHOPS)

  If you use some paper and pen you will easily find out that the answer is 2*N-2 but another harder question still remains regarding the implementation. N<=10^100 which calls the big int implementation. If you are not using Java or Python or some other language where bigInt is ready for use here are some tips for using it and the source code provided here has it's own implementation of it. So we need to keep an array of digits and recall the memories of multiplication from our early grades where we were writing one under another and multiplying digit by digit. Check the source code for a good understanding. Also you should handle the cases 0 and 1 separately.

       FULL SOURCE CODE

SPOJ 5132. Hello Kitty (HELLOKIT)

 The constraints are very low which give us a good opportunity to get the task accepted with a simple brute force. Simple build the first string and every time remove the first letter and add it from the back and you will get the next string. Repeat the process until the new string gets equal to the initial string.

       FULL SOURCE CODE

SPOJ 5676. STONE GAME (RESN04)

Thing we have to notice here is that the game can't have different outcomes if played different way. Consider the pile i , which has A[i] elements, how many times a move can took place for pile i, as long as there are full i-s in A[i] which means A[i]/i times, we can calculate the total number of moves possible for all the piles and in the end if it is an odd number then Alice will win.

       FULL SOURCE CODE

SPOJ 4301. Tables

It is obvious that the bigger the capacity of the boxes the less amount of boxes we will need to get enough nails. So we need to sort them out and start taking from the biggest until we get enough.

       FULL SOURCE CODE

ACM 2023. Donald is a postman / Дональд-почтальон

Basic implementation. We need to somehow keep the corresponding number of shelf of every name so that we can access it with the given names, the C++ map can help a lot here. Also one thing, for making a little easier you can easily notice that there are no 2 names that start with the same letter but belong to different shelfs which means that we can only consider the first letter of the names.

       FULL SOURCE CODE

ACM 1563. Bayan / Баяны

Yet another task which is being handled easily with C++ map because with map we can easily keep the names which we have already encountered before, and if we did increment the answer by 1.

       FULL SOURCE CODE

ACM 2012. About Grisha N./ Про Гришу Н.

 The simple calculation shows that in 4 hours he can manage to solve 240/45 = 5 full tasks which means that if he solves more than 6 before this he will make it.

        FULL SOURCE CODE

SPOJ 206. Bitmap

 A simple BFS but we need to be a little clever. Remember how we were doing it? we were starting form a certain node and our wave was passing over all the nodes and the node was the closest, and there is no other path which is shorter than the one we found on the current way, In our case instead of starting from each node all over again we can start from all the '1' nodes which will generate us the same answer. for more details look at the source code/

       FULL SOURCE CODE

ACM 1723. Sandro's Book / Книга Сандро

   This task might have been difficult if we had to find the most powerful spell which also has the maximum length. Suppose our spell is a string S , if the given string contains the string S N times that means that any letter of S will be there at least N times. So by finding the letter which appears the most is one of the maximum spells.

       FULL SOURCE CODE

ACM 1617. Flat Spots / Ползуны

   Keep the track of the amount of each number inputed and then divide to 4 every amount individually and add to the final answer.

       FULL SOURCE CODE

ACM 1837. Isenbaev's Number / Число Исенбаева

 The constraints are small so we can go with a brute forces solution but it requires a lot of implementation. First of all I recommend using C++ . Initially all the names have a position of infinity. In the process of reading we need to find the team of the main character and mark all of his teammates with the number 2 (we will start numeration form 1 and 0 will be considered as undefined). Then n times, loop over the list and each time give each teammate a number if at least on of it's teammate has been defined, and update the number of every member if possible.

       FULL SOURCE CODE

ACM 1196. History Exam / Экзамен по истории

 C++ map can help us here a lot, just keep a map where A[i] will be true if the number i exist in the professor's list. Then input the student's answers and increment the final answer by 1 if the current number of the student has a value of true  If you have problems using map you need to implement binary search which takes logN time to check for the existence of an element in a sorted list. You can find more info about Binary Search here.

       FULL SOURCE CODE

ACM 1636. Penalty Time / Штрафное время

    The only thing which we need to check is whether the total time of the first team + all the unsuccessful tries *20 exceed the second team's time or not. If they exceed it means that they cheated.

       FULL SOURCE CODE 

ACM 1496. Spammer / Спамер

C++ map handles this problem perfectly. Keep a map of type<string,int> and increase the corresponding string element in this map by 1 after reading each name. Then loop over all the elements of the map and check if the current one has a value greater than 2 output that word and continue.

       FULL SOURCE CODE

ACM 1607. Taxi / Такси

  We can assume that the answer is the current deal, initially it is the number suggested by the passenger, then the answer becomes the price of the taxi driver, then if the passenger can reduce the price then it will be the new answer, and then the taxi driver, We just need ot implement this process to get the final answer, also if the reduction or increase can't happen we just agree with the other price. There is one little tricky case to handle, if initially the offer of the passenger is higher then the offer of the driver then the answer is the offer of the passenger.

       FULL SOURCE CODE 

ACM 1545. Hieroglyphs / Иероглифы

  The task wants us to find all the words which start with a given letter. Input the data and save in an array then loop over it and check for the first letter of the current word if it is the same as the given letter then output that word.

       FULL SOURCE CODE

ACM 1991. The battle near the swamp / Битва у болота

If the number of bullets in the Ith pack is more than the total number of monsters K than there will be K-A[i] bullets left , otherwise there will be A[i]-K survivors. The rest is just input, sum and output.

       FULL SOURCE CODE

ACM 1925. British Scientists Save the World / О заслуге британских учёных

  Just loop over both columns and calculate the sum of each, then add the K number and then check if the sum of the first column is greater or equal then the sum of the left column plus the additional (N+1) 2s which we needed to consider initially.

       FULL SOURCE CODE

ACM 1349. Farm / Ферма

 This task is very easy if you know the Fermat's Last Theorem, it states that if we have an expression a^n+b^n=c^n and if n is greater than 2 than there is no triple of positive integers a b c that satisfies this equation. In case of 1 the answer is 1 2 3 in case of 2 it is any Pythagorean triple such as 3 4 5 and in all other cases the answer is -1.

       FULL SOURCE CODE

ACM 1243. Divorce of the Seven Dwarfs / Развод семи гномов

 The only problem here is checking of the divisibility part. How do we check if the number if divisible by 7 or not? Here is how, we take the numbers 1 3 2 6 4 5 and loop over the number from the other end and add the current digit multiplied by the current number in the given sequence. If we divide the number to 7 and take the remainder it will give the same answer as the remainder of the initial number divided by 7 and taken the remainder.

       FULL SOURCE CODE

ACM 1110. Power / Степень

  The constraints are small enough so I recommend pure brute force. Here is one thing to consider. If a number X=M*K+R (we are considering the divisibility on M and R is the remainder). So, if we multiply X with another X we will have X=M*M*K*K +2*R*m*K + R*R  all the elements are divisible by M except for the last one which means that taking the remainder after calculating the power or in the process of calculating the power will not change the final answer. This is important because the numbers might too big to fit into integer type so you need to take a remainder after every step.

       FULL SOURCE CODE

       

ACM 1893. A380

   There are just a bunch of cases to handle 3 different packs of if statements and each pack with 3 conditions to check.

        FULL SOURCE CODE

ACM 1327. Fuses / Предохранители

The task statement might be a little confusing , here is what it asks for, there is a machine which has a fuse and after each time it is launched the fuse dies, where the next day the machine is not working because the fuse is being replaced. So on the first day the machine works, then on the second day the fuse is dead and it is being replaced, on the third day the machine works again with the new fuse, and then the fuse dies and on the forth day the new fuse will be placed and so on, => on the odd number of days the machine works and on the even numbers the machine doesn't work and we need to calculate how many days the machine will work in the interval [A,B].

       FULL SOURCE CODE

ACM 1100. Final Standings / Таблица результатов

The bubble sort works this way, if the current number which we are considering is smaller than the next one than we swap the places of those 2. We can look at this from another side, If we have a number which "is not in his position" then we should move it up until he meets someone which is more or equal than the current number. We can conclude that the order of the equal numbers will be the same after sorting. We should notice that the number which needs to be sorted can be from 0 to 100 which means that we can check for every number individually starting from 100 and output the corresponding number in the given order in the input/

       FULL SOURCE CODE

ACM 1876. Centipede's Morning / Утро сороконожки

 There are 2 cases which can be "the worst", the first case if as follows, he gets out only the right shoes until all the right shoes are over and then he will take the left shoes and finish which gived total of 2*b+40 moves. Or he might take out 39 right shoes in the beginning , wear them , then take all the left shoes and then take the last right shoe and finish which will give a total of 2*39+40+(a-40)*2+1=2*a+39

       FULL SOURCE CODE

ACM 1881. Long problem statement / Длинное условие задачи

We need to implement the process carefully. We will keep variables representing the current page, line and how many characters are left on the current line. Then we need to input the words and check if there is enough space left for that word then we add it to the current line otherwise we start a new line, by starting a new line we need to keep the track of the page because if the new line is greater than the number of lines on the page then we need to move to a new page.

       FULL SOURCE CODE

ACM 1585. Penguins / Пингвины

 Keep 3 variables which will represent the number of each kind, then process the input, after reading each string check which kind it is and increase the corresponding number by 1 and then output the final answer.

       FULL SOURCE CODE

ACM 1263. Elections / Выборы

let us have an array vote[10000] where vote[I] shows the number of votes received by the candidate I. We fill this array while reading the input and then after that we loop over the numbers from 1 to N and output (vote[I]/m)*100.

       FULL SOURCE CODE

ACM 1225. Flags / Флаги

Let us keep an array of pairs A where A[i].first will show the number of flags that end with a red stripe and A[i].second will show the number of flags that end with a white stripe. We don't need to keep another one for the "blue" case because basically no flag ends with a stripe "blue". So, suppose we have calculated the asnwer up to A[N-1] so what will it be for A[N], if the flags of length N-1 ended with a red stripe then there will be that much flags of length N ending with a white stripe (we can add white to red) and also if N-2 th stripe was red then the N-1th one could have been blue and we could have add another white stripe to those ones. So the final answer will be A[N](white)=A[N-1](red)+a[N-2](red). and A[N](red)=A[N-1](white)+A[N-2](white). The total answer is the sum of those 2.

       FULL SOURCE CODE

ACM 1581. Teamwork / Работа в команде

Keep an element cur which will show the number of elements which equal to the current element, initially it is equal to 1. Then loop over the array, if Ith and I+1 th elements are equal then increase the value of cur by 1 and move on. If they are not equal than add to the answer sequence the pair(cur, A[I]) and turn cur back to 1.

       FULL SOURCE CODE

ACM 1567. SMS-spam / SMS-спам

Just keep the cost of every available character in the way you want and then loop over the given string and calculate the answer.

       FULL SOURCE CODE

ACM 2001. Mathematicians and Berries / Математики и ягоды

Suppose the weight if the first basket is B1 and the weigh of the first man's berries is N. The same for the second one B2 and M. And we have input data a1,b1,a2,b2,a3,b3. If we write down all the equations it will be very clear and easy.

1.N+B1=a1
2.m+B2=b1
3.n+m+B1=a2
4.B2=b2
5.B1=a3
6.n+m+B2=b3
Throw away the 3rd and 6th equations. Out of the other ones we get that
N=a1-B1=a1-a2
and
M=b1-B2=b1-b2

       FULL SOURCE CODE

ACM 1924. Four Imps / Четыре чертёнка

First of all, the result can;t give different remainders divided on 2 no matter how we distribute pluses and minuses. We know that odd numbers are of a form 2*k+1 so no matter we add aor subtract them the result will give an even number => if there is even number of odd numbers from 1 to n than the answer is "black".

       FULL SOURCE CODE

ACM 1639. Chocolate 2 / Шоколад 2

The only thing which we need to see that is for breaking the chocolate down into the pieces of 1x1 we will do the same amount of moves no matter how we cut it. If that number of moves is odd then the first on will cut the last piece and he will win otherwise the second one will win.

       FULL SOURCE CODE

ACM 1910. Titan Ruins: Hidden Entrance / Руины титанов: сокрытый вход

Loop over the numbers from 1 to N-2 and check for the sum of elements A[i],A[i+1],A[i+2] and update the answer if necessary.

       FULL SOURCE CODE

ACM 1880. Psych Up's Eigenvalues / Собственные числа Psych Up

We will use C++ STL map for this one. For more info about map go here.
 No need for arrays ,we keep only one map of type <int,int> where A[I] tells how many times we encountered the number I.  We just input the first two blocks and increment the corresponding map element by 1. Then when we read the third block we input and check if we have faced the current number 2 times with the help our map, if yes then we increment answer by 1.

       FULL SOURCE CODE

ACM 1820. Ural Steaks / Уральские бифштексы

Steaks are 2 sided so we need to consider them as 2n sides which need to be cooked and we have a pan which can hold up to k sides. It will be stupid to leave a spot in k empty if there are some sides left, so basically the answer will be 2n/k rounded up ( we fry full k sides until we are down to some remainder which is smaller than k and also take 2 more minutes to fry the final steaks). But this formula doesn't work when we have 2*n<k initially, In this case the answer is 2 which need sot be handled separately.

       FULL SOURCE CODE 

ACM 1877. Bicycle Codes / Велосипедные коды

For making things easier and more understandable we can just implement the process and check if there will be a day where we will open the lock. On the odd days the first lock is applied and on the even days the second one, it is just easy too loop over all the codes starting from 0 and check for the corresponding lock, if we can open a lock at some point then the answer "YES".

       FULL SOURCE CODE

ACM 1044. Lucky Tickets. Easy!

We will do semi-brute force in here. We will keep an array of sums, where A[i] shows the number of elements which has a sum of it's digit equal to i. In the input we get a number which we will call 2n because it is always even. So we need to calculate the number of elements in which the sum of the first n digits equals to the sum of the second n digits. We need to look over all the tickets of size n ( the total number will be 10^n which is 10^4 on the worst case) and increase the corresponding sum in the array A by 1 in other words, we loop over all the numbers from 000...00 (n times) to 99...99( n times) and calculate the sum of digits suppose it is S, and increment A[S] by 1. Then loop over all the tickets from 00..000 ti 99...99 and calculate every time the sum of digits again (this can be considered as taking the current ticket as the first half and seeing how many other sequences there are that have the same sum of digits) and add the corresponding answer from A[] to our final answer.

       FULL SOURCE CODE

ACM 1014. Product of Digits / Произведение цифр

First we need to find the prime factorization of N. If there is a factor greater than 7 than the answer is -1 for sure. Obviously the less digits our answer has the smaller it will be so if for example we got 2 3s , it is better to save it as one 9 in the answer. The same goes for other digits like 2 ( 3 2s can be kept as 1 8). Our answer will be a sequence of digits, (we will not care for their order until we get all the necessary digits). First of all we need to take 2 3s and push 9 to our answer . We might be down to 1 or 0 3s in the end, and then we have to check that case individually. We need to take triples of 2s and add 8s, in this case we might be down to 3 cases where there is no 2 left of there is one left or there are two 2s left. And then we might need to check for the case of 6 (if we have 1 3 and at least 1 2). For skipping all those unnecessary conditions we can take the number 9, see how many times our N can be divided to 9 and accordingly add the digit 9 to our answer, then the same for 8 then 7 ..... until we finish with 2. If after all those operations our number is still greater than 1 that means that there is a factor which we can't express as one digit. Then when we have gathered all the necessary digit which after being multiplied will give us N, we need to sort them in ascending order and output the answer. NOTE THIS IS A BIG ONE : the case of 0 is tricky. Some people output 0 . It is not correct because the task says that our answer must be a positive integer and 0 is not considered as positive. Some people output -1 which is also wrong because if there is one digit 0 in our answer than the product will give 0, so in case of 0 the answer is 10.

       FULL SOURCE CODE

ACM 1009. K-based Numbers / K-ичные числа

 We need to solve this task using dynamic programming because the brute force will give TLE. So how do we do it? Let us handle the case of N=1 separately, it is obvious that the answer for N=1 will be K. So for the rest, Suppose we have the numbers of length I of the base J. So how many number can we form with the base J and length I+1. The length increased by 1 which means that we need to add one more digit ( digits from 0 ,1,2,...K-1) to the numbers of length I and base J which satisfies the problem demand. So, if the number ended with 0 we can add (K-1) digits from 1 to (K-1) and if the last digit is not 0 than we can add every digit form 0 to K-1. We need to keep an array of pairs A[I][J] where A[I][J]->first  shows the number of numbers on length I of base J which end in a non zero digit and A[I][J]->second shows the number of numbers of length I of base J which end with the digit 0. ==>> A[I][J]->second=A[I-1][J]->first  and A[I][J]->first=(A[I-1][J]->first+A[I-1][J]->second)*(i-1).

       FULL SOURCE CODE  

ACM 1787. Turn for MEGA / Поворот на МЕГУ

 Every minute can pass only k cars, which means after if there were M cars at the Ith minute, then if that number is less or equal than k than all will pass or else the remaining M-k cars will be left to pass on the I+1 th minute. We need to do this on our given array, loop over it from 1 to n and see if the current element is less or equal than k then turn it to 0 and move on, otherwise subtract k and add the remaining number to A[I+1] . The final answer will be held in the element A[n+1]

       FULL SOURCE CODE

ACM 1149. Sinus Dances / Танцы синуса

 There is nothing much to explain here, you just need to implement and get the string as given in the task description carefully. Check the source code for some details and hints on implementation.

       FULL SOURCE CODE

ACM 1493. One Step from Happiness / В одном шаге от счастья

  We can just check for the numbers N-1 and N+1 and output the answer. The checking part is easy, you need to take the last three digits and sum up and then the rest 3 digits and sum up and check for equality. There is a little thing which we need to take care about. The number can have a preceding 0. For handling it, you can input it as string and then digit by digit add to number 1 where in the end you will have a 7 digit number where the digits from 1 to 6 can be 0s because the number will have an unusable digit 1.

       FULL SOURCE CODE

ACM 1785. Lost in Localization / Трудности локализации

 This task is just a bunch of if statements which need to be carefully implemented.

       FULL SOURCE CODE

ACM 1654. Cipher Message / Шифровка

 We will use C++ STL stack for this one. If you are using other language than you should implement stack yourself, stack basically is a sequence which has an option of accepting elements form the beginning and removing elements from the beginning. You can find more info about stack/C++ stack here. We need to keep a stack which will give the answer string. We need to loop over out string and check, if the new element which we are about to add to the stack equals to the top element of the stack, then we remove the top element of the stack, otherwise we push the new element to the top of the stack. After those operations we will be down to a stack which will contain out final answer.

       FULL SOURCE CODE

ACM 1083. Factorials!!! / Факториалы!!!

 Just input the number and the string and calculate with the given formula n*(n-k)*(n-2*k).....(n-m*k) where m*k<n.  (k is the number of !s).

       FULL SOURCE CODE

ACM 1086. Cryptography / Криптография

    The 15000 the prime number is 160000 and something so we can find all the prime numbers up to 200000 and save them and then process the input. The fast way of finding the prime numbers from 1 to N is the sieve of Eratostenes which works for O(NlogN) time. You can find info about the sieve of Eratostenes here.

       FULL SOURCE CODE

ACM 1001. Reverse Root / Обратный корень

You need to input some numbers and then output their square roots in the reverse order.

       FULL SOURCE CODE 

ACM 1209. 1, 10, 100, 1000...

I am not sure about the pattern in here but we can do it with recovering the sequence. indeed the query can be up to 2^32 where we can't keep the full sequence but just because it consists of only 1s and 0s, we can only keep the positions of 1s. In C++ the STL container map can handle this situation. So how do we do it, the first one is 1. The second one is also 1. Then the next 1 can be found by jumping form the previous one 2 steps. Then 3, then 4, .... We can do it until we calculate all the 1s up to 2^32 which is not too long in our case, it will be a little more than sqrt(N).

       FULL SOURCE CODE

ACM 1319. Hotel / Отель

 Suppose we have a function which takes a point and starts going into the direction of the diagonal and filling the elements on the way until it gets out of the border N. It is easy to implement, we need to take the given coordinate and add every time 1 to both of the coordinates to get to the next cell. We need to launch this function for the cells A[1][n...1] which will complete the first half and also A[2...n][1] which will complete the matrix.

       FULL SOURCE CODE

ACM 1079. Maximum / Максимум

There might some pattern in this sequence but just because n<99999 then I suggest building the sequence and then calculate the maximums. I suggest precalculating all the answers before processing the input. You can keep an additional array of answer ANS[100000] where ANS[i] shows max (A[1],A[2],....A[i]).

       FULL SOURCE CODE

ACM 1313. Some Words about Sport / К вопросу о спорте

Here is how our program should work. We start from a certain cell, and decrease both coordinates by 1 and output the number of the new cell if it is within the range [1..n][1..n].  We need to do this for all the elemenets of the first column one after another which will cover the half of the solution and then continue it for the elements [2..n][n].

        FULL SOURCE CODE

ACM 1264. Workdays / Трудовые будни

 We check for every number N times. Just because the numeration starts from 0  (0...M) we have M+1 number to check for which gives the final answer of N*(M+1).

       FULL SOURCE CODE

ACM 1197. Lonesome Knight / Один в поле воин

 We need to input the coordinates in the chess format and turn it to number and then check for every coordinate the knight can strike.
This is the list of all the corresponding coordinates needed to add to the current coordinate to get to a cell which a knight can strike.
  1, 1, 2, 2,-1,-1,-2,-2
  2,-2, 1,-1, 2,-2, 1,-1

       FULL SOURCE CODE

ACM 1005. Stone Pile / Куча камней

N is up to 20. Which means there are total of 2^20 ways of forming 2 different piles. The brute force solution will be enough but we need to find the best way to implement it. We can do it with bitmasks.  In other words, we take numbers from 1 to 2^20 and get their binary representation (which must have a length of N, if it is not long enough we add zeroes to it). Then in our binary representation , the Ith position will tell us to which pile do we take our Ith elemenr. If it is 1 than we need to take it to the first pile otherwise to the second pile.

       FULL SOURCE CODE

ACM 1293. Eniya / Эния

    Surface of each will be AxB and also x2 because we need both sides and the final answer will be AxBx2xN.

       FULL SOURCE CODE

ACM 1409. Two Gangsters / Два бандита

Just because both of them shot the last bottle , the entire number of bottles will be A+B-1. And the final answer A+B-1-A, and A+B-1-B.

       FULL SOURCE CODE

ACM 1025. Democracy in Danger / Демократия в опасности

It is easy to understand that we need to choose the groups which have the smallest amount of people so that the half of it would be small and the total number of voters would be as small as possible. So we need to sort our given data and choose the first N/2+1 groups.

       FULL SOURCE CODE

ACM 1068. Sum / Сумма

Just a simple sum problem with little constraints, but be careful when dealing with the negative numbers because the input can consist of negative number as well.

       FULL SOURCE CODE

ACM 1000. A+B Problem

 read 2 number and output their sum, the first task of almost any programmer.

       FULL SOURCE CODE

SPOJ 5976. Traversing Grid (TRGRID)

The constraints of this task give us a hint that there is no complicated algorithm which must be hardly implemented. After doing a few tests with pen on paper you might figure out a few things. First of all suppose we have NxM grid, so after doing one full cycle (on cycle means that we went to the end of the first row, then turned down, went to the bottom of the grid, then turned left went to the end and then turned upwards and went until we reached the coordinate (2,1) which means that we are again facing right which means that we have go all over again but on the grid of size (N-2,M-2). For a better understanding have a look at the picture below.

The red line represents the first cycle, after it we are again facing right and it is the same as passing 1x2 grid. So, the first thing is decreasing the grid as much as we can by cutting 2s out of it. How do we cut 2s? We take the minimum of 2 sides minus one, and if that number is even then we subtract it from both sides or we decrease it with 1 and then subtract it.  After the cutting process the smaller side of grid will be left either 1 or 2. Now it is time only for a few conditions. In case of (1,1) the answer is R, in case of (1,2) it is R, in case of (2,1) it is D , in case of (2,2) it is 'U' , in case of (1,other)  ,  it is R and in case of , (other ,1) is D and for (2,other) is 'L' and (other, 2) is 'U'. Also check out the source code .

       FULL SOURCE CODE 

SPOJ 1728. Common Permutation (CPRMT)

  From the first look it really smells like a complicated dynamic programming algorithm but we need to have a deeper look to understand the difficulty of this task. Here is what the task wants from us: find a string x that a permutation of x will be a subsequence of s1 and s2. Subsequence means that the letters should exist on those strings s1 and s2 and every other letter must be on the right than the previous one (they don't have to be consequetive) . This would be a dynamic programming task if there wasn't the phrase "one permutation of x". Let me demonstrate with an example. CgrAyuT

(I made some letters uppercase for clarity). So , if we have an X="CAT" than it can be considered as a subsequence of the given string but x="TAC", can't , but we are free to take any permutation of X we want so we will move the elements and form the word "CAT" and check. So,  the answer is simple, it will be just a string which contains all the letters which both of the strings contain. It can be found easily in O(s.size()^2) time which is enough. NOTE don't forget to sort the final answer because the problem requires the first answer in alphabetical order.

       FULL SOURCE CODE

SPOJ 8061. Christmas Play (AMR10G)

N<=20000. We need to sort the entire array and then for every i , if i+k-1<=n choose the minimum of A[i+k-1]-A[i].

       FULL SOURCE CODE

SPOJ 7169. Pizza

The first thing just comes to mind is to add all the number and round up and output the answer, but unfortunately it is not how it works. Suppose we have 3/4 3/4 and 1/2 by doing the way I described above you will calculate 2 pizza's for friends but the answer is 3, because if we by 2 pizzas for 3/4 s then with the remaining 1/4 and 1/4 we can't form one 1/2 . So, here is what I suggest doing for being correct. First of all we need to buy pizzas for all 1/2s (take 2 1/2s and add 1 pizza) until either one 1/2 is left or none. Then we need to buy 1 pizza for 1/2 and 3/4 (until we run out either of 1/4s or 3/4s). If we have 3/4s left then we need to increment the answer by their number. Then we need to add the number of 1/2s *0.5 and the number of 1/4s *0.25 and round up the answer. NOTE Don't forget to add 1 to the total answer (see the problem statement) and output the new line.

       FULL SOURCE CODE

SPOJ 8670. THE MAX LINES

    First of all, it is easy to notice that the triangle is a right angle triangle because it has a base which is the diameter of the circle. that means that BC^2=AC^2 + AB^2 we can add and subtract one AC which will not change the equation. BC^2=AC^2 + AB^2 -AC + AC  . Let us write BC^2 as (2r)^2 which will be 4r^2 and let's group the right part properly. 4r^2= (AB^2+AC)+AC^2-AC . =>

AB^2+AC= 4r^2 -AC^2+AC which can be considered as a function f(AC) where AC is the unknown variable. We need to find the maximum value of function f(AC) which can be done with differentiation . f '(AC)= 0 -2*AC +1 .
-2*AC+1=0 => AC=1/2  => we can easily notice that the function increases up to f(1/2) and then it decreases so the maximum value is at AC=1/2 which gives the full answer of 4*r*r -1/4+1/2 =4*r*r+1/4.

       FULL SOURCE CODE

SPOJ 6219. Edit Distance

  This is a basic problem of edit distance which you can read about in here http://manyprogrammingtutorials.blogspot.com/2014/09/edit-distance-levenshtein-distance.html

.

       FULL SOURCE CODE

Edit Distance ( Levenshtein distance)

  The task is to find the minimum number of operations necessary to turn one string into another. The available operations are 1. insert a char everywhere in a string 2. Delete any char of the string 3. Replace any char in a string.  This is another Dynamic Programming problem. Suppose the length of the first string (S1) is N and the length of the second one (S2) is M. We need an array of NxM where the element A[I[J] shows the answer for the segments S1[1..I] and S2[1..J] (let us add a blank char in front of both string). For a better understanding let's have a look at a table below.

As you can see the string starts with an empty character, which means that the first row and the first columns are filled by formula a[1,I]=I and a[J][1]=J which is true because for obtaining an empty string we need to delete all the elements of the other string which will give an answer of the size of the non empty string. Basically when looking at the cell A[I][J] we need to look to the cells A[I-1][J] , A[I][J-1] and A[I-1][J-1]. Let's consider the cell A[I-1][J] of we were able to build the string S2[1..J] from S1[1...I-1] for A[I-1][J] steps then fro building the string S[1..J] from S[1..I] we need to add one more step (just add the new character (new means the Ith) and it will be A[I-1][J]+1 moves). The same goes for A[I][J-1]. Now let's consider the A[I-1][J-1] the, int this case we have 2 new elements S1[I] and S2[J], we can build it with the same number of steps if we won't have to deal with the new elements which means that if S1[I[==s2[J] then we only need A[i-1][j-1] operations to make the string S2[1..J[ from S1[1..I] otherwise A[I-1][J-1]+1 operations. So the final formula is A[i][j]=min( A[I-1][J], A[I][J-1], A[I-1][J-1]  + 1 (+1 if S1[I]not equal to S2[J]). 

SPOJ 7757. Flowers Flourish from France

The task itself is not hard, but we need to carefully handle the implementation. Here is hat I suggest, take the first letter and keep it in a variable. Let's call it K. K is the symbol which we need to check every time. and also turn it into upper case, if it is already uppercase it will not change, we do it so that we can avoid the problem of letters being the same but the cases being different. Then loop over the given string , whenever we encountered a space that means that the next letter is a first letter of a word, we take that letter, turn it into uppercase and check with variable K. If they are the same we keep going, but now the value of K becomes the newly found letter uppercased. If at some point a letter which was after ' ' (the forst letter of a certain word) is not equal to current K than we abort and output 'N'.

       FULL SOURCE CODE

       

COJ 1626. Adding Reversed Numbers

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 7406. Beehive Numbers (BEENUMS)

The important thing here is to notice the pattern of the beehive. The first layer contains 1 cell. When building a new layer we lay 6 more. If you just take out pen and paper and start drawing you will figure out the pattern, when laying the next layer we lay 6*2 12 cells, so for laying Nth layer we will need N=6*(N-1) cells when N>2. I recommend calculating all the numbers and store them in the map before processing the input.

       FULL SOURCE CODE

SPOJ 95. Street Parade (STPAR)

   We need to take out elements in order with a little help of one stack.  We need to solve this by eliminating every possible element starting from the left and also taking out those very same elements from the stack if it's their turn ( the phrase "their turn" means that we already eliminated all the elements up to the current one , and we can eliminate him if he is one the leftmost spot or on top of the stack). We need to loop over the given array from left to right and see, if it's his turn then eliminate it (this can be understood in many ways, just ignoring and passing to the next one  or removing it from the array, it depends on your preference ). (note that we keep a variable cur (current) which shows which is the current element to be eliminated), now if we can't eliminate it we add it to our stack waiting for it's turn, (NOTE there is no other way, if our current element can;t be eliminated now because it's not his turn then we do not have any other option but to push him into stack). And in every step we also check "if it's now the turn of the top element of stack", if yes we need to keep removing them until we either reach an element which can't be eliminated now or our stack gets empty.  We need to keep doing those until we have looped over all elements. If we were able to successfully remove all of them then the answer is yes.

       FULL SOURCE CODE

SPOJ 379. Ambiguous Permutations (PERMUT2)

The constraints N<=100000 make this task an easy one. We need to build the sequence and check if every element is equal to the given sequence if it is then the answer is yes otherwise no.

       FULL SOURCE CODE

COJ 1189. Skew Binary

It is guaranteed that the number will fit in 32 bit integer, the rest is easy,we need to input the number as a string, then from right to left loop over it and every time multiply the current digit with it's appropriate power of 2 minus 1.

       FULL SOURCE CODE

COJ 1143. To and Fro

This is an implementation task so we need to think the easiest and the most understandable method. I suggest trying to recover the matrix then the string itself. We can do it in the following way. The first element of the given string S[0] is the first element of an array A[1][1] . Now we need to move according to the direction, and every time write the current char in the current spot, whenever we reached the end (or the beginning) of the array we need to flip the direction, get down to the next row and keep on going. Check out the source code for a better understanding.

       FULL SOURCE CODE

SPOJ 400. To and Fro

This is an implementation task so we need to think the easiest and the most understandable method. I suggest trying to recover the matrix then the string itself. We can do it in the following way. The first element of the given string S[0] is the first element of an array A[1][1] . Now we need to move according to the direction, and every time write the current char in the current spot, whenever we reached the end (or the beginning) of the array we need to flip the direction, get down to the next row and keep on going. Check out the source code for a better understanding.

       FULL SOURCE CODE

COJ 1457. Baseball Tournament

The number of distinct pairs of N people is ( N*(N-1) )  /2 here is why
suppose we have all the members numbered from 1 to N.
1,2,3...N.
So, one can be a pair( can play a game) with 2,3,4,...N.  Total N-1 games
2 can be pair with all starting from 3 . with 3,4,5,...N. Total N-2
........
..........
and N-1 can be a pair with N. total 1 pair.
So the result is, 1+2+3+..+N-1 which has a good formula of  ( (N-1)*(N-1+1) ) /2
The final answer is the answer above multiplied with the given parameter K.

       FULL SOURCE CODE

COJ 1179. Optimal Parking

  The task might not be very clear on the statement part or maybe it is left up to the reader to understand. Anyway, the task wants the best coordinate to park where the distance which we walk would be minimal, and the distance means, getting out of the car, entering every store and coming back to the car. No matter where we park our car the distance walked will be minimal if we get to the beginning (or to the end) of the line and start visiting stores one after another until we have reached the other end of the line and then we also need to add the distance which takes from the other end of the line to our car. The constraints are only from 0 to 99 so we can just try out every single coordinate and calculate with brute force method.

      FULL SOURCE CODE

COJ 1808. Hamming Distance

We only need to input the 2 strings then loop over and see if elements on the same index match or not.

       FULL SOURCE CODE

COJ 1328. CAVerage

We only need to sum up all the numbers, then divide on N and then check if it is smaller than every element or not.

       DOWNLOAD THE FULL SOURCE CODE

COJ 2148. Quadratic Equations

The equation has a solution if b^2-4*ac>=0.

       FULL SOURCE CODE

COJ 2091. Counting Task

There are many ways you can solve it. You can can take every element get it's code and mark it in a boolean array or you can simply use C++ map to mark the characters directly.

       FULL SOURCE CODE

COJ 1324. Snow White

There are only 9 number so the easiest approach is taking every single possibility and check. There are different ways but the easiest method is using 7 for loops.

       FULL SOURCE CODE

COJ 1237. Mean Median Problem

There are only 3 cases possible
1. (A+B+C)/3=A
2. (A+B+C)/3=B
3. (A+B+C)/3=C

from each we can get
1. C=2*A-B
2. C=2*B-A
3. C=(A+B)/2

You can make a function which checks the answer for 3 numbers and run it 3 times on all of the cases above and pick the minimum.

       FULL SOURCE CODE

COJ 2620. Aaaaaaaah

Output one 'A' then 4*N 'a' s and then one more 'h'.

       FULL SOURCE CODE

COJ 1219. Bounty Hunter

This task can be a little confusing because of the second parameter which is the distance from home. You may easily ignore it, there is nothing specified in task which wants us to use it, and more to that it says that who cares if we walk much, the important thing is to get paid as much as possible SO we only need to sort the array and start taking deals from the most expensive until our bullets run out.

       FULL SOURCE CODE

COJ 1273. Domino Factory

The most important thing is to correctly calculate the number of domino figures. So how do we do it?
Suppose we have numbers from 0 to N, how many distinct pairs we can make?
0-1,0-2.0-3.......,0-N
which gives N+1 pairs
so now let's consider all the new dominoes with 1
1-1,1-2,1-3,...1-N
total of N pairs
than for 2 it is
2-2,2-3,2-4,....2-N
N-1 pairs
and so on until the last one which is 0 .
So the total number of pairs of number from 0 to N is the sum of numbers from 1 to N+1 which has a good formula ( (N+1)*(N+2) )/2. The answer will be the sum of number from 1 to N+1 multiplied with the 2 sides of domino.

       FULL SOURCE CODE

COJ 1101. Binaries Palindromes

The constraints are a little high. It would be better if the answers have been calculated before reading data. Check whether the number from 1 to 200000 are binary palindromes and keep the answers/ And then input data and output answer.

       FULL SOURCE CODE

COJ 2205. Counting Ones

The constraints are very low, up to 1000 so we can do it with simple implementation, take every number and divide it to 2 and every time add the answer and the output the final result.

       FULL SOURCE CODE

COJ 1573. Just Another Easy Problem

The task consists of 2 parts, conversion and check. First of all conversion. If we have a hex number and want to convert it to decimal we have to do the following. We need to multiply every digit with the power of it's index base 16 counting from the right to left. For example we have a number ABCD , after converting to decimal it will be 13*(16^0) + 12* (16^1) + 11*(16^2) + 10* (16^3).  Now let's check for the divisibility. The sum of numbers form 1 to N is N*(N+1) /2 and it is easy to notice that when N is odd then the result is divisible otherwise not.

       FULL SOURCE CODE

COJ 1839. A Funny Task

This task may sound a little weird, because even if we have even number of oranges, after passing the first guard we will be down to odd number and we might have a little confusion when giving the half and 3 more, but you just skip this and write the answer as it should be ,   (((N+3)*2+3)*2+3)*2 . 

       FULL SOURCE CODE

COJ 1842. Distance of Manhattan

The statement of the problem already gives everything, you only need to input 4 numbers and output the sum of absolute differences of the first third and second forth numbers.

       FULL SOURCE CODE

COJ 1118. The Drunk Jailer

Due to it's small constraints we can easily implement this algorithm. N is up to 100 which makes it very easy to solve using brute force.

       FULL SOURCE CODE

COJ 1445. What's Next?

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

COJ 1388. Last Digit of A ^ B

We can only have a look at the last digit of each base by ignoring the rest of the number. If we have a closer look at the last digits of powers from bases 0 to 9 we will notice a good pattern. So below is the list of last digits of  powers of numbers from 1 to 9.
1- 1 1 1 1 1
2- 2 4 8 6 2
3- 3 9 7 1 3
4 -4 6 4 6 4
5- 5 5 5 5 5
6- 6 6 6 6 6
7- 7 9 3 1 7
8- 8 4 2 6 8
9- 9 1 9 1 9

One thing we can notice which is true for all numbers is that after every 4th power the last digits are repeating themselves . This means that the answer for the power of 3 and the power of and the power of 11 are the same. So we only need to consider the powers from 1 to 4 and then when outputing the answer we need to only take the remainder of the given power and check for the according last digit. Also don't forget the power=0 case.

       FULL SOURCE CODE 

COJ 1025. Democracy in Danger

It is easy to understand that we need to choose the groups which have the smallest amount of people so that the half of it would be small and the total number of voters would be as small as possible. So we need to sort our given data and choose the first N/2+1 groups.

       FULL SOURCE CODE

COJ 1079. Sums in a Triangle I

There is not much to say about this problem. The idea is simple , we just keep an array of answers , the we loop over it and update the current element with the best answer ( it would be max( a[i-1][j-1]+a[i][j],a[i-1][j]+a[i][j]) ) The drill ios the source limit. You need to preserver as much as possible . Avoid using many enters, spaces. Don't keep variables which you are not going to use. Make sure to check my source code. Its only 2 lines :D The first is #include <iostream> and the second on is full of operations. Its a long line :)

       FULL SOURCE CODE

COJ 2413. Div 5

The number is divisible by 5 if it's last digit is either 5 or 0.

       FULL SOURCE CODE

COJ 1506. Exam Grader

 Another implementation. Just loop over the correct string and every other string and calculate the answer accordingly.

       FULL SOURCE CODE

COJ 2196 - Even? Odd?

If the last digit of a number is divisible by 2 it means that the entire number is also divisible by 2. The rest is easy, input it as a string, take the last char and check.

       FULL SOURCE CODE

COJ 1212. Jingle Composing

The task is easy , it needs a good implementation. For making things a little less complicated I recommend writing a separate function which gets the value of a char.

        FULL SOURCE CODE

COJ 1132. Divisor Summation

 The number of test cases i really large so we can't process every test individually , it will just take a lot of time. So, instead we can precalculate all the answers from 1 to 500000. here is how we should do it, it will look like a sieve of Eratostenes, we will start looping from 2 to 500000 and every time. Let us have an array A where A[I] shows the answer for I. On every step of our loop we take the current index and add it to every member of A which is divisible to I. Such as, for 2 we take 2 and add 2 to numbers , 4,6,8,10,....500000. Then we do the same for 3,4,...500000. This will not take too much time and will give us all 500000 answers we seek. Then we just need to input the queries and output the answer directly.

       FULL SOURCE CODE

SPOJ 74. Divisor Summation

 The number of test cases i really large so we can't process every test individually , it will just take a lot of time. So, instead we can precalculate all the answers from 1 to 500000. here is how we should do it, it will look like a sieve of Eratostenes, we will start looping from 2 to 500000 and every time. Let us have an array A where A[I] shows the answer for I. On every step of our loop we take the current index and add it to every member of A which is divisible to I. Such as, for 2 we take 2 and add 2 to numbers , 4,6,8,10,....500000. Then we do the same for 3,4,...500000. This will not take too much time and will give us all 500000 answers we seek. Then we just need to input the queries and output the answer directly.

       FULL SOURCE CODE

COJ 1681. Solving Polynomials

a*x^2+b*x+c=0 has a solution only when b^2-4*a*c >=0 . The rest is simple.

        FULL SOURCE CODE

COJ 1022. Train Swapping

If we look deeper we will understand that no matter how we do the swaps the answer is not going to be different ( of course if we do swaps only when one is bigger than the one standing next to him). The rest is easy, we need to loop over and swap if there is a need until there will be no more swappings left.

       FULL SOURCE CODE

COJ 1683. DPA

The constraints are very low (N<=500) which means that the simplest brute force solution will pass 100%. Just loop over all  the numbers uptp N-1 and check for divisibility and add to sum, then compare the sum with N and output the answer accordingly.

       FULL SOURCE CODE

COJ 1326. Account Balance

Again an easy implementation, just read the numbers and subtract or add according to the character given with the number. The output the answer.

       FULL SOURCE CODE

COJ 1252. The Seven Percent Solution

Another implementation task. I recommend avoid using insertions or other complicated stuff, just loop over the string and see if the current char is from a given list or no. If it is than print the corresponding code otherwise output itself. 

       FULL SOURCE CODE

COJ 1077. The 3n + 1 Problem

First of all, there is no specific pattern for numbers so we need to calculate all of them. First of all we better calculate all the numbers and save them in an array. We need to do it extremely efficiently because 10^6 is large and we might easily end up getting TLE. So first of all the A[I] shows the answer for the number I. A[1] is 1 , then we need to continue, looping from 2 to 10^6 we need to calculate answer for every single answer, but we can be a little clever. Here is how, suppose we need to calculate for a specific number K. now we calculate all the numbers on the way, suppose we got Kn,Kn-1,.....1 so there are n numbers, So the answer for K is n. We calculated it successfully but there were numbers which we just threw away, the ones we got after K before reaching 1, isn't it true that the number after K has an answer of n-1 and the number after him has the answer of n-2.... So instead we can keep all the numbers we seen so far, and then when we reached 1 we can loop back and give each number on the way it's appropriate value which will save us a lot of time. Then the rest is just inputing and outputing the answer. NOTE on big note which caused me a lot of WA, it is not specified that in the input i is smaller or equal to j, this is important thing to consider. Also check out the source code for a better understanding,

       FULL SOURCE CODE

COJ 1157. u Calculate e

This task is easy by itself, it is just a simple calculation but as you can see it has a low accepted percent which depends on some reasons. I got wrong answer many times only because of the output format.First of all you it is a little confusing but you really need to output all the garbage before actually outputing the numbers. The first two lines, which are "n e" and  "- -----------". Those two need to be printed, then you need to keep the format. The first tree numbers you better output individually then you need to keep the precision , exactly 9 digits after the dot., nor more and not less.

       FULL SOURCE CODE

COJ 1024. 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 simple 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

COJ 1069. Soda Surpler

Constraints are small so we can do it with the most obvious way. First of all, add the first two numbers, now we need to check how many sodas we can buy, and after that, when we buy them how many empty total bottles we are having left after buying and drinking the current sodas. Do this until we are unable to buy any more. Also check the case of infinite , there are 2 cases, either soda costs 0, or soda costs 1 but we have at least 1 bottle.

       FULL SOURCE CODE

COJ 1493. Geometrical Task II

Here are formulas for the necessary areas
Triangle (a*h)/2  a is the side and h is the height taken to that side
Rhombus (d1*d2)/2  d1 and d2 are diagonals of rhombus
circle pi*r*r   where pi is 3.14 and r is the radius.

 If you are having trouble outputing with correct precision have a look at this.

       FULL SOURCE CODE

Output double/float numbers with precision

Sometimes we require to output numbers rounded to some exact precision. There are a few ways of doing them. If you are using scanf/printf you can do it in this way. Suppose we need to  output to 7th precision,

double a;
printf("%.7f",a);

This means output a rounded to 7th precision.

 If you need to use cin and cout here is how you should do it. Include iomanip  ( #include <iomanip> )
then before couting write this
cout<< fixed << setprecision (7);
cout<< a<< endl;

COJ 1043. Simple Dishes

Here is a very simple but good approach, we loop from the right to left over our dishes and whenever we see one we can take we sure take it and decrease the mass bye the dish we just took which will eventually work out the answer itself.

       FULL SOURCE CODE

COJ 1177. Group Reverse

The task is a simple implementation task. You can input and output directly with carefully using loops or you cna modify the string and then output it. Have a look at source code.

       FULL SOURCE CODE

COJ 1176. Ternary

We need to keep a sequence and every time add the element N%3 to that sequence and divide N to 3 until it becomes 0. And then output the reversed sequence.

       FULL SOURCE CODE

COJ 1070. A Simple Calculation

For explaining this task we need to have a look at an example.

On the picture above you can see the example of N=3. So, as you can see I gave coordinates to every single edge. Now, we will solve 2 different tasks, the number of squares and the number of rectangles. First of all let's try to calculate the number of rectangles. We will form rectangles with 2 coordinates which we will choose, one of them will be the upper left point and the second one the lower right point. So the it's easy to understand that the first coordinate (upper left coordinate) can be only in rancge   ( [1,3] ,[1,3] ), so at first let's consider the first coordinate as point (1,1) how many rectangle we can form with the upper left coordinate (1,1) the lower right coordinate can be (2,2) (2,3) (2,4) (3,2) (3,3) (3,4) (4,2) (4,3) (4,4) in other words we can take the coordinate (2,2) and we can see how long can we expand it both vertically and horizontally which leaves 3x3 toatal of 9 possibilities where the upper left coordinate is (1,1). Now let's check for (1,2) the same way, we can take coordinate (2,3) and see how much we can expand it, we can expand 3 vertically and 2 horizontally which gets us total of 2x3 6 possiblities. I think we can understand now that we will have this result, 3x3,3x2,3x1,     2x3, 2x2, 2x1,   1x3,1x2,1x1 those are results where the upper left coordinate is respectively on the first second and the third line. SO, the final answer is all the multiplication pairs of numbers from 1 to N. .
  Now about the squares, we can figure out the number of squares with the same way. If we consider the upper left coordinate as (1,1) then how many squares we can form? 3 totally Then if we consider all the acceptable coordinates of the first line as the upper left coordinate we will get the following result , 3,2,1.
Then on the second line it's 2,2,1. Then it's 1,1,1. As you can see the second line's answer is smaller than the previous one by 1. And the third is smaller than the second by 2.

       FULL SOURCE CODE