A. Анаграмматический Хаос

Xotira: 32 MB, Vaqt: 1000 ms

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

Дается строка \( s \) состоящая из \( k \) первых букв английского алфавита. За одну операцию можно переставить две соседние буквы в строке \( s \). Пусть \( d(x, y) \) - минимальное количество операций, которое требуется, чтобы строку \( x \) превратить в строку \( y \). Обозначим \( P(s) \) как множество всех перестановок строки \( s \). Требуется найти \( \max_{s' \in P(s)} d(s, s') \).

2
bbba

3

3
abc

3

3
caccb

6

B. Космическая Балансировка

Xotira: 32 MB, Vaqt: 1000 ms

Галактический архитектор Эркин снова создает звездные системы. На этот раз ему поручено создать \( k \) галактик из \( n \) звезд с весами \( m_1, m_2, \ldots, m_n \). Однако, в соответствии с законом Космического баланса, полученные галактики должны иметь одинаковую массу. Помогите Эркину определить, возможно ли это.

5 3
2 7 5 3 13

NO

5 3
3 5 4 1 2

YES

C. Команда аналитиков

Xotira: 128 MB, Vaqt: 2000 ms

Аркадий - менеджер команды аналитиков из \(k\) человек. У Аркадия есть бэклог из \(n\) задач, \(i\)-я задача требует \(t_i\) дней работы любого из членов команды (мы считаем всех членов команды равнозначными). Над каждой задачей от начала до конца должен работать кто-то один. Передавать задачи в процессе выполнения неудобно. Для каждой задачи известен дедлайн - \(d_i\) рабочих дней. Помогите Аркадию определить, успеет ли его команда выполнить все задачи в срок.

5 2
3 3
2 2
3 6
2 4
2 6

YES

2 1
4 7
4 7

NO

1 2
1 2

YES

5 2
5 5
2 2
1 6
2 4
2 6

YES

D. Минимальное Максимальное Ребро

Xotira: 32 MB, Vaqt: 2000 ms

Дан взвешенный связный неориентированный граф и отмечены две вершины s и t. Найдите минимальное максимальное ребро на пути из вершины s в вершину t.

5 7 1 5
2 5 2
1 2 5
3 1 5
4 5 6
3 2 3
2 4 4
5 1 10

5

E. Настольная игра

Xotira: 32 MB, Vaqt: 2000 ms

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

В этой игре нестандартные правильна получения ресурсов. Объем получаемых на каждому ходу ресурсов является случайной величиной и определяется следующим образом: 

Все \(n\) шестигранных кубиков помещаются в непрозрачный мешок:

Игрок перемешивает кубики и вытягивает 2 из мешка. 

Побрасывает два вытянутых кубика и определяет два числа \(a\) и \(b\) на верхних гранях. 

Объем предоставляемых ресурсов равен \((a+b)^3\). 

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

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

 

 

 

2
1 2 3 4 5 6
1 2 3 4 5 6

465.500000

3
2 2 2 2 2 2
4 5 5 5 5 4
9 8 9 1 9 4

978.222222

4
1 1 1 1 1 1
1 2 3 4 5 6
3 4 3 4 3 4
9 9 9 9 9 9

943.250000

F. Озеленение Марса

Xotira: 32 MB, Vaqt: 2000 ms

Требуется высадить аллею из \(n\) деревьев. Лунки под деревьями пронумерованы последовательно. Расстояние между деревьями определяется как разность номеров лунок, где они растут. 

На Марсе могут выжить только \(k\) сортов деревьев. Красота одного дерева \(i\)-го сорта \(c_i\). 
Требуется озеленить Марс с максимальной суммарной красотой. Однако, деревья одного сорта конфликтуют, поэтому их следует садить как минимум на расстоянии \(k\). 

2 5
6 7

33

1 5
9

45

5 2
11 10 7 5 18

29

G. Степень двойки

Xotira: 32 MB, Vaqt: 2000 ms

Любое натуральное число \(n\) может быть представлено как сумма степеней двойки. Например, число 6 может быть представлено как 1 + 1 + 1 + 1 + 1 + 1, 2 + 2 + 2, 4 + 2, 4 + 1 + 1, и т.д.

Обозначим \(f(x)\) - минимальное количество членов в разбиении числа \(x\).

Для данного натурального числа \(n\) определите натуральное число \(m\) ,для которого выполняются следующие условия:

\(f(n) = f(m)\)

Число m больше числа \(n\) и является минимально возможным.

6

9

20

24

1026

1028

H. XOR Турнир

Xotira: 32 MB, Vaqt: 1000 ms

XOR Турнир - соревнование, где встречаются лучшие из лучших спортивных программистов. Алиса и Боб, участники этого турнира, решили потренироваться в своей любимой игре. 

Для этой игры двум участникам дается массив из \( n \) целых неотрицательных чисел. Участники по очереди забирают себе по одному числу из массива. После того как в массиве больше не осталось чисел, происходит подсчет XOR сумм для каждого участника. Побеждает тот, у кого получившееся XOR сумма больше. Если же XOR суммы оказались равны, объявляется ничья.

Ваша задача: написать программу, которая определит исход игры при том, что Алиса и Боб играют оптимально и Алиса ходит первой.

3
2 3 5

Alice

3
1 1 1

Bob

3
1 2 3

Draw

I. Язык Foo

Xotira: 32 MB, Vaqt: 2000 ms

Ниже вам будет приведен псевдокод некоторой функции Foo. Вам нужно понять, как работает эта функция, и лучше ее реализовать. 

function Foo(array_of_ints a): // input parameters: array of integers
     result = 0
     while size(a) > 2: // as long as the array length is at least two elements
         sort(a) // sort the array in ascending order
         n = size(a)
         x = a[0] + a[n - 2]
         result += x // add x to the accumulated result
         delete(a, n-2) // delete element by index (n-2)
         delete(a, 0) // delete element at index 0
         add(a, x) // add element by value x to end of array
     return sum(a) + result // add the sum of elements to the accumulated result

Обратите внимание, что этот псевдокод использует 0-индексацию массива.

1
362018

362018

3
3 6 2018

2036

6
3 6 2 0 1 8

53