Codeforces Round #444 (Div. 2) Editorial

Revision ru3, by Denisson, 2017-11-04 18:50:43

887A - Div. 64

Автор: .tx.

Если в строке нет единиц, то ответ "NO", так как оставшееся число должно быть положительным. Иначе найдем самую левую единицу и проверим, что после нее есть хотя бы 6 нулей.

Решение: 32056640.

887B - Cubes for Masha

Автор: .tx.

Ответ никогда не превосходит величины 98. Переберем числа от 1 до 99 и найдем первое такое, что его нельзя собрать из кубиков.

Решение: 32056754.

887C - Solution for Cube

Автор: .tx.

Возможных вариантов входных данных, на которые ответ "YES", не более 12, не учитывая перестановки цветов. Их все можно было записать в массив.

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

Решение: 32056890. Denisson

Решение: 32056905. .tx

887D - Ratings and Reality Shows

Автор: .tx.

Посчитаем два массива префиксных сумм на событиях данных во входных данных. Один по значениями (a, b), другой со значениями (c, d). Ответом является момент времени 0 или момент сразу после какого-то из событий данных в задаче. Воспользуемся методом двух указателей. Один указатель будет показывать после какого события V мы хотим устроить ток-шоу, а другой на момент времени сразу после его окончания. Тогда мы можем устроить ток-шоу, если минимум из префиксных сумм на значениях (c, d) от элементов между указателями не меньше, чем разность префиксных сумм на значениях (a, b) и (c, d) от элемента V. Также нужно не забыть проверить, что рейтинг Изабеллы не стал отрицательным раньше проведения ток-шоу.

Решение: 32057284.Denisson

Решение: 32057313..tx

887E - Little Brother

Авторы: .tx, Denisson.

Центр искомой окружности лежит на серединном перпендикуляре к отрезку AB, где A, B — точки данные в условии. Если окружность с центром в середине отрезка и радиусом половины длины отрезка подходит, то она будет являться ответом. Иначе переберем по какую сторону будет лежать центр искомой окружности относительно прямой AB. Каждая изначально нарисованная окружность блокирует непрерывный интервал допустимых значений для искомой окружности. Границы этого интервала можно найти бинарным поиском. Теперь необходимо найти минимальное незаблокированное значение для радиуса. Это можно сделать, например, с помощью метода сканирующей прямой.

Решение: 32057661.Denisson

Решение: 32057674..tx

Решение: 32057685. [submission:cdkrot]

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Denisson 2017-11-05 10:30:48 32
en3 English Denisson 2017-11-04 22:40:31 3 Tiny change: ' an array ai we can ch' -> ' an array $a_i$ we can ch'
en2 English Denisson 2017-11-04 22:37:36 15 Tiny change: '1-04]\n\n[Решение.](https:/' -> '1-04]\n\n[Solution.](https:/'
en1 English Denisson 2017-11-04 22:21:02 4836 Initial revision for English translation
ru8 Russian Denisson 2017-11-04 20:14:15 507
ru7 Russian Denisson 2017-11-04 19:17:42 5
ru6 Russian Denisson 2017-11-04 19:12:46 178 Мелкая правка: '#Еще раз п' -> '###Еще раз п' (опубликовано)
ru5 Russian Denisson 2017-11-04 19:11:22 122
ru4 Russian Denisson 2017-11-04 19:09:42 1736 Мелкая правка: 'ь ровно одно меньше, тогда пр' -> 'ь ровно один такой элемент, тогда пр'
ru3 Russian Denisson 2017-11-04 18:50:43 915
ru2 Russian Denisson 2017-11-04 18:32:37 1541 Мелкая правка: 'enisson]\nРешение:' -> 'enisson]\n\nРешение:'
ru1 Russian Denisson 2017-11-04 18:01:18 365 Первая редакция (сохранено в черновиках)