Информатика

Назовем опорным числом последовательности натуральных чисел - целое число x, такое что:

• Сумма всех элементов между 1 и x включительно равна сумме всех элементов между x и n включительно.

Например, для числовой последовательности из 8 элементов (числа от 1 до 8 включительно) опорным числом будет число 6 (1+2+3+4+5+6 = 6+7+8).

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

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 2000).

Формат выходных данных
Выведите минимальную опорную точку последовательности натуральных чисел от 1 до n. Если такой точки не существует, вернуть -1.

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP.

Вы должны вывести (через пробел, в порядке возрастания) все числа, которые мог задумать Август.

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

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

Пронумеруем напёрстки от \(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 баллов.

Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

На вход программы поступают числа n ( 1 ≤ n ≤ 100) - количество вершин в графе и m (1 ≤ m ≤ n(n-1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Выведите матрицу смежности заданного графа.

Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

На вход программы поступает число n (1 ≤ n ≤ 100) – количество вершин  графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности. 

Требуется отсортировать массив по неубыванию методом "выбора".

Пример

Дан массив целых чисел nums (первый элемент массива имеет индекс 0). Найдите наименьший "средний" индекс массива.

Средний индекс - это индекс, для которого выполняется условие: сумма элементов слева от индекса равна сумме элементов справа от индекса (не включая сам элемент со средним индексом). То есть

leftSum[middle] = rightSum[middle].

Где:

middle - средний индекс массива.
leftSum[middle] - сумма элементов, стоящих слева от элемента nums[middle]. Если таких элементов нет, то leftSum[middle] = 0. 
rightSum[middle] - сумма элементов, стоящих справа от элемента nums[middle]. Если таких элементов нет, то rightSum[middle] = 0.

Формат входных данных
Первая строка содержит натуральное число N (1 <= N <= 105) - количество элементов в массиве nums. Вторая строка содержит N чисел numsi - элементы массива nums (|numsi|<=1000, 0 <= i < N).

Формат выходных данных
Выведите одно число - наименьший "средний" индекс массива. Если такого индекса нет, то выведите -1.

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел vi - значения максимальной скорости i-го автомобиля (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵). В третьей строке записано натуральное число k (k ≤ n). 

Формат выходных данных
Напечатайте максимальную скорость автомобиля, являющегося "k-м самым быстрым автомобилем".

Дан массив \(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\) целых чисел, каждое в своей строке — ответы на задачу для каждого набора входных данных в том порядке, в котором оны даны во вводе.

IT-компания <<VK>> имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из <<VK>> могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

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

• <<Исток>> графа — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.

• Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.

• Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.

• Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину графа. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.

• Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как HEAD.

Пример графа можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершина номер \(8\) соответствует команде merge между ветками <<main>> и <<new_config>> (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в прикрепленном к условию архиве.

Изначально граф состоит из единственной вершины с номером \(1\), на которую указывает текущая ветка <<main>>. Требуется поддерживать следующие команды:

1. <<add <файл> <хеш изменений>>> — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда состояния файла до и после изменения одинаковы.

   Иными словами, если в пустой файл добавляется строчка <<print(something)>>, и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.

2. <<commit>> — подвесить к HEAD новую вершину, состоящую из всех изменений (add), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего HEAD перемещается на нее.

   Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку <<ERROR: no changes>>, при этом новая вершина не создается.

3. <<reset <номер>>> — переместить HEAD на вершину с данным номером.

   Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные (commit) изменения (add), операция отклоняется с ошибкой <<ERROR: uncommitted changes>>.

4. <<checkout <имя ветки>>> — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить HEAD на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на HEAD, после чего сделать ее текущей.

   Если присутствуют несохраненные изменения, операция отклоняется с ошибкой <<ERROR: uncommitted changes>>, аналолгично операции reset.

5. <<merge <имя ветки>>> — объединить изменения в текущей ветке и в ветке с указанным именем. При этом создается новая вершина, которая подвешивается к HEAD и к вершине, соответствующей второй ветке. HEAD при этом перемещается на новую вершину, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.

   Если есть незакоммиченные изменения, операция отклоняется с ошибкой <<ERROR: uncommitted changes>>.

   Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как \(D_1\), а во второй — как \(D_2\), то конфликт возникает, когда оба множества \(D_1 \setminus D_2\) и \(D_2 \setminus D_1\) непустые. В таком случае операция отклоняется с ошибкой <<ERROR: conflicts detected>>.

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

   Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после merge двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть измененение одного и того же файла, которого нет в другой версии.

   Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции merge.

   

   

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<OK>> и номер вершины, на которую указывает HEAD, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

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

Каждый набор входных данных начинается со строки, содержащей единственное целое число \(n\) — количество команд в наборе (\(0 \le n \le 400\)). В \(i\)-й из следующих \(n\) строк задается \(i\)-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв (‘a’ – ‘z’) и нижних подчеркиваний (‘_’), а хеши изменений — уникальные шестнадцатеричные строки длины ровно \(6\) (состоят из цифр и маленьких латинских букв от ‘a’ до ‘f’). Имена файлов в команде add состоят из маленьких латинских букв, точек и слешей (‘/’).

Также гарантируется, что команде reset всегда передается существующая вершина, а команде merge — существующая ветка, не совпадающая с текущей.

Формат выходных данных
Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку <<Test case <номер>>> (наборы нумеруются от \(1\) до \(T\)), а затем \(n\) результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату <<OK <HEAD>>>, либо формату <<ERROR: <сообщение об ошибке>>>.

На день рождения Маше как обычно подарили массив \(a\) из \(n\) натуральных чисел, в котором каждое число находится в пределах от \(1\) до \(m\) включительно. Маша очень любит число три, поэтому длина массива делится на три.

Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел. Другими словами, каждая тройка имеет или вид \((x, x, x)\), или \((x, x+1, x+2)\), где \(x\) — какое-то натуральное число.

Маша хочет поиграть с подаренным массивом, и ее интересует количество способов разбить числа этого массива на такие тройки. Два способа разбиения считаются различными, если нельзя установить взаимно-однозначное соответствие между тройками первого разбиения и тройками второго разбиения, что числа внутри соответствующих троек равны. Так как количество разбиений может быть большим, Маше достаточно знать его остаток по модулю \(10^9+7\).

Помогите Маше посчитать количество способов разбить числа подаренного ей массива на тройки по модулю \(10^9+7\).

Формат входных данных
Первая строка входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 5000\), \(1 \le m \le 5000\), \(n=3\cdot k\) для какого-то натурального \(k\)).

Вторая строка содержит \(n\) целых чисел \(a_i\) — числа массива (\(1 \le a_i \le m\)).

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

В первом примере числа можно разбить на тройки двумя способами: {\((2, 2, 2)\), \((3, 3, 3)\), \((4, 4, 4)\)} и {\((2, 3, 4)\), \((2, 3, 4)\), \((2, 3, 4)\)}.

В биологической лаборатории проводят эксперимент. В начале у ученых есть \(n\) замороженных бактерий, пронумерованных от \(1\) до \(n\).

Согласно плану эксперимента замороженная бактерия с номером \(i\) попадёт в чашку Петри через \(a_i\) секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.

Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером \(i\) занимает \(t_i\) секунд. Как только бактерия созрела, она начинает размножаться: немедлено превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.

Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента — определить, через сколько секунд размер колонии будет в точности равен \(m\).

Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен \(m\).

Формат входных данных
В первой строке даны целые числа \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^{9}\)) — количество замороженных бактерий и желаемый размер колонии.

Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)) — времена перемещения замороженных бактерий в чашку Петри.

