реализация

123
456
789

Беси может нажимать одну клавишу, две клавиши одновременно (имеющие общую сторону, всего 12 комбинаций), 4 клавиши одновременно, которые формируют квадрат (1245, 2356, 4578, or 5689).

Например, если телефонный номер 123659874, она может сэкономить время следующим образом:

1. Нажать 1 и 2 одновременно.
2. Нажать 3.
3. Нажать 6, 5, 9, 8 одноврменно.
4. Нажать 7 и 4 одновременно.

Однако при нажатии нескольких клавиш одновременно, цифры могут могут записаться в произвольном порядке. Например, после последнего нажатия (7 и 4 одновременно) может получиться 123596847 или 213659874

По заданной последовательности цифр, вычислите количество телефонных номеров, которые она может набрать, по модулю \(10^9+7\).

**Замечание: Время на тест для этой задачи 4s, в два раза больше чем обычно..**

На этой ферме имеется два амбара - один в поле \(1\), другой в поле \(N\). ФД хочет быть уверен, что имеется путь между двумя амбарами последовательностью дорожек. Оно готов построить до двух новых дорожек, чтобы добиться своей цели. Стоимость построения дорожки между полями \(i\) и \(j\) есть \((i-j)^2\).

Помогите ФД определить минимальную стоимость сделать так, чтобы амбары \(1\) и \(N\) стали достижимы друг для друга.

ФД планирует разделить множество дорог на несколько путей и делегировать ответственность за каждый путь специальному человеку. Чтобы избежать раздора, он хочет, чтобы все пути имели одинаковую длину. Он хочет узнать для каких длин существуют такие разбиения.

Более точно для каждого \(1 \leq K \leq N-1\), помогите ФД определить, могут ли дороги быть распределены на пути длиной ровно \(K\).

Каждый час корова или

• Останавливается, если трава в текущей ячейке уже съедена другой коровой.
• Съедает всю траву в текущей ячейке и перемещается на одну ячейку вперёд в своём исходном направлении.

Через некоторое время каждая корова оставит за собой колею пустых ячеек.

Если две коровы попадут одновременно на одну и ту же ячейку с травой, они поедят вместе и продолжат движение в своих направлениях в следующий час.

ФД не любит, когда корова прекращает пастись, и он хочет узнать, кто виноват в его остановленных коровах. Если корова \(b\) остановилась в ячейке, которую съела корова \(a\), тогда он считает, что корова \(a\) остановила корову \(b\). Более того, если корова \(a\) остановила корову \(b\), а корова \(b\) остановила корову \(c\), он считает, что корова \(a\) также остановила корову \(c\) (то есть отношение "остановила" транзитивно). Каждая корова "виновата" в количестве коров, которые она остановила. Для каждой коровы вычислите количество остановленных ею коров.

Чтобы было понятнее относительно направлений и координат, если корова в ячейке \((x,y)\) и двигается на север, то она попадёт в ячейку \((x,y+1)\), а если на восток - то в ячейку \((x+1, y)\).

В настоящий момент коровы выстроились в линию в порядке \(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\). Он хочет переупорядочить коров так, чтобы они стали в порядке \(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.

Фермера Джона слышит только корова, которая стоит перед ним. В этот момент ФД может сказать ей перейти на \(k\) позиций назад (\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит, двигаются вперёд, освобождая место для неё, в которое она и становится.

Например, пусть \(N=4\) и коровы стоят в таком порядке

 ФД: 4, 3, 2, 1 

Единственная корова, которая слышит ФД, это корова \(4\). Если он скажет ей сдвинуться на 2 позиции, порядок станет таким:

 ФД: 3, 2, 4, 1 

Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.

Определите последовательность инструкций (с минимальным их количеством), которые должен дать ФД, чтобы отсортировать всех коров.

Ферма описывается как \(N\) полей (\(1 \leq N \leq 10,000\)), последовательно пронумерованных \(1 \ldots N\), амбар находится в поле 1. Поля соединены \(M\) двунаправленными тропинками (\(N-1 \leq M \leq 50,000\)). С каждой тропинкой ассоциировано время её прохождения, и от любого поля имеется путь к амбару, состоящий из некоторого множества тропинок.

Поле \(i\) содержит \(c_i\) коров. Услышав колокол, все коровы двигаются к амбару так, чтобы потратить минимальное количество времени. Если имеется несколько путей с минимальным временем, коровы выбирают "лексикографически минимальный" путь. Например, путь через поля 7,3,6,1 лексикографически минимальнее, чем путь 7,5,1.

ФД хочет сократить общее время движения (сумму времён движения всех коров) как можно больше добавлением одной сокращающей тропинки, которая имеет время прохождения \(T\) (\(1 \leq T \leq 10,000\)), от амбара (поле 1) до другого поля, которое он выберет. Если корова встретится с этой сокращающей тропинкой на своём обычном пути, тогда корова пойдёт по этой тропинке, если в результате уменьшится время её прихода в амбар. Иначе, корова пойдёт по своему обычному маршруту, даже если бы она могла уменьшить своё время в пути, используя сокращающую тропинку.

Помогите ФД определить наибольшую величину уменьшения суммарного времени движения, которое он может достичь добавлением сокращающей тропинки.

Назовём позицию между элементами \(i\) и \(i+1\) массива \(A\) точкой разбиения если максимум из \(A[...i]\) не больше чем минимум \(A[i+1 \ldots]\). Беси помнит, что быстрая сортировка реорганизует массив так, чтобы у него появилась точка разбиения, а затем рекурсивно сортирует две стороны \(A[...i]\) и \(A[i+1 \ldots]\). Однако хотя она помнит, что все точки разбиения можно найти за линейное время, она забыла как в быстрой сортировке реорганизуется массив, чтобы быстро создать точку разбиения. Она решила использовать пузырьковую сортировку для решения этой задачи

Ниже приведен алгоритм Беси Сначала она написала простую функцию, которая делает один проход пузырьковой сортировки:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Рекурсивный код Беси для "быстрой" сортировки такой:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A) 
   divide A at all partition points; recursively quickish_sort each piece
}

