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