В третьей строке даны \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^{9}\)) — продолжительность созревания замороженных бактерий.

Формат выходных данных
Если размер колонии никогда не будет равен \(m\), выведите \(-1\).

В противном случае выведите число секунд после начала эксперимента, через которое размер колонии будет в точности равен \(m\).

Рассмотрим, как развивается эксперимент в первом примере.

Дан массив \(A = [a_1, a_2, \ldots, a_n]\), содержащий \(n\) натуральных чисел.

Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух элементов \(x\) и \(y\) одного цвета, таких что \(x\) нацело делился на \(y\) и выполнялось равенство \(\frac{x}{y} = p\), где \(p\) — простое число. Гарантируется, что такая раскраска существует.

Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).

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

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)) — элементы массива.

Формат выходных данных
Выведите описание разбиения массива на два множества в следующем формате.

Выведите \(n\) целых чисел, \(i\)-е из которых равняется \(1\), если элемент \(a_i\) надо раскрасить в первый цвет и \(2\), если элемент \(a_i\) надо раскрасить во второй цвет.

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

В первом примере есть два элемента первого цвета: \(2\) и \(3\), и два элемента второго цвета: \(1\) и \(4\). Элементы первого цвета не делятся нацело друг на друга. \(4\) нацело делится на \(1\), но их отношение не является простым числом.