I'm glad to see you on Codeforces Beta Round # 64.

Today I am the author of the tasks. I'm a student of Tyumen State University.

I want to thank all those who helped me to prepare the round: Nikita Durynin (Austeritas) for the pair ideas for the tasks, Dmitry Bochkarev (Walrus) and Chernenkov Alexey (Laise) for the testing, Artem Rakhov (RAD) for coordinating the activities, Maria Belova for translating and Mike Mirzayanov (MikeMirzayanov) for a great system.

Today I am the author of the tasks. I'm a student of Tyumen State University.

I want to thank all those who helped me to prepare the round: Nikita Durynin (Austeritas) for the pair ideas for the tasks, Dmitry Bochkarev (Walrus) and Chernenkov Alexey (Laise) for the testing, Artem Rakhov (RAD) for coordinating the activities, Maria Belova for translating and Mike Mirzayanov (MikeMirzayanov) for a great system.

Today you will visit the Walrusland and help the common citizens and government to solve their problems.

Good luck for everybody, let the best man win!

Winner is Petr. Congratulations!

I hope this will be a good contest!

For a / rev(a) , you can transform it to its lowest form c / d by dividing numerator and denominator by their gcd and store (c,d) -> a in a map.

This way, for each x, you can find all the numbers y, that can form lucky pair (x,y)

That was the main idea and after that there were different approaches. I iterated over all x , from 1 to max_x , and for each x , did a binary search on y to find the minimum y in [1,max_y] that has at least w pairs.

> This way, for each x, you can find all the numbers y, that can form lucky pair (x,y)

How? And what did you store in the map?

It seems it was EPIC FAIL

… using a binary indexed tree. That was a missing part in my case.

An alternative way is, as daffes wrote, to do it linearly (starting from (

x,y) = (1,max), increase_{y}xif there are not enough lucky tickets, decreaseyotherwise). I had completely overlooked this approach.http://www.topcoder.com/tc?module=MemberProfile&cr=22771049

Description, i think that limit the end of a WORD with only one ( . , ? , !) or none at all ?

By the way, in this problem, a sentence always ends with one of “.” “?” “!”. A sentence without these symbols is not allowed.

A long time lost, searching for an error in the solution, which did not exist

size of one messagefrom samples of B.and what was the logic behind 4rth question ?

^{0}, 3^{1}, 3^{2}.B_{k},k≥ 1 with size 2^{k}× 2^{k},B_{k + 1}is built based on four blocks, each of size 2^{k}× 2^{k}. To get the answer you cannot avoid placing something likeB_{k}at the lower left 2^{k}× 2^{k}block. But forB_{k + 1}the upper triangle must be filled, so you can see that the upper right 2^{k}× 2^{k}block must have no space left. What about upper left and lower right ones? Well, you can actually see that their upper triangles are also filled, giving you exactly the same initial setting forB_{k}, so you must have number of spaces for each block exactly the same as that inB_{k}. So ifB_{k}hasC_{k}spaces, thenB_{k + 1}hasC_{k + 1}= 3C_{k}spaces fork> 1. That gives you the 3^{k - 1}formula fork> 0. Be careful in handling the casek= 0.Thanks.