Thank you )

Кажется, Вы можете писать этот тур вместе со всеми.

у меня такое зашло. заполним все как шашки. потом пока не заполнили нужное количество, ищем клетку с мин количеством соседей и туда заселяем). ну и потом перекрасим каждую клетку в другой цвет и опять так сделаем и выберем минимум.

Зашла такая ерунда (по крайней мере, не доказал ее): раскрасим доску по-шахматному, сначала ставим жителей на белые клетки, а когда они закончатся, жадно на остальные (от клеток с наименьшим количеством белых соседей к клеткам с наибольшим количеством), потом наоборот. Минимум из ответов для этих способов будет ответом на тест.

Решение за O(1): Если n ≤ (r * c + 1) / 2, то ответ 0. Иначе давайте выбирать, какие клетки сделаем свободными. Раскрасим клетки в шахматном порядке. Все свободные клетки будут одного цвета. Переберём, какой именно цвет, потом жадно сделаем свободными сначала внутренние клетки, потом клетки, лежащие на границе, но не в углу, потом клетки, лежащие в углу.

Will Round 1A also appear in a Gym? If not Mike, could someone with trainer permissions add it? Thanks.

Can someone help me, how can I see failing test case? Thanks

edit: I found the problem 5 3 9 -> 3 (I had 4)

You make it sound too simple...
congratulations

I reduced this problem to the following one. Select M edges from the graph so that they have minimal number of incident vertices, but did not know how to solve it. Any ideas how one can tackle this problem?

Glad I'm not the only one. It felt a bit dirty..

Pattern for A? I don't see any easy-to-observe-and-hard-to-come-up observations here. My solution's main ideas were "You have to go through 10^k - 1 and 10^k for valid k's", "If 10|n, then ans(n) = 1 + ans(n - 1)" and "If I have a digit which is a positions from left and b positions from right I need to perform digit·10^min(a, b) operations" and "Reverse is needed unless n looks like 1000...003454, where that 100...00 part is at least as long as half of length"

rng_58 Can you explain your solution of C ?

I guess that it is some fake Gennady.Korotkevich, since the original tourist ™ passes to the finals automatically as winner of the previous year.

Да, и так для каждого разряда.

Еще нужно учитывать, что правая часть иногда 0

Я сначала набирал максимальное 10^k ≤ n, а потом уже так наращивал половины.

переобозначим n — количество людей

Заметим, что если наша скорость inf = 360/0, то ответ n.

Посмотрим, при каких скоростях меняется ответ.

Если скорость равна 360/ time * (360LL — d), то ответ уменьшается на 1(мы не успеваем догнать человека)

Если скорость равна 360/time * (360LL — d + 360 * j), то ответ увеличивается на 1(человек успевает нас догнать на 1 раз больше).

Теперь для простых тестов: положим все эти штуки (нет смысла брать больше чем 2n для одного человека) в массив/мап и выберем при какой скорости минимум.

Для сложного теста: эмулируем тоже самое с помощью очереди с приоритетами, тут уже нет смысла брать больчем чем 2n суммарно

Мой код из дорешки http://ideone.com/kaVERe

First you want to have same number of digits as n. So, you want to move 1->10->100->.. Let's say you have d digits in total. The best strategy is to move to 100..099..9(d/2 times 9) then reverse this to 99..9(d/2 times)0..01 and add 99..9(ceil(d/2) times) to reach 100..0(d+1 digits).

After that, you would want to make transformations such that, after reverse you have same prefix as n or lesser than that. For example, if you have 10000..0(d+1 digits) and n is of from n0, n1, ..nd, then you have to try for all prefixs n0, ..ni and make 100..ni, ni - 1, ..n0. After that apply reverse to get n0, n1, .., ni00..1. You will have to add ni+1,..nd(suffix) — 1. Make sure that the add component is greater than 1, if it is zero, substract one from prefix and add 1 in the MSD of suffix.

I only knew that the flip cannot increase the digit of a number, so must go from 1-->10-->100... But then I have totally no idea...

Also, I do not know if this is important, but will there be a unique optimal path from number a to number b (a < b), that some number c is in the path and c > b > a?

For example, from 18 to reach 28, will path like ...18-->81-->82-->28 be a unique and optimal one?

From A-small, I think the answer is No, but I cannot figure out why...

BTW, I checked your code, and there's at least one flaw in your rust template. In this line:

io::stdin().read_line(&mut s).unwrap();

io::stdin() is protected by mutex, and its read_line() function is implemented like this:

lock mutex
read_line() from internal buffer
unlock mutex

You can lock it one time and read everything directly from internal buffer:

let stdin = io::stdin();
let buf = stdin.lock();
...

this can lead to significant speedup.

Congratulations! you should notice that there are some people had advanced to next round ranked in 1000th! ^_^

Check the scoreboard again. :)

Practice on round 1C from 2014 and 2013. For the preparation of the round, maybe this video will help you. Mimino mentions this idea of generating the first elements of the series, to detect a pattern. Good luck!