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

А ты хоть дай один контест. Спасибо авторам!

as usual

правильно

Мне не очень понравилось. Не люблю задачи на строки, причем такие, где надо не думать, а надо тупо реализовывать, что сказано. Не люблю, когда решение очевидно, но надо писать море кода (как, например, в С). Побольше бы идейных задач. Спасибо!

Две задачи на реализацию. Зачем? За что?

Не знаю, как доказывается выпуклость функции, и на контесте я это решение не реализовал, но...

Очевидно, k5 мы можем выкинуть из аргументов функции. Единственный момент: для k3 и k4 должно выполняться равенство s — (c3 * k3 + c4 * k4) = 0 (mod c5). Заметим, что c5 у нас небольшое, так что для всех k3 (mod c5) посчитаем массив всех k4 (mod c5), таких, что указанное выше равенство выполняется. Мысленно "размотаем" эти массивы до бесконечности и загоним с их помощью тернарники.

UPD. Вот код моего решения по описанной выше идее.

Самая интересная задача. Зарплату для 4-шников можно перебрать, а дальше или решить диофантово, или тупо перебрать решение влоб, что тоже быстро, так как если решение есть, оно будет повторятся с шагом НОК(c1,c3). Единственное, что я не учел, это то, что если решения нет, то перебирать его не следует.

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

c[0], c[1], c[2] — количество 3, 4, 5. нужно найти k[0], k[1], k[2]. Несколько кусков решения: 1) перебираем k[1] 2) теперь нужно научиться решать k[0] * c[0] + k[2] * c[2] = s — c[1] * k[1] это диофантово уравнение a * x + b * y = z. делим a, b, z на нод(a, b). находим решение a * x + b * y = 1, домножаем на z. мы нашли некое решение этого уравнения. чтобы получить другие нужно прибавить к x += b / (a, b), к y += — a / (a, b); запомнили разности и одно решение. вспоним о нем позже.

3) давайте-ка теперь вспомним про три неравенста: 0 <= k[0] <= k[1] <= k[2]. обозначим x за k[0] * c[0]. получаем три неравенства на x (сумма k[i] * c[i] = s, k[1] * c[1] мы знаем). они преобразуются в это (ручка + бумажка): x приладлежит [0...min(s — c[1] * k[1] — k[1] * c[2], k[1] * c[0])]. запомнили.

4) теперь вспомним про странную функцию, которую нам дали. там какие-то суммы модулей. но также abs(x) = max(x, -x). расскрываем тогда эту функцию, как максимум 4ех (и все выражаем через x = k[0] * c[0]):

f = max(s — 3 * k[1] * c[1], -(s — 3 * k[1] * c[1]), (2x + k[1] * c[1] — s), -(2x + k[1] * c[1] — s)). По сути у нас 3 функции, все линейные, одна горизонтальная. нужно найти минимум их максимума. Как это сделать? Нужно перебрать те bestx, при которых какие-то из этих линейных становятся равны. теперь все просто: перебираем три bestx, находим лежащие в упомянутом отрезке большие bestx и меньше либо равные.

Use this link.

http://www.codeforces.com/blog/entry/4696#comment-95880

You're repeating the same bugs, with almost two similar input formats :S

You have a bad memory, Dude!

Смотря как код писать, у некоторых реализации достаточно короткие.

Ты же на Java пишешь, а там так классно инпут парсится. Я посабмитил три легкие задачи и обнаружил себя на первом месте)

I didn't solve it at the end, but my idea was to register the number of filled seats for every diagonal in a Fenwick Tree. This would give me the number of filled seats at a distance d from the preferred position in logarithmic time for every d.

With that value I can check if there is a free spot at minimum distance, and then just look for it with brute force.

This would give a O(log(n) n k) algorithm, I guess it should fit in time.

Ага, если б так же быстро рейтинг обновили. UPD. Обновили.

private String next() throws IOException {

while (tokens == null) {

        tokens = new StringTokenizer(input.readLine(), "\t\n\r\n(), ");

    }

    if (!tokens.hasMoreTokens()) {

        tokens = null;

        return null;

    }

    return tokens.nextToken();

}

А сколько раундов было проведено по вашим задачам, чтобы давать указания авторам какими они должны быть?

за счет правила про разницу очков иногда просто победы не хватает, нужна победа с крупным счетом

слово else при считывании не написал и минус)спасибо, всех с днем молодежи!

Кстати а кого выбирают если все условия приоритета одинаковые, ведь не сказано что имена команд различны!

The names of teams team1 and team2 are non-empty strings, consisting of uppercase English letters, with length of no more than 20 characters; goals1, goals2 are integers from 0 to 9.

What else do you need?

Потому что требуется минимальная разница между количеством забитых командой Берляндии и забитых команде Берляндии.

потому что при неоднозначном выборе нужно было вывести тот счет, в котором разница голов меньше. Поэтому иногда лучше счет 1:0, 5:3, 8:1 и другие

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

в случае неоднозначного выбора требуется выбрать счет X:Y, при котором величина X - Y принимает наименьшее значение;

No. The 66668th is 551 1028. You can see my submission: 1830110

Кажись, что одну штуку перебираем, а остальные ищем алгоритмом эвклида.

См. мой пост выше.

K*(N+M) may work in time.

меньше пропустить нужно

да можно было и вничью сыграть, так что врядли на это намекалось

Там же написано, что все совпадения случайны.

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

X > Y, that is, Berland is going to win this game; 

X must be greater than y

No, You are wrong: "if it is still impossible to come up with one score, you should choose the score where value Y (the number of goals Berland misses) is minimum."

here: http://codeforces.net/blog/entry/4769 edit. fixed link