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

Правка ru1, от Edvard, 2016-08-25 01:08:13

710A - Ходы короля

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

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

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

710B - Оптимальная точка на прямой

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

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

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

710C - Магический нечётный квадрат

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

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

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

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

Теги educational round 16, editorial

История

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