Разбор задач Educational Codeforces Round 16

Revision ru2, by Edvard, 2016-08-25 01:24:39

710A - King Moves

Легко видеть, что в задаче возможно всего три случая. Если король находится углу доски, то у него 3 возможных хода. Если он стоит на краю доски, то у него 5 возможных хода (если конечно он не в углу). Наконец, если король не стоит на краю доски, то у него всего 8 возожных хода.

Решение на С++

Сложность: O(1).

710B - Optimal Point on a Line

Легко видеть, что ответ всегд находится в одной из заданных точек (функция суммарного рассояния между парой заданных точек монотонна). Далее можно либо для каждой точки посчитать суммарное расстояние и выбрать оптимальную точку, либо заметить, что ответом является точка находящяяся посередине в отсортированном списке заданных точек (если точек чётное количетсво то слева посередине). Последний факт легко доказыватся, но можно это и не делать и сдать задачу первым способом.

Решение на C++

Сложность: O(nlogn).

710C - Magic Odd Square

Задачу предложил Resul Hangeldiyev Resul.

Решение задачи легко получить из второго примера. Легко видеть, что если расставить все нечётные числа в виде ромба посередине квадрата, то мы получим магический квадрат.

Решение на C++

Сложность: O(n2).

710D - Two Arithmetic Progressions

Эту задачу я уже давно хотел дать на раунд, она мне казалась очень стандартной, но я недооценил её сложность.

Запишем уравнение, которое описывает все решения задачи: a1k + b1 = a2l + b2 → a1k - a2l = b2 - b1. Имеем линейное диофантово уравнение с двумя неизвестными: Ax + By = C, A = a1, B =  - a2, C = b2 - b1. Его решение имеет вид: , где последнее уравнение решается с помощью расширенного алгоритма Евклида, а p произвольное целое число. Далее нам нужно удовлетворить двум условиям: и . Поскольку мы знаем знаки чисел A и B, последние уравнения задают отрезок возможных значений для переменной p, длина этого отрезка и является ответом на задачу.

Решение на C++

Сложность: O(log(max(a1, a2))).

Tags educational round 16, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Edvard 2016-08-30 01:56:47 4835
en5 English Edvard 2016-08-30 01:11:02 1545
en4 English Edvard 2016-08-30 00:41:38 1965
en3 English Edvard 2016-08-30 00:04:38 2 Tiny change: 'ncorner than the answ' -> 'ncorner then the answ'
en2 English Edvard 2016-08-30 00:03:23 945
en1 English Edvard 2016-08-29 23:57:58 1839 Initial revision for English translation
ru4 Russian Edvard 2016-08-25 01:51:17 4900 Мелкая правка: 'ность: $O(slen\cdot logm)$, гд' -
ru3 Russian Edvard 2016-08-25 01:37:55 1633
ru2 Russian Edvard 2016-08-25 01:24:39 1967 Мелкая правка: 'уравнение получается решается ' -> 'уравнение решается '
ru1 Russian Edvard 2016-08-25 01:08:13 2829 Первая редакция (опубликовано)