ACM 2031. Overturned Numbers

  The task statement gives us a great hint, specifically the picture in the statement, that is the longest possible sequence, since 2 3 4 5 7 are unreadable this means that the last digits of the sequences must be 8,9,0,1 at best case which has a length 4.

ACM 1106. Two Teams / Две команды

Here is a little suggestion. Let us start a wave from any node. That chosen node we will send to the first team, then all of his unmarked neighbors will be sent to the second team, and then the neighbors of all the nodes form the previous to the first team and so on. If we have a forest ( where there are sub graphs not connected to one another) then we should do this for all the sub graphs. Then we need to check whether our result is a valid solution or not. If it is not, then there are no other ways of making the teams. 

ACM 1139. City Blocks / Городские кварталы

 First let us answer the following question : how many coordinates will the helicopter pass which have a natural coordinates. We need to look at the geometrical illustration.

Have a look at the picture below.

So, this is our coordinate system and the points (0,0) and (9,6) are connected, what are all the coordinates which have natural coordinates and the red line passes over them those are (0,0) (3,2) (6,4) (9, 6) . I think you already see the pattern here but let's try proving it. So we can build a right angle triangle with the points (0,0) (9,0) and (9,6) , we will call that triangle 1. And let's build another one with the points (0,0) (0,6) (6,4) we will call that triangle 2. So, if we compare the triangles 1 and 2 we can say that they are similar (due to equal angles) which means that their sides are   multiples. A Conclusion  all the multiples of the pair (9,6) (to the one which we connected the initial (0,0) point) are vertexes of such triangles, => are the points which have natural coordinates which our line crosses. Let's have a little case which is (0,0) to (2,3). (2,3) do not have any multiples so there is no point with natural coordinates on the way. which means that the line crosses all the available vertical lines and all the available horizontal lines separately. The total number of those is 2+3-1=4 which gives us the first idea of the answer which is N+M-1. If there are natural coordinated points then our task is divided into sub tasks, in out case we have 3 different sub-tasks each has the same answer. For finding the number of natural coordinates on the way we need to find the GCD (greatest common divisor). In this case it would be (M/GCD+N/GCD-1) * GCD which gives the answer of M+N-GCD.

ACM 1638. Bookworm/ Книжный червь

 This task has a difficulty of only 84  and yet almost 2/3 of the total submissions are not accepted. I liked this one really. It is a very tricky task. Let's start with examining the input. Some people say that it is wrong, it looks wrong at first but eventually you will understand. So here is the input.

10 1 1 2

We Expect the answer to be 22, because we expect that the from the first page of book 1 to the last page of book 2 is a total distance of 2 covers and 2 volumes. But it's not correct because we need to imagine the book shelf in our minds and see for ourselves. I made a little picture to illustrate my point below. Have a quick look.

I think now everything is settled. As you can see it takes only 2 covers to travel from the beginning of the first book to the end of the second book which buildup our generaly formula  (end-start)*2*cover + (end-start-1)*volume. 

But there are 2 more tricky cases. It is not guaranteed that the starting number is always less then the ending number. If they are equal then the worm passes through the whole volume and if the second one is smaller than the first one then the worm passes though 2 more additional volumes. 

ACM 2035. Another Dress Rehearsal / Очередной пробный тур

First of all, if X+Y is less than the sum than there is no answer, in all other cases we can find an answer pair for sure. Here is how we will find it. We will take the difference of the X+Y and the sum. Assuming that our answer pair is X and Y until the difference is 0. We take the difference of X+Y and sum and we subtract it from X, until either X becomes 0 or the difference. The rest difference, we will subtract from Y and the resulted X and Y will be out answer.

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