Теперь Беси интересно, насколько быстро работает её код. Для простоты она считает, что её итерация работает линейно и поэтому она просто инкрементирует глобальную переменную work_counter внутри цикла текущим размером массива так, чтобы оценивать общую работу, выполненную алгоритмом.

По заданному входному массиву, предскажите финальное значение величины work_counter после завершения алгоритма quickish_sort.

1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой, затем корову 2 и затем корову 5.

2. Некоторые коровы могут настаивать, чтобы их доили в определённой позиции внутри порядка. Например, корова 4 может настаивать, чтобы её доили второй среди всех коров.

По счастью, ФД всегда может подоить своих коров в порядке, удовлетворяющем всем условиям.

К несчастью, корова 1 заболела, поэтому ФД хочет подоить эту корову как можно раньше, чтобы раньше отпустить её в амбар отдыхать и выздоравливать. Помогите ФД определить самую раннюю позицию, в которой можно будет подоить корову 1.

Игра Му-Му происходит на высокой узкой решётке из \(N\) ячеек в высоту и (\(1 \leq N \leq 100\)) и 10 ячеек в ширину. Вот пример для \(N = 6\):

0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

Каждая ячейка или пустая (обозначена 0) или содержит стог сена одного из 9 различных цветов (обозначенных символами 1..9). Гравитация вынуждает стоги сена падать вниз, поэтому никогда 0 не будет ниже, чем стог сена.

Две ячейки принадлежат одному и тому же связному региону, если они имеют общую вертикальную или горизонтальную сторону и один и тот же цвет, отличный от 0. Каждый раз, когда регион начинает содержать \(K\) или более ячеек, все его стоги сена исчезают - превращаются в 0. Если в один момент времени существует несколько таких регионов они исчезают все одновременно. Затем, гравитация может вынудить стоги сена заполнить некоторые из ячеек, которые стали нулевыми. В получившейся конфигурации могут снова образоваться региона размера не менее \(K\) ячеек. В этом случае они также исчезают (одновременно, если есть несколько таких регионов). Затем гравитация вновь двигает вниз стоги сена и процесс повторяется, пока есть хоть один регион, в котором не менее \(K\) стогов.

По заданной конфигурации доски для Му-Му вычислите финальную картинку доски после выполнения всех операций.

”„ е®зҐв ўлЎа вм Ї®¤¬­®¦Ґбвў® Є®а®ў, Ё § вҐ¬ Їа®ЁвҐаЁа®ў вмбп Ї® н⮬㠯®¤¬­®¦Ґбвўг, ўл§лў п Є ¦¤го Ё§ нвЁе Є®а®ў Ї® ®зҐаҐ¤Ё (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп Ёе ID), ®Їпвм Ё ®Їпвм ¤® вҐе Ї®а, Ї®Є  ўбҐ Є®а®ўл ­Ґ бв ­гв ®вб®авЁа®ў ­л. Ќ ЇаЁ¬Ґа, Ґб«Ё ®­ ўлЎҐаҐв Ї®¤¬­®¦Ґбвў® Є®а®ў б ID \(\{2, 4, 5\}\), в® ®­ б­ з «  ўл§®ўҐв Є®а®ўг \(2\), § вҐ¬ Є®а®ўг \(4\), § вҐ¬ Є®а®ўг \(5\). …б«Ё ўбҐ \(N\) Є®а®ў Ґйс ­Ґ ®вб®авЁа®ў ­л, ®­ Ўг¤Ґв ўл§лў вм нвЁе Є®а®ў ®Їпвм Ё ®Їпвм, бЄ®«мЄ® ­г¦­® а §.

”„ е®зҐв ¬Ё­Ё¬Ё§Ёа®ў вм а §¬Ґа нв®Ј® ¬­®¦Ґбвў . Ѓ®«ҐҐ в®Ј®, Ї®бЄ®«мЄг ®­ бзЁв Ґв зЁб«® \(K\) бз бв«Ёўл¬, Ї®¬®ЈЁвҐ Ґ¬г ®ЇаҐ¤Ґ«Ёвм \(K\)-®Ґ «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ё­Ё¬ «м­®Ґ Ї®¤¬­®¦Ґбвў® ¬Ё­Ё¬ «м­®Ј® а §¬Ґа  в Є®Ґ, зв® ўл§лў п Ї®б«Ґ¤®ў вҐ«м­® Є®а®ў нв®Ј® Ї®¤¬­®¦Ґбвў  ­г¦­®Ґ Є®«ЁзҐбвў® а § ¬®¦­® ®вб®авЁа®ў вм ўбҐе Є®а®ў.

Џ®¤¬­®¦Ґбвў® \(S\) Ё§ \(\{1,\dots,N\}\) ­ §лў Ґвбп «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 Ї®¤¬­®¦Ґбвў® \(T\) Ґб«Ё бЇЁб®Є н«Ґ¬Ґ­в®ў ў \(S\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, зҐ бЇЁб®Є н«Ґ¬Ґ­в®ў Ё§ \(T\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп). Ќ ЇаЁ¬Ґа, \(\{1, 3, 6\}\) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 \(\{1, 4, 5\}\).

ЋжҐ­Ёў ­ЁҐ: ‚ вҐбв е ­  \(3/16\) Ў ««®ў \(N \leq 6\) and \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(5/16\) Ў ««®ў, \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(8/16\) Ў ««®ў, ­Ґв ¤агЈЁе ®Ја ­ЁзҐ­Ё©.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4 1
4 2 1 3

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

2
1
4

Њл ­ зЁ­ Ґ¬ б ¬ ббЁў  \(\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 1Ў Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 4 Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}\). ‚ нв®© в®зЄҐ ¬ ббЁў ®вб®авЁа®ў ­.

Problem credits: Spencer Compton

К несчастью бюджет ФД ограничен, поэтому он решил построить ещё меньший забор, продав до трёх коров.

Помогите ФД вычислить наименьшую возможную площадь, которую он может огородить, забором после удаления не более трёх коров из стада и огораживания оставшихся коров.

Для этой задачи рассматриваем коровы как точки, а забор как коллекцию из четырёх отрезков прямых. (То есть не думайте о корове как единичном квадрате). Заметим, что ответ может быть равным 0, например, если оставшиеся коровы все стоят на одной вертикальной или горизонтальной прямой.

К несчастью бюджет ФД ограничен, поэтому он решил построить ещё меньший забор, продав одну корову.

Помогите ФД вычислить наименьшую возможную площадь, которую он может огородить, забором после удаления одной коровы из стада и огораживания оставшихся \(N-1\) коров.

Для этой задачи рассматриваем коровы как точки, а забор как коллекцию из четырёх отрезков прямых. (То есть не думайте о корове как единичном квадрате). Заметим, что ответ может быть равным 0, например, если оставшиеся коровы все стоят на одной вертикальной или горизонтальной прямой. Наконец, поскольку \(N\) может быть довольно большим, Вы должны написать программу, которая будет работать достаточно быстро.

Форма этой коровы описывается решёткой из \(N \times N\) символов (\(3 \leq N \leq 8\)), пример показан ниже, где символы '#' представляют часть коровы, а символы '.' не части коровы.

...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............

К несчастью, ФД ещё не спел купить корову, как в магазинчик ворвался бык, который поломал всё вокруг, включая корову ФД. Корова разломалась на две части, которые затерялись среди других \(K\) (\(3 \leq K \leq 10\)) кусков стекла на полу. Каждый из этих \(K\) кусков описывается решёткой \(N \times N\) символов, как и исходная фигурка.

Помогите ФД определить, какие из этих \(K\) кусков являются двумя частями фигурки ФД. При падении на землю куски ФД не поворачивались и не переворачивались, поэтому для их сборки ФД должен только сдвигать куски горизонтально или вертикально. Куски не могут наезжать друг на друга и должны сформировать точно исходную фигуру.

ФД может двигать оба куска горизонтально и/или вертикально на любое количество позиций, но так, чтобы все символы '#' оставались внутри решётки \(N \times N\). Форма каждого из кусков необязательно состоит из связного региона символов '#'. Но при сдвиге все они сдвигаются на одинаковое количество позиций.

ФД перекрасил дои и амбар и хочет быть уверенным, что Беси не доберётся ни туда, ни туда (Корова и свежая краска не есть хорошая комбинация!). Соответственно, ФД хочет быть уверенным, что Беси никогда не выйдет ни за самый левый, ни за самый правый стог. ФД может добавить сена в один стог по своему выбору, так чтобы гарантировать, что Беси не выберется. Пожалуйста, помогите ему определить минимальное количество дополнительного размера, который он должен добавить к некоторому стогу сена, чтобы гарантировать, что Беси останется в ловушке.