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.