Если верить цветовой шкале, worse станет первым участником с белым ником

В каждый момент времени у нас есть колбы с h₁, h₂, ..., h_n литрами ртути. Воды в колбах никогда не будет.

Первый запрос состоит в выполнении присваивания h_p = x (то есть в p-той колбе теперь будет x литров ртути).

Второй запрос состоит в следующем: нам дано v литров воды. Мы можем выбрать некоторое непустое подмножество колб и произвольным образом (мысленно, вода в колбах от эксперимента не появляется) разлить в них эти v литров ртути. Более формально: пусть = {m₁, m₂, ..., m_k}, где . Тогда мы должны взять любие такие положительные числа d₁, d₂, ..., d_k, что d₁ + ... + d_k = v.

Мы можем выбирать множество и числа d_i как угодно. При этом мы хотим минимизировать значение величины .

Искомый минимум (то есть минимум по всем возможным парам (множество
, числа d_i)) надо вывести.

Вам ещё самый большой подъём делать.

Варианты того, что сегодня случится:

1. Получив нулевой рейтинг, codeforces воспримет тебя как только что зарегистрированного участника (у них тоже нулевой рейтинг), и со следующего раунда тебе придётся по новой идти к нулю с 1500.

2. Рейтинг станет отрицательным.

3. Ты станешь топ1, так как случится переполнение (если для хранения рейтинга используется тип данных вроде usnigned int):

unsigned int a = 13;

a -= 40;

cout << a << endl;

Вывод: 4294967269.

а что если...

no it will be :D

how will be destiny of worse ?

I think users didn't find any specific problem in the text of the blog entry or ... to talk! Everything was ok :)

Where is scoreboard for out of competition participants?

Really?

UPD. same in G++ 4.7 w/o C++0x

If you'll increase both numbers by more than 1e5, then product will increase by more than 1e10. But it is clear that you can get better answer, so you may check only all possibilities of increasing one of numbers by 0..1e5, and for every such possibility calculate required increasing of second number.

Вроде нет. Дерево 4->3. Документ приходит 3, 4й его не подписывал, но в одном мн-ве.

DP[i][j] — how many ways to solve first i points while having j open segments.

You have following moves at position i:

• close some of previous segments, don't open new (j+1 ways to choose segment to close)
• close some of previous segments, open new (j ways to choose segment to close)
• open segment and close it in same cell (1 way)
• open segment and don't close anything here (1 way)
• neither open nor close segment here (1 way)

And for every possibility you should check that number of segments covering position i after such move is h-a[i];

Answer will be in DP[n][0] (you solved all points, all segments were closed).

A simple linear solution. Consider the sequence b_i = h - a_i. If some two b_i, b_i + 1 differ by more than one, the answer is 0, since some two blocks begin or end in the same position.

Otherwise the answer is the product of values val_{(i, i + 1)}:

1. if b_i - 1 = b_i + 1, then we must end one of the b_i - 1 blocks. This can be chosen in b_i - 1, so val_{(i, i + 1)} = b_i;
2. if b_i - 1 = b_i, then we can end any of b_i - 1 blocks that still continue at position i - 1, and start a new block at position i. Or we can continue all of the blocks. So val_{(i, i + 1)} = b_i + 1;
3. if b_i - 1 = b_i - 1, we should begin a new block, so val_{(i, i + 1)} = 1;

Выведите три целых числа s, a1 и b1 (a ≤ a1; b ≤ b1) RTFM)

Yeah, I was confused about how to solve (a + x)(b + y) ≥ 6n where x and y are the number by which a and b are incremented. I tried to solve this for most of the time and I couldn't concentrate on problem C because I couldn't solve B!

A lot of us tried a greedy approach or maths, making it seem tough, but a brute force approach would have solved this.

As pointed out by I_love_Tanya_Romanova and aaaaaaaaaaaaaaaaaaaaaaab in the comments, both numbers cannot exceed 1e5 (LeBron's idea) or sqrt(6*n) (AvadaKedavra's idea). You just check a or b for all possibilities from 0 to 1e5 or sqrt(6*n) and calculate the required increase of the second number.

I think this time problem B was one of the hardest problem B's I have ever not solved...

Thanks for this. I should not be happy for solving the C question for the first time. :(

Congrats, I too had my best performance so far today! Solved E for first time! :)

Not sure if that's the cause but a thing I notice is you do not return 0 in the end of the function, so I suppose the returned value is undefined, therefore it may return true at some moment?

I guess they are struggling with assigning white color to worse.

да и цвета для него нет.

Probably worse's today achievement completely distorted the global rating update system.

Me too... http://codeforces.net/contests/with/Tudor

Wow , nice submission id 7774444

Это все worse сломал, скоро админинстрация починит, наверное

UPD: О, ты уже фиолетовый. Странно, я еще нет

there are many question like this with weak tests... anyway after this time if i cant solve a problem efficent i will send a naive solution :|

Can you give one?

You are a candidate master, but it seems that worse broke the rating system by getting negative rating (thus not fitting into the 0 — 1199 gray rank, but in a new color — white). Hopefully once it gets fixed you will be promoted to candidate master.

There is a bug with the rating/rank system. He had 1472 rating before Round #266 and got promoted to purple after the competition. Check his profile.

If a >= sqrt(6n) and b >= sqrt(6n), then a*b >= 6n; in this case, do nothing. Let a be the smaller of the two input numbers, and b be the larger of the two.

One trivial solution is to increase b until the room is big enough. E.g. if a = 10, b = 11, 6n = 1001 (somehow): then the trivial solution is 10*101 = 1010. Then your "overflow" is at most a, which as we said was <= sqrt(6n). Let TRIVIAL be the value of this trivial solution, i.e. in this case, 1010.

Therefore, the optimal solution has "overflow" at most a. Suppose that the optimal solution is x*y, with x <= y (WLOG). Then x <= sqrt(6n) + 1, because otherwise, x*y > (sqrt(6n)+1)*(sqrt(6n)+1) >= 6n + 2sqrt(6n) > 6n + a >= TRIVIAL, therefore the solution was non-optimal.

What we have shown is: you are guaranteed that an optimal solution exists with at least the smaller number being less than sqrt(6n). It is possible that one of the two is larger, though, e.g. 1*6n = 6n. However, your goal is only to find the smaller number, through the following method.

Fix w between 1 and sqrt(6n). For every w, let h be the smallest integer s.t. w*h >= 6n, i.e. h = ceil(6n/w). Keep track of the best value you've found so far. Then, you iterate through sqrt(6n) < 10^5 possible values of w, and for every such w, your computation is constant time, so your algorithm is linear in sqrt(6n).

Similar is happening with me too. My submission gives answer as 2041 for input test case 2. However on ideone and my local compiler, answer is 1.