### NALP's blog

By NALP, 12 years ago, translation,

Hi to all!

## 215A - Bicycle Chain

Because of small constraints we can iterate i from 1 to n, iterate j from 1 to m, check that bj divide ai and find max value of

Unable to parse markup [type=CF_TEX]

. Then we can start this process again and find amount of the pairs in which

Unable to parse markup [type=CF_TEX]

is max value.

## 215B - Olympic Medal

Let amagine we have values of

Unable to parse markup [type=CF_TEX]

, p1 and p2. Then:

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

Now it’s easy of understand, we must take maximum value of

Unable to parse markup [type=CF_TEX]

and p1, and minimum value of p2 to maximize

Unable to parse markup [type=CF_TEX]

. You could not use three cycles for iterating all values, but you could find property above about at least one value and use two cycles.

## 215C - Crosses

Let’s iterate

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

— sides of bounding box. Then we can calculate value of function

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

, where two lastest brackets mean amount of placing this bounding box to a field n × m.

Now we must calculate

Unable to parse markup [type=CF_TEX]

. At first, if

Unable to parse markup [type=CF_TEX]

then the result of the function is

Unable to parse markup [type=CF_TEX]

(you can prove it to youself).

If

Unable to parse markup [type=CF_TEX]

then we must to cut 4 corners which are equal rectangles with square

Unable to parse markup [type=CF_TEX]

. We can iterate length of a one of sides, calculate another side, check all constraints and add 2 to the result of the function for all such pairs of sides.

The time of a solution is O(n3), but it’s with very small constant, less then 1.

## 215D - Hot Days

You can use only two features about this problem: the solution is independenly for all regions and there are only 2 possible situations: all children are in exactly one bus or organizers must take minimum amount of bus such no children got a compensation. It’s bad idea to place some children to hot bus and to place some children to cool bus simultaneously.

For solving you must calculate this 2 values and get minimum.

## 215E - Periodical Numbers

Will be soon…

• +30

| Write comment?
 » 12 years ago, # |   +1 Why in problem D (Hot Days) you only need to consider the two situations mentioned? Thank you.
•  » » 12 years ago, # ^ |   0 because the cost is a linear function about the number of buses
•  » » 12 years ago, # ^ |   0 I also can't understand the solution
•  » » » 12 years ago, # ^ |   +1 Supose that we will arrange n buses in ith city： If T[i]-t[i]>m/n , no children will get compensations.If T[i]-t[i]
•  » » » » 12 years ago, # ^ |   0 Thanks a lot. I get it now :)
 » 12 years ago, # | ← Rev. 2 →   0 I didnt get the solution for Crosses. Here f(n1,m1,s) denotes the number of crosses that can be created with area s and n1 = max(a,c) & m1 = max(b,d). But why are we adding f(n1,m1,s).(n-n1+1).(m-m1+1) to the answer ?
•  » » 12 years ago, # ^ |   0 Because we can additionally position the center of the cross in Unable to parse markup [type=CF_TEX] ways on the given grid.
 » 12 years ago, # |   +3 So will you write the solution for the last problem too?
 » 12 years ago, # |   +1 Why the solution to problem E still hasn't been published?