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

Revision ru2, by Edvard, 2016-06-14 01:38:58

678A - Johny Likes Numbers

Задачу предложил Әбдірахман Исмаил bash.

Нам нужно найти минимальное x, что x * k > n. Легко видеть, что . Для подробного знакомства с математическими функциями пола и потолка я рекомендую книгу авторов Грэхем, Кнут, Паташник "Конкретная математика". В этой книге есть отдельная глава, посвящённая этим функциям и их свойствам.

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

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

678B - The Same Calendar

Задачу предложил Артур Яворски KingArthur.

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

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

Сложность: O(1) — легко видеть, что количество итерация не превосходит небольшой константы.

678C - Joty and Chocolate

Задачу предложил Sheikh Monir skmonir.

Легко видеть, что в оба цвета мы можем покрасить доски с номерами кратными lcm(a, b) — НОК чисел a и b. Очевидно, что эти доски выгоднее красить в более дорогой цвет. Таким образом, ответ равен: .

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

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

Tags учебный раунд 13, разбор задач

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Edvard 2016-06-17 00:08:58 71
en6 English Edvard 2016-06-17 00:06:45 2252
en5 English Edvard 2016-06-16 01:55:47 3667
en4 English Edvard 2016-06-16 01:45:55 1547
en3 English Edvard 2016-06-16 01:38:08 841
en2 English Edvard 2016-06-16 01:35:20 941
en1 English Edvard 2016-06-16 01:19:27 632 Initial revision for English translation
ru9 Russian Edvard 2016-06-16 00:45:21 76 Мелкая правка: ' summary="C++ solution">\n~~~~~\' -> ' summary="Решение на C++">\n~~~~~\'
ru8 Russian Edvard 2016-06-16 00:40:51 307
ru7 Russian Edvard 2016-06-15 00:49:41 3519 Мелкая правка: 'тьего типа отсортиру' -> 'тьего типа, отсортиру'
ru6 Russian Edvard 2016-06-14 23:38:12 51 Мелкая правка: 'ть: $O(log max(a, b))$.\n\n##' -> 'ть: $O(log(max(a, b)))$.\n\n##'
ru5 Russian Edvard 2016-06-14 23:37:44 62 Мелкая правка: 'ность: $O(1)$.\n\n###' -> 'ность: $O(log max(a, b))$.\n\n###'
ru4 Russian Edvard 2016-06-14 23:36:58 1541
ru3 Russian Edvard 2016-06-14 23:20:12 2276 Мелкая правка: '[1, 1]]$, v=[0, 1]$.' -
ru2 Russian Edvard 2016-06-14 01:38:58 832 Мелкая правка: 'т равен: $\lfloor p\frac na \' -> 'т равен: $p\lfloor \frac na \'
ru1 Russian Edvard 2016-06-14 01:21:42 1580 Первая редакция (опубликовано)