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

Правка ru6, от fcspartakm, 2016-05-05 15:03:36

670A - Holidays

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

670B - Game of Robots

Для решения данной задачи будем перебирать сколько идентификаторов назовут роботы в порядке слева направо. Договоримся, что будем решать эту задачу в 1-индексации. Пусть текущий робот назовёт i идентификаторов, тогда если k - i > 0 выполним k = k - i и перейдем к следующему роботу, в противном случае, выведем a[k], где a[] — это массив с идентификаторами роботов, и закончим алгоритм.

670C - Cinema

Воспользуемся map-ом (назовём его cnt) и насчитаем, сколько учёных говорит на каждом языке (то есть cnt[i] должно быть равно количеству учёных, которые говорят на языке номер i). Заведём пару res, в которой будем хранить количество \textit{очень довольных} учёных и количество \textit{почти довольных} учёных. Изначально выполним присвоение res = makepair(0, 0). Переберем все фильмы, начиная с первого. Пусть текущий фильм имеет номер i. Тогда, если res < makepair(cnt[b[i]], cnt[a[i]]), выполним присвоение res = makepair(cnt[b[i]], cnt[c[i]]) и обновим ответ номером текущего фильма.

670D1 - Magic Powder - 1

Данную задачу с уменьшенными ограничениями можно решить следующим образом. Будем печь по одной печеньке до тех пор пока это возможно. Для каждой новой печеньки насчитаем val — сколько нужно волшебного порошка для её приготовления. Для этого переберём все ингредиенты, и для ингредиента номер i, если a[i] ≤ b[i] выполним присвоение b[i] = b[i] - a[i], в противном случае, выполним присвоение b[i] = 0 и val = val + a[i] - b[i]. После того, как мы перебрали все ингредиенты, если val > k, то больше печенек испечь мы не сможем. В противном случае, выполним присвоение k = k - val и перейдем к приготовлению следующей печеньки.

670D2 - Magic Powder - 2

Будем делать бинарный поиск по ответу. Пусть мы проверяем текущий ответ cur. Тогда целевая функция должна выглядеть следующим образом. Насчитаем в переменную cnt сколько грамм волшебного порошка нам нужно для приготовления cur печенек. Переберём все ингредиенты по очереди. Пусть текущий ингредиент имеет номер i. Тогда если a[icur > b[i] выполним присвоение cnt = cnt + a[icur - b[i]. Если после рассмотрения какого-то ингредиента cnt стало больше чем k целевая функция должна вернуть false. Если такого не произошло ни после какого ингредиента, целевая функция должна вернуть true.

Понятно, что если целевая функция вернула true нужно сдвинуть левую границу бинпоиска в cur, иначе нужно сдвинуть правую правую границу.

670E - Correct Bracket Sequence Editor

670F - Restore a Number

Теги div2, editorial, 350, разбор

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru14 Русский fcspartakm 2016-05-05 21:35:00 0 (опубликовано)
ru13 Русский fcspartakm 2016-05-05 21:31:11 2
en9 Английский fcspartakm 2016-05-05 18:51:14 2620
en8 Английский fcspartakm 2016-05-05 18:27:42 2234
en7 Английский fcspartakm 2016-05-05 18:07:04 334
ru12 Русский fcspartakm 2016-05-05 18:02:23 7 Мелкая правка: 'ть правую правую гр' -> 'ть правую гр'
en6 Английский fcspartakm 2016-05-05 18:02:09 1123
en5 Английский fcspartakm 2016-05-05 17:56:59 813
en4 Английский fcspartakm 2016-05-05 17:50:53 783
en3 Английский fcspartakm 2016-05-05 17:44:46 584
en2 Английский fcspartakm 2016-05-05 17:38:10 1000
en1 Английский fcspartakm 2016-05-05 17:32:35 6507 Initial revision for English translation
ru11 Русский fcspartakm 2016-05-05 17:13:38 1749
ru10 Русский fcspartakm 2016-05-05 15:46:58 1564
ru9 Русский fcspartakm 2016-05-05 15:09:44 2 Мелкая правка: ']$, где $a[]$ &mdash; ' -> ']$, где $a$ &mdash; '
ru8 Русский fcspartakm 2016-05-05 15:04:18 1 Мелкая правка: 'ше чем $k$ целевая ф' -> 'ше чем $k$, целевая ф'
ru7 Русский fcspartakm 2016-05-05 15:03:54 3
ru6 Русский fcspartakm 2016-05-05 15:03:36 766
ru5 Русский fcspartakm 2016-05-05 14:44:25 651
ru4 Русский fcspartakm 2016-05-05 14:23:34 631
ru3 Русский fcspartakm 2016-05-05 14:10:53 382
ru2 Русский fcspartakm 2016-05-05 14:04:26 569
ru1 Русский fcspartakm 2016-05-05 13:53:08 191 Первая редакция (сохранено в черновиках)