Разбор Codeforces Round #322 (Div. 2)

Правка ru15, от fcspartakm, 2015-09-25 16:10:45

581A — Хипстер Вася

Первое ответное число (количество дней, которое Вася сможет быть одет по моде) это min(a, b), так как каждый из этих дней он будет надевать по одному красному и по одному синему носку.

После этого у него останутся либо только красные носки, либо только синие носки, либо не останется носков вовсе. Поэтому второе ответное число это max((a - min(a, b)) / 2, (b - min(a, b)) / 2).

Асимптотика решения — O(1).

581B — Элитные дома

Данная задача решается следующим образом. Пойдем по массиву справа налево и будем поддерживать в переменной maxH максимальную высоту дома, который мы уже рассмотрели. Тогда ответом для i-го дома будет число max(0, maxH + 1 - hi), где hi количество этажей в i-м доме.

Асимптотика решения — O(n), где n — количество домов.

581C — Три логотипа

Данная задача решается несколькими способами, рассмотрим один из них.

Для начала подсчитаем суммарную площадь s данных нам прямоугольников. Тогда сторона ответного квадрата это sqrt(s). Если sqrt(s) не целое число, выводим -1. Иначе сделаем следующее.

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

Для каждого из добавляемых прямоугольников сделаем следующее — найдем самую верхнюю левую свободную клетку free в квадрате c (напомним, что мы также перебираем, поворачиваем ли мы прямоугольник на 90 градусов или нет). Попытаемся наложить текущий прямоугольник в квадрат c, причем его левый верхний угол должен совпадать с клеткой free. Если текущий прямоугольник полностью помещается в квадрат c и не накладывается на уже занятую каким-то другим прямоугольником клетку, заполним соответствующие клетки в квадрате c нужной буквой.

Если после добавления всех трех прямоугольников не нарушилось ни одно из условий и весь квадрат c оказался заполненным мы нашли ответ — выводим квадрат c.

Если ответ не нашелся ни для одной перестановки прямоугольников — выводим -1.

Для произвольного количества прямоугольников k асимптотика решения — O(k! * 2k * s), где s — суммарная площадь заданных прямоугольников.

Также данная задача для 3 прямоугольников имеет решение с разбором случаев с асимптотикой O(s), где s — суммарная площадь заданных прямоугольников.

581D — Развитие навыков

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

Отсортируем заданный массив следующим образом — из двух чисел левее должно стоять то, к которому нужно добавить меньше единиц улучшений, чтобы оно стало кратно 10. Например, если исходный массив {45, 30, 87, 26}, то после сортировки он должен выглядеть следующим образом — {87, 26, 45, 30}.

Теперь проитерируемся по отсортированному массиву слева направо по i от 1 до n. Пусть cur = 10 - (aimod10). Если cur ≤ k, присвоим ai = ai + cur, а из k вычтем cur, иначе, если cur > k выйдем из цикла.

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

Осталось посчитать ответ ans — проитерируемся по массиву по i от 1 до n и присвоим ans = ans + (ai / 10).

Асимптотика решения — O(n * log(n)), где n количество заданных навыков героя.

581E — ???

581F — Зубликанцы и мумократы

Для решения задачи посчитаем 2

Теги round, div2, 322

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru20 Русский fcspartakm 2015-09-28 14:02:11 0 (опубликовано)
en24 Английский fcspartakm 2015-09-28 12:09:42 67
ru19 Русский fcspartakm 2015-09-28 12:09:09 52
en23 Английский fcspartakm 2015-09-28 11:44:25 1251
en22 Английский fcspartakm 2015-09-28 11:26:03 19 Tiny change: ' $nv$.\n\nВторой с' -> ' $nv$.\n\nThe second case: \nВторой с'
en21 Английский fcspartakm 2015-09-28 11:24:50 1646
en20 Английский fcspartakm 2015-09-28 11:07:13 424
en19 Английский fcspartakm 2015-09-28 11:02:23 462
en18 Английский fcspartakm 2015-09-28 10:49:04 718
en17 Английский fcspartakm 2015-09-28 10:40:17 223
en16 Английский fcspartakm 2015-09-28 10:33:11 3122
en15 Английский fcspartakm 2015-09-28 10:31:30 664
en14 Английский fcspartakm 2015-09-28 10:18:15 563
en13 Английский fcspartakm 2015-09-28 10:07:03 123
en12 Английский fcspartakm 2015-09-28 09:57:25 477
en11 Английский fcspartakm 2015-09-28 09:50:45 2047
ru18 Русский fcspartakm 2015-09-28 09:44:09 5082
ru17 Русский fcspartakm 2015-09-28 09:28:09 53
en10 Английский fcspartakm 2015-09-28 09:26:00 2114
ru16 Русский fcspartakm 2015-09-28 09:24:06 2118
ru15 Русский fcspartakm 2015-09-25 16:10:45 56
en9 Английский fcspartakm 2015-09-25 14:10:24 1 Tiny change: 'e followin — w' -> 'e following — w'
en8 Английский fcspartakm 2015-09-25 14:08:26 0 Tiny change: ' degrees ot not (we c' -> ' degrees or not (we c'
en7 Английский fcspartakm 2015-09-25 14:08:26 2 Tiny change: ' degrees ot not (we c' -> ' degrees or not (we c'
en6 Английский fcspartakm 2015-09-25 14:07:35 2756
en5 Английский fcspartakm 2015-09-25 13:51:07 2 Tiny change: ' to iterato on array ' -> ' to iterate on array '
en4 Английский fcspartakm 2015-09-25 13:50:34 532
en3 Английский fcspartakm 2015-09-25 13:17:49 703
en2 Английский fcspartakm 2015-09-25 13:08:32 530
en1 Английский fcspartakm 2015-09-25 13:04:29 4088 Initial revision for English translation
ru14 Русский fcspartakm 2015-09-25 12:36:42 8
ru13 Русский fcspartakm 2015-09-25 12:36:00 941
ru12 Русский fcspartakm 2015-09-25 11:51:25 4
ru11 Русский fcspartakm 2015-09-25 11:51:12 1 Мелкая правка: 'вадрате $c (напомним' -> 'вадрате $c$ (напомним'
ru10 Русский fcspartakm 2015-09-25 11:50:57 47
ru9 Русский fcspartakm 2015-09-25 11:49:20 1 Мелкая правка: 'mutation()$, а такж' -> 'mutation())$, а такж'
ru8 Русский fcspartakm 2015-09-25 11:48:50 2 Мелкая правка: 'ощью $next/_permutati' -> 'ощью $next\_permutati'
ru7 Русский fcspartakm 2015-09-25 11:48:37 1
ru6 Русский fcspartakm 2015-09-25 11:48:16 1510
ru5 Русский fcspartakm 2015-09-24 17:35:56 319
ru4 Русский fcspartakm 2015-09-24 17:26:14 2 Мелкая правка: '------\n\n[581D ' -> '------\n\n\n[581D '
ru3 Русский fcspartakm 2015-09-24 17:25:35 337
ru2 Русский fcspartakm 2015-09-24 17:23:17 53
ru1 Русский fcspartakm 2015-09-24 17:22:02 996 Первая редакция (сохранено в черновиках)