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

Правка ru1, от Edvard, 2016-03-02 01:03:34

632A - Grandma Laura and Apples

Задача предложена пользователем unprost.

Рассмотрим на процесс с конца. Последний покупатель всегда покупает половину яблока и половину получает бесплатно (поэтому последняя строка на самом деле всегда равна halfplus). Далее каждый покупатель удваивает текущее количество яблок и возможно прибавляет к нему единицу. Таким образом, нам просто задано бинарное представление числа записанное с конца. Для подсчёта ответа нужно просто с конца восстанавливать количество яблок попутно, вычисляя сумму денег.

С++ solution by me

С++ solution by unprost

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

Теги учебный раунд 9, разбор задач

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Edvard 2016-03-03 02:14:37 138
ru12 Русский Edvard 2016-03-03 02:04:28 140
ru11 Русский Edvard 2016-03-02 17:52:11 122
en6 Английский Edvard 2016-03-02 17:51:16 2062
en5 Английский Edvard 2016-03-02 17:29:46 963
en4 Английский Edvard 2016-03-02 17:17:52 1105
ru10 Русский Edvard 2016-03-02 17:05:02 180
en3 Английский Edvard 2016-03-02 17:03:47 748
en2 Английский Edvard 2016-03-02 16:58:00 686
ru9 Русский Edvard 2016-03-02 03:33:59 39
en1 Английский Edvard 2016-03-02 03:33:00 1838 Initial revision for English translation
ru8 Русский Edvard 2016-03-02 03:24:21 2035 Мелкая правка: '_2},\ldots\n,a_{k_m,j}' -
ru7 Русский Edvard 2016-03-02 02:55:42 4
ru6 Русский Edvard 2016-03-02 02:46:07 2299
ru5 Русский Edvard 2016-03-02 02:11:36 2
ru4 Русский Edvard 2016-03-02 02:08:48 870 Мелкая правка: 'руков [used:pitfall].' -
ru3 Русский Edvard 2016-03-02 01:36:50 1379 Мелкая правка: 'ость: $O(n logn l)$, где $l$ --- наиб' -
ru2 Русский Edvard 2016-03-02 01:14:49 776
ru1 Русский Edvard 2016-03-02 01:03:34 748 Первая редакция (опубликовано)