codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

478.md (11802B)


      1 Source: https://codeforces.com/blog/entry/14307
      2 
      3 [478A - Initial Bet](/contest/478/problem/A "Codeforces Round 273 (Div. 2)")
      4 
      5 Для решения задачи важно заметить, что в ходе игры количество монет на столе меняться не может. Суммарное количество монет на столе после того, как сделаны ставки, остается неизменным. Следовательно, разделив суммарное количество монет на столе на количество игроков, можно получить начальную ставку каждого из них. Если разделить без остатка невозможно, то такой итог игры невозможен. Стоит обратить внимание на то, что начальная ставка каждого из игроков должна быть отлична от нуля, следовательно, ноль никогда не может являться ответом.
      6 
      7 [478B - Random Teams](/contest/478/problem/B "Codeforces Round 273 (Div. 2)")
      8 
      9 Если переформулировать задачу в терминах теории графов, то ее можно сформулировать следующим образом: Имеется граф, состоящий из *n* вершин и *m* компонент связности. Внутри каждой компоненты связности каждая пара вершин этой компоненты связана ребром. Другими словами, каждая компонента связности является полносвязной. Какое наименьшее и какое наибольшее количество ребер может содержать такой граф? Рассмотрим процесс построения графа из *n* вершин и *m* компонент связности. Для начала предположим, что каждая из *m* компонент содержит ровно одну вершину. Остается распределить оставшиеся *n* - *m* вершин так, чтобы минимизировать или максимизировать количество ребер. Заметим, что при добавлении новой вершины в компоненту связности размера *k*, количество ребер увеличивается на *k* (новая вершина соединяется с каждой из уже существующих одним ребром). Следовательно, для того, чтобы минимизировать количество образованных ребер на каждом шаге, требуется каждый раз добавлять вершину в компоненту связности наименьшего размера. Если действовать согласно такой стратегии, то после распределения вершин по компонентам связности появится ![](https://espresso.codeforces.com/f2dd69fd7a1b67aa1fd1d3d893bb4e863c673845.png) компонент размера ![](https://espresso.codeforces.com/23bf9240219e1f4e57857064942c58e0a30a02e7.png) и ![](https://espresso.codeforces.com/c8af2c82914e21d3966b364d091f3ab39e4251c2.png) компонент размера ![](https://espresso.codeforces.com/a742da0bd78ccd90499f2053cc9404817940aa21.png). Аналогично, для того, чтобы максимизировать количество ребер, на каждом шаге необходимо добавлять очередную вершину в компонентну связности наибольшего размера. Если действовать согласно такой стратегии, то образуется одна компонента связности размера *n* - *m* + 1, оставшиеся компоненты связности будут состоять из одной вершины. Зная количество компонент связности и их размеры, можно посчитать общее количество ребер. Для полносвязной компоненты, состоящей из *k* вершин, количество ребер равняется ![](https://espresso.codeforces.com/76f5a76c24d5c9b5a7cde0307e6d8ab6c18a5833.png). Следует помнить про необходимость использовать 64-битный тип данных для хранения количества ребер, которое квадратично зависит от значения *n*.
     10 
     11 [478C - Table Decorations](/contest/478/problem/C "Codeforces Round 273 (Div. 2)")
     12 
     13 Рассмотрим ситуацию, когда величина *max*(*r*, *g*, *b*) - *min*(*r*, *g*, *b*) ≤ 1, в таком случае, очевидно, ответ равен ![](https://espresso.codeforces.com/1f4b6f58254684d5ca88ce39a85a2c14f96c3a7a.png). Мы всегда можем украсить столько столов тремя воздушными шарами разных цветов. Очевидно, что оставшееся количество шаров будет меньше трех и, следовательно, не может быть использовано для украшения стола в любом случае. Все оставшиеся случаи имеет смысл свести к ранее рассмотренному. Если есть один цвет такой, что количество шариков этого цвета больше, чем суммарное количество шариков для оставшихся двух цветов, то всега выгодно украшать стол двумя шарами этого цвета и одним шаром того из оставшихся цветов, которого больше на данный момент. Далее можно разными способами группировать операции и выполнять более одной операции за раз. Другим решением можно назвать тот факт, что ответ будет отличен от ![](https://espresso.codeforces.com/1f4b6f58254684d5ca88ce39a85a2c14f96c3a7a.png), но только тогда, когда *max*(*r*, *g*, *b*) ≥ 2·(*r* + *g* + *b* - *max*(*r*, *g*, *b*)), в таком случае ответ *r* + *g* + *b* - *max*(*r*, *g*, *b*). В этом случае шарики двух наиболее редких цветов закончатся раньше, чем шарики одного наиболее популярного, если украшать каждый стол с использованием двух шариков наиболее популярного цвета.
     14 
     15 [478D - Red-Green Towers](/contest/478/problem/D "Codeforces Round 273 (Div. 2)")
     16 
     17 Для начала можно заметить, что для того, чтобы построить красно-зеленую башню высоты *h* потребуется ![](https://espresso.codeforces.com/a1588b5905c62029684c7ec7d88ec2e5db459f0e.png) кубиков. Следовательно, высота полученной башни для заданных ограничений никогда не превысит 893. Эту высоту можно определить заранее, если предположить, что все кубики одного цвета. Попробуйте доказать это самостоятельно. Далее можно решить задачу с использованием динамического программирования. Пусть *F*(*t*, *r*) — количество способов собрать башню наибольшей высоты, если собрано *t* верхних этажей и остались незадействованными *r* красных кубиков. Среди аргументов функции нет количества оставшихся зеленых кубиков *g* — его можно однозначно определить из значений *t* и *r*: ![](https://espresso.codeforces.com/9172367fbab3e36cc71aece821cc3d875d389724.png), где *r*0 и *g*0 — изначальное количество красных и зеленых кубиков, соответственно. Ну а дальше следует рассмотреть лишь два перехода: пострить *t* + 1-ый уровень из красных или из зеленых кубиков: *F*(*t*, *r*) = *F*(*t* + 1, *r* - *t*) + *F*(*t* + 1, *r*). Очевидно, кешировать данные в массиве размера 893 × 2·105 — не лучшая затея. В таком случае можно подсчитывать значения функции для всех значений *t* от 0 до *h*, храня в памяти только значения для текущего значения *t* и для предыдущего, от которого оно будет зависеть.
     18 
     19 [478E - Wavy numbers](/contest/478/problem/E "Codeforces Round 273 (Div. 2)")
     20 
     21 Для решения этой задачи необходимо было заметить, что волнистых чисел на интервале от 0 до 107 намного меньше, чем 107. В таком случае можно решить задачу с использованием подхода meet-in-the-middle. То есть отдельно решить эту задачу для первых семи цифр ответа, и для последних семи цифр ответа. Для этого потребуется отдельно сгенерировать все волнистые числа на интервале от 0 до 107, которые начинаются с возрастания двух соседних цифр, и аналогичные волнистые числа, которые начинаются с убывания двух соседних цифр. Дальше для каждой первой половины мы можем посчитать *r**l* — ее остаток от деления на *n* и, затем, определить количество подходящих вторых половин, которые должны иметь остаток от деления равный ![](https://espresso.codeforces.com/e2c9a78d995efa6eca2addd398adabca7206004b.png).
     22 
     23 Для задачи было установлено ограничение времени равное 1.5 сек. На самом деле, если написать решение с подходом meet-in-the-middle достаточно оптимально, то решению потребуется гораздо меньше времени. [Приведенная авторская реализация](http://pastebin.com/DKhxef4N) ([8271836](/contest/478/submission/8271836 "Submission 8271836 by pkhaustov")) умеет решать аналогичную задачу для 1 ≤ *n*, *k* ≤ 1016 примерно за 2.5 сек.