Информатика

Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.

Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).

Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).

Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.

Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).

Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).

Числа Фибоначчи определяются следующим образом: \(F_1 = 1\), \(F_2 = 2\), а для \(n > 2\) выполнено \(F_n = F_{n - 2} + F_{n - 1}\). Таким образом, начало последовательности чисел Фибоначчи выглядит так \(1, 2, 3, 5, 8, 13, 21, \ldots\).

Вам заданы числа \(n\) и \(k\). Требуется найти все способы представить число \(n\) в виде суммы неубывающих чисел Фибоначчи, причем кажое число разрешается использовать не более \(k\) раз.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \le n \le 100\)).

Вторая строка ввода содержит число \(k\) (\(1 \le k \le 20\)).

Формат выходных данных
Выведите все искомые представления, по одному на строке. Разделяйте числа знаком <<+>>, не используйте пробелы.

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

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

Бомбослав заметил, что ребята во дворе не очень изобретательны в своих действиях, и всегда меняют местами левый напёрсток со средним на нечётных действиях (то есть на первом, третьем, пятом и так далее) и средний с правым на чётных действиях (то есть на втором, четвёртом и так далее).

Пронумеруем напёрстки от \(0\) до \(2\) слева направо. То есть левый напёрстком имеет номер \(0\), средний номер \(1\), а правый номер \(2\). Бомбослав не успел увидеть начало игры, но посчитал, что ведущий совершил \(n\) действий и в итоге шарик оказался под напёрстком \(x\). Под каким напёрстком находился шарик в самом начале?

Формат входных данных
В первой строке входных данных записано одно цело число \(n\) (\(1 \leq n \leq 2 \cdot 10^9\)) — количество действий, совершённых ведущим.

Во второй строке записано одно целое число \(x\) (\(0 \leq x \leq 2\)) — номер напёрстка, под которым оказался шарик через \(n\) действий.

Формат выходных данных
Выведите одно целое число от \(0\) до \(2\), означающее номер напёрстка, под которым находился шарик в самом начале.

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

1. Первым действием ведущий поменял местами левый и средний напёрстки. В результате шарик оказался под левым напёрстком.

2. Вторым действием ведущий поменял местами средний и правый напёрстки. Шарик остался под левым напёрстком.

3. Третьим действием ведущий снова поменял местами левый и средний напёрстки. В результате шарик снова оказался посередине.

4. Последним четвёртым действием ведущий опять поменял местами средний и правый напёрстки и шарик оказался под правым напёрстком.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, верно работающие при \(n \leq 100\,000\) будут набирать не менее 50 баллов.

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).

С массивом разрешается выполнять следующие два вида действий:

1. Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).

2. Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:
   
   

Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.

Определите, какое минимальное число монет требуется заплатить, чтобы превратить данный массив в пустой. Обратите внимание, что ответ всегда существует, потому что можно просто \(n\) раз применить первую операцию.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

Формат выходных данных
Выведите \(T\) целых чисел, каждое в своей строке — ответы на задачу для каждого набора входных данных в том порядке, в котором оны даны во вводе.

Примеры

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

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

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел ai - количество магической энергии в i-м доме.

Ограничения на входные данные 

• 1 <= n <= 100
• 0 <= a[i] <= 1000
• 1 <= i <= n

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

Примеры

Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.

Вам нужно создать структуру данных, которая представляет из себя массив целых чисел. Изначально массив пуст. Вам нужно поддерживать две операции:

• запрос: «? i j» — возвращает минимальный элемент между i-ым и j-м, включительно;
• изменение: «+ i x» — добавить элемент x после i-го элемента списка. Если i=0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.

Первая строка входного файла содержит единственное целое число n — число операций над массивом (1<=n<=200000). Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 10⁹.

Для каждой операции в отдельной строке выведите её результат.

Комментарий к примеру тестов

Примеры

8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5

4
3
1

Дан массив. Надо научиться обрабатывать два типа запросов.

* 1 L R - перевернуть отрезок [L,R]

* 2 L R - найти минимум на отрезке [L,R]

Первая строка файла содержит два числа n, m. (1<=n,m<=10⁵) Во второй строке находится n чисел ni (1<=a_i<=10⁹) - исходный массив. Остальные m строк содержат запросы, в формате описанном в условии. Для чисел L, R выполняется ограничение (1<=L<=R<=n).

На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.

Примеры

10 7
5 3 2 3 12 6 7 5 10 12
2 4 9
1 4 6
2 1 8
1 1 8
1 8 9
2 1 7
2 3 6

3
2
2
2

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE

DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить» и «найти» (по значению). Программа должна обрабатывать запросы трёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
 

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7

DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO

Примеры

3 2
2 6
3 4 5

1
1

3 2
1 6
4 3 5

0

3 5
1 7
5 3 4

3 
2
3
1