реализация

97 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Необычный массив#50409

У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Для каждой позиции \(i\) и для каждого подотрезка массива \([l, r]\), который содержит позицию \(i\) (то есть, \(1 \le l \le i \le r \le n\)), Вася вычисляет значение \(c_{i, l, r}\) следующим образом. Вася выписывает на листочек числа из массива с позиции \(l\) до позицию \(r\), всего \(len=r-l+1\) чисел (среди которых обязательно есть \(a_i\)), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции \(j\) в полученном отсортированном массиве стоит число \(a_i\). Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции \(mid = \lceil (len+1) / 2 \rceil\) (\(len / 2 + 1\) в случае четного \(len\) и \((len+1)/2\) в случае нечетного \(len\)). Полученное расстояние \(|j - mid|\) и есть искомая величина \(c_{i,l,r}\).

Например, если у Васи был массив \(a=\{5,1,3,2,1,7\}\), а \(i=2\), \(l=2\), \(r=5\), то Вася выпишет на листочек числа \(\{1,3,2,1\}\), отсортирует их и получит массив \(\{1,1,2,3\}\), длина которого равна 4. Середина этого массива находится на позиции \(4/2+1=3\), а искомое число \(a_i=1\) стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение \(c_{2,2,5}\).

Для каждой позиции \(i\) Вася вычисляет величину \(b_i\), которая равна максимуму среди значений \(c_{i,l,r}\) среди всех подотрезков, содержащих позицию \(i\).

Как вы видите, определение числа \(b_i\) достаточно сложное. Помогите Васе вычислить значения \(b_i\) для всех позиций массива.

Формат входных данных
В первой строке входных данных находится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — размер массива Васи.

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

Формат выходных данных
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно \(b_i\).


Примечание

Разберем подробнее первый пример.

  1. Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок \([1,5]\), где \(l=1\) и \(r=5\). Для вычисления \(c_{i,l,r}=c_{1,1,5}\) Вася выпишет числа \(\{5, 4, 3, 2, 1\}\) и после сортировки получит \(\{1, 2, 3, 4, 5\}\). Середина этого массива находится на позиции 3, а искомое число \(a_1=5\) — на позиции 5. Таким образом, \(c_{1,1,5}=2\). Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, \(b_1=2\).

  2. \(b_2=c_{2,2,4}\).

  3. \(b_3=c_{3,3,5}\).

  4. \(b_4=c_{4,1,4}\). Действительно, если выписать числа на подотрезке \([1,4]\), то получится массив \(\{5,4,3,2\}\), который после сортировки превратится в \(\{2,3,4,5\}\). Середина этого массива находится на позиции \(3\), а искомый элемент \(a_4=2\) — на позиции 1. Таким образом, \(c_{4,1,4}=2\).

  5. \(b_5=c_{5,1,5}\).

 

Дерево отрезков, RSQ, RMQИспользование сортировкиреализация
✓ 1✗ 2—Войти и решать
Устный счет#49860

Отвлечемся от задач про программистов и перенесемся в совершенно обыкновенные ясли, где мальчик Вова (3 годика) практикуется в устном счете, а если точнее — в вычислении арифметических выражений по модулю \(10^9 + 7\).

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

Пока шел тихий час, Вова спал, а хулиганы стерли несколько цифр в выражении и заменили их на другие. Менять знаки или результат вычисления выражения хулиганы не решились, даже для них это слишком низко. Когда Вова проснулся, он обнаружил рядом с его листочком ластик и карандаш. У Вовы есть принципы — если хулиганы изменили не более двух цифр, то он их простит, иначе они будут наказаны по всей строгости ясельных законов.

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

Формат входных данных
Единственная строка входного файла содержит выражение, которое обнаружил Вова у себя на листке. Выражение состоит из двух частей, разеделенных знаком ‘=’.

Первая часть содержит \(n\) целых неотрицательных чисел, разделенных знаками сложения (‘+’) и умножения (‘*’) (\(1 \le n \le 10^5\)). Вторая часть — целое неотрицательное число, означающее результат вычисления выражения.

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

Формат выходных данных
В случае, если данное выражение не может быть получено из верного равенства заменой не более двух цифр, выведите <<NO>>.

В противном случае в первой строке выведите <<YES>>. На следующей строке выведите целое число \(k \leq 2\) — количество чисел, которые были изменены.

В следующих \(k\) строках выведите по два числа — позицию измененнного числа в выражении (от \(1\) до \(n\)) и его исходное значение.

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

 

Вывод формулыреализация
✓ 0✗ 3—Войти и решать
Быстрый исполнитель#49859

Студент первого курса ИТМО Миша изучает новый примитивный язык программирования. В этом языке все операции производятся над массивами целых неотрицательных чисел длины \(n\).

Миша успел создать массив \(a\) и равный ему массив \(b\). Также он успел реализовать четыре функции:

  1. shift — делает циклический сдвиг массива \(a\) влево на \(d\), то есть при \(a = [a_0, a_1, \ldots, a_{n-1}]\) выполняет присваивание \[a \gets [a_d, \ldots, a_{n-1}, a_0, \ldots, a_{d-1}] \text{;}\]

  2. xor — присваивает в массив \(b\) его поэлементный xor (побитовое исключающее <<или>>) с массивом \(a\), то есть \[b \gets [a_0 \oplus b_0, a_1 \oplus b_1, \ldots, a_{n-1} \oplus b_{n-1}] \text{;}\]

  3. and — присваивает в массив \(b\) его поэлементный and (побитовое <<и>>) с массивом \(a\);

  4. or — присваивает в массив \(b\) его поэлементный or (побитовое <<или>>) с массивом \(a\).

Используя эти функции, Миша написал программу, задаваемую последовательностью операций xor, and и or длины \(m\). Программа в цикле \(p\) раз выполняет следующие действия: для каждой операции из последовательности сначала вызывается shift, а затем соответствующая этой операции функция. Так, для последовательности операций \([\mathtt{or}, \mathtt{xor}, \mathtt{and}]\) и \(p = 5\) программа будет выглядеть как

b = a = [...]
repeat 5 times {
    shift
    or
    shift
    xor
    shift
    and
}

К сожалению, язык еще новый, и его интерпретатор не справляется с выполнением такой программы. Помогите Мише определить, чему будет равно конечное состояние массива \(b\) после выполнения заданной программы.

Формат входных данных
В первой строке ввода перечислены четыре целых числа \(n\), \(m\), \(d\) и \(p\) — длина массива, количество операций в последовательности, величина сдвига и количество повторений (\(0 \le d < n \le 2 \cdot 10^5\); \(1 \le m \le 10\); \(1 \le p \le 10^9\)).

Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\), они же — изначальные значения элементов массива \(b\) (\(0 \le a_i \le 10^9\)).

В третьей строке через пробел перечисены \(m\) слов, каждое из которых равно <<xor>>, <<and>> или <<or>> — последовательность применяемых на каждой итерации цикла операций.

Формат выходных данных
Выведите \(n\) целых чисел — элементы массива \(b\) после выполнения описанной программы.

Задачи на моделированиереализация
✓ 1✗ 2—Войти и решать
Трансформация массива#49773

Вам дано \(t\) пар массивов \(a_i\) и \(b_i\) равной длины.

За одну операцию модификации можно:

  • Поменять местами любые два элемента массива \(a_i\), но каждый элемент массива может участвовать не более чем в одном обмене.

  • Вычесть из любого элемента массива \(a_i\) единицу. Данную операцию можно применять неограниченное число раз к любому элементу массива.

Для каждой пары массивов найдите минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или определите, что это невозможно.

Входные данные
В первой строке дано число \(t\) — число пар массивов (\(1 \le t \le 40\)).

В следующих \(3t\) строках содержатся описания пар массивов. Каждая пара описывается тремя строками.

В первой из них дано число \(n_i\) — количество элементов в каждом массиве \(i\)-й пары(\(1 \le n_i \le 10\)). Во второй строке заданы \(n_i\) чисел \(a_{i,j}\) — элементы массива \(a_i\) (\(1 \le a_{i,j} \le 1000\)). В третьей строке заданы \(n_i\) чисел \(b_{i,j}\) — элементы массива \(b_i\) (\(1 \le b_{i,j} \le 1000\)).

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

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

 
жадные алгоритмыреализация
✓ 2✗ 0—Войти и решать
Разделяй и властвуй#49449
В тридесятом государстве ради сбора мытных денег (таможенных пошлин) с торговых людей царь Салтан указал сделать зáсеки – заградительный полосы, которые тянутся с севера на юг или с запада на восток и преграждают путь всякому пешему и конному.

Тридесятое государство имеет форму прямоугольника, стороны которого тянутся с запада на восток и с севера на юг. Картограф изобразил карту государства в виде прямоугольника на системе координат с центром O, совпадающим с юго-западным углом страны и осями, параллельными осям координат. Засеки на карте изображены в виде отрезков различной длины, параллельных осям координат. При этом оказалось, что никакие два отрезка не пересекаются и не лежат на одной прямой.


Для удобства управления своей страной царь Салтан повелел разделить ее на непересекающиеся прямоугольные области с соблюдением следующих условий: 

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

Напишите программу, помогающую картографическому приказу построить искомое разбиение.

Входные данные
В первой строке находятся координаты северо-восточного угла страны, Во второй строке указано количество засек N (N≤1000). Каждая из следующих N строк содержит описание одной из засек в виде четверки числе x1, y1, x2, y2, что соответствует отрезку с концевыми точками (x1, y1)  и (x2, y2). Все координаты являются неотрицательными целыми и не превосходят 10000.

Выходные данные
В первую строку  выведите количество областей M в найденном разбиении. В последующих M строках должны находиться целочисленные координаты юго-западного и северо-восточного углов для каждой из областей разбиения. Числа внутри строки разделять пробелами.
 
разделяй и властвуйреализация
—Войти и решать
ХЕШ-ФУНКЦИЯ#49404
Для быстрого распознавания идентификаторов в современных трансляторах  используются хеш-функции. Хеш-функция сопоставляет строке целое число из некоторого промежутка. Критерием оценки хеш-функции является количество коллизий, то есть ситуаций, когда различным встретившимся строкам сопоставляется одно и то же число.

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

На время тура вам предоставляется файл words.txt, содержащий перечисленные в алфавитном порядке 10 000 слов. Слова из этого файла будут использоваться при тестировании вашего решения. Это означает, что во всех тестах слова будут выбираться только из этого множества. Во время тестирования файл words.txt будет вашей программе недоступен.

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



Входные данные
Входные данные содержат список неповторяющихся слов по одному в строке, выбранных. Регистр букв в словах будет тем же, что и в файле words.txt.

Выходные данные
Для каждого слова из заданного списка требуется вывести соответствующее хеш-значение. Числа должны быть записаны по одному в строке.
 
реализацияХеш
—Войти и решать
Ханойская фабрика#49297

Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.

На складах фабрики находятся \(n\) колец, \(i\)-е кольцо имеет внутренний радиус \(a_i\), внешний радиус \(b_i\) и высоту \(h_i\). Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:

  • Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j \leq b_i\).

  • Кольца не должны проваливаться друг в друга, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j > a_i\).

  • Суммарная высота всех использованных колец должна быть максимальна.

Формат входных данных
В первой строке входных данных записано целое число \(n\) (\(1 \leq n \leqslant 100\,000\)) — количество колец на складах фабрики.

В \(i\)-й из последующих \(n\) строк записаны три числа \(a_i\), \(b_i\) и \(h_i\) (\(1 \leq a_i, b_i, h_i \leq 10^9\), \(b_i > a_i\)) — внутренний радиус, внешний радиус и высота \(i\)-го кольца соответственно.

Формат выходных данных
Выведите максимальную высоту башни, которую смогут получить работники фабрики.


Замечание

В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке \(3\), \(2\), \(1\).

Во втором примере можно либо поставить кольцо \(3\) на кольцо \(4\) и получить башню высоты \(3\), либо поставить кольцо \(1\) на кольцо \(2\) и получить башню высоты \(4\).

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

Решение, корректно работающие при \(1 \leq n \leq 9\), наберут не менее \(10\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 15\), наберут не менее \(20\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 1000\), наберут не менее \(60\) баллов.

Жадный алгоритмИспользование сортировкиреализация
✓ 1✗ 3—Войти и решать
Тестирование мессенджера#49029

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

  1. генерируется случайный сценарий взаимодействия пользователей с приложением;

  2. в приложении симулируется выполнение этого сценария;

  3. проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

  1. Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

    Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.

  2. Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

    Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.

  3. Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

    Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

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

Формат входных данных

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

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

  1. События первого набора задаются в формате <<\(t_i\): REG \(\mathtt{id}_i\) \(\mathtt{handle}_i\)>>.

  2. События второго набора задаются в формате <<\(t_i\): CHANGE \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

  3. События третьего набора задаются в формате <<\(t_i\): SEND \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

Гарантируется, что в каждом наборе входных данных все \(t_i\) различны. Гарантируется, что успешно зарегистрированный пользователь не предпринимает попытки зарегистрироваться еще раз.

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

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> SENT <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> TO <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество отправленных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, получившего от него больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, отправленных пользователю \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, получивших от него максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не отправлял сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

 
реализацияСортировка событийХеш
✓ 1✗ 2—Войти и решать
Устранение массива#49028

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

 
Задачи на моделированиереализация
✓ 3✗ 0—Войти и решать
Система контроля версий - 2#49027

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    image image

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<SUCCESS>> и номер вершины, на которую указывает 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\) результатов выполнения команд, каждый в своей строке.

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

 

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

графыреализация
✓ 0✗ 2—Войти и решать
Минимальное максимальное#43135
Алексей Юрьевич и Михаил Леонидович отправились на поезде в Троицк. По дороге к ним подсели вахтовик и дембель. После знакомства и небольших историй о себе вахтовик и дембель решили устроить Алексею Юрьевичу и Михаилу Леонидовичу тест «на мужика»: нужно решить непростую задачку по программированию.
Помогите Алексею Юрьевичу и Михаилу Леонидовичу пройти тест «на мужика».
Задан массив целых чисел a1,a2,...,an.
Стоимостью подотрезка массива 1 <= l <= r <= n назовем величину f(l,r) = sum(l,r) − xor(l,r), где sum(l,r) = al +al+1+...+ar, а xor(l,r) = al ⊕al+1 ⊕...⊕ar (⊕ здесь обозначает операцию XOR, побитовое исключающее «ИЛИ» чисел, подробнее в разделе «Замечание»).
Требуется найти подотрезок заданного массива с максимальным значением f(l,r). Если ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением r − l +1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 104) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 105) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,...,an (0 <= ai <= 109) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 · 105.
Выходные данные
Для каждого набора входных данных выведите два числа 1 <= l <= r <= n таких, что значение f(l,r) максимально по всем подотрезкам массива a, а длина r −l +1 минимальна. Если существует несколько правильных ответов, выведите любой из них.
 
Примеры
№ Входные данные Выходные данные
1 6
1
0
2
5 10
3
0 2 4
4
0 12 8 3
5
21 32 32 32 10
7
0 1 0 1 0 1 0		 1 1
2 2
3 3
2 3
3 4
4 6

Замечание
Операция XOR двух чисел a и b — это битовая операция, которая применяется независимо к каждой паре соответствующих битов a и b. Эта операция представляет собой сложение по модулю 2. Вот её таблица истинности для пары битов:
a b a⊕b
0 0 0
0 1 1
1 0 1
1 1 0

В первом наборе входных данных f(1,1) = 1 − 1 = 0.
Во    втором    наборе    входных    данных    f(2,2)    =    10 − 10    =    0.    Заметим,    что f(1,2) = (10 + 5) − (10 ⊕ 5) = 0, но нам среди максимальных значений f(l,r) нужно найти подотрезок с минимальной длиной.
В четвертом наборе входных данных f(2,3) = (12+8) − (12 ⊕ 8) = 16.
В пятом наборе входных данных есть два правильных ответа, так как f(2,3) = f(3,4) и их длины равны.

 
математикареализация
✓ 2✗ 3—Войти и решать
K-mex#43131
Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
•    + x — добавить число x в множество. Гарантируется, что раньше его там не было,
•    - x — удалить число x из множества. Гарантируется, что это число там есть,
•    ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 105) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 1018), если запрос удаления, то - x (1 <= x <= 1018), если же запрос поиска, то ? k (1 <= k <= 1018). Гарантируется, что будет хотя бы один запрос типа ?.

Выходные данные
Для каждого запроса типа ? выведите k − mex множества.
 
Примеры
№ Входные данные Выходные данные
1 18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 100000000
? 100000000
- 4
? 1
? 2		 3
6
3
3
10
3
200000000
3
4

Замечание
После первого и второго запроса во множестве будут элементы 0,1,2. Наименьшее неотрицательное число, которое не делится на 1 и которого нет в множества, равно 3.
После четвертого запроса во множестве будут элементы 0,1,2,4. Наименьшее неотрицательное число, которое не делится на 2 и которого нет в множества, равно 6
 
реализацияХеш
✓ 1✗ 2—Войти и решать
Копейский рок#43129
Мало кто знает, но у Данилы Багрова и Татарина есть ещё один брат, неизвестный широкой публике. Проживает он тихо, мирно в Копейске, вдали от столичной суеты и назойливых папарацци.
Однажды Данила Багров и Татарин решили навестить своего брата. Приехав к нему домой в Копейск, Данила обнаружил в шкафу обширную коллекцию дисков различных рок-групп. На полках лежали диски «Nautilus Pompilius», «Би-2», «АукцЫона», «Смысловых галлюцинаций», «Агаты Кристи» и многих других. Однако Даниле не понравилось, как эти диски были разложены на полках.
Шкаф с полками можно представить в виде прямоугольника n×m, где в каждой клетке лежит один диск. Каждый диск описывается одним числом — некоторым номером группы, которая записала этот диск. Будем считать, что если два диска имеют одинаковое число, то их записала одна и та же группа, а если разные — то их записали разные группы.
Данила хочет добиться того, чтобы в каждом столбце все диски были записаны разными группами. Для этого он может сколько угодно раз переставлять диски произвольным образом на любой полке (то есть внутри любой строки), однако, запрещено менять местами диски с разных полок.
Помогите Даниле и скажите, можно ли такими действиями добиться того, чтобы в каждом столбце все диски были записаны разными группами.
Входных данные
В первой строке через пробел заданы два целых числа n и m — размеры шкафа (1 <= n,m <= 100).
В следующих n строках через пробел записаны m целых чисел ai,j — номер группы, которая записала диск, лежащий на i-й полке в j-м столбце (1<= ai,j <=109).
Выходные данные
В первой строке выведите Impossible, если Данила не может расставить всё так, чтобы в каждом столбце диски были записаны разными группами, и Possible, если такая расстановка возможна.
В случае, если Данила может добиться желаемого, выведите финальную расстановку дисков в шкафу. Если таких расстановок несколько, выведите любую из них.
 
Примеры
№ Входные данные Выходные данные
1 3 4
1 2 2 3
3 2 1 4
2 4 1 3		 Possible
3 2 1 2
1 3 2 4
2 1 4 3
2 3 3
1 1 1
1 1 1
1 1 1		 Impossible
математикареализация
✓ 0✗ 8—Войти и решать
Сын маминой подруги#39500
Вася уже в десятом классе. После месяца ежедневных заруб в доту со своими товарищами, он начал замечать, что его оценки начали проседать. Исправлять их он, конечно же не собирается, но есть один нюанс...
Вместе с Васей в классе учится сын маминой подруги — Петя. Вася очень не любит его, потому что мама Васи дружит с мамой Пети и знает про него почти всё. В конце триместра у васиной мамы есть традиция садиться и сравнивать оценки Васи с оценками Пети. За каждый случай, когда у Васи оценка ниже, чем у Пети, мама выдаёт ему наряд вне очереди! — мыть весь день посуду, пропылесосить во всём доме, помыть окна или отвести/забрать младшую сестру из детского сада.
Конечно же, эта ситуация Васе не очень нравится, потому что в среднем Вася умнее Пети. Вася хочет минимизировать количество штрафных нарядов, поэтому он собирается перемешать оценки.
Помимо оценок в журнале встречается метка n. Она означает, что ученика на уроке не было. Если кого-то из учеников не было на уроке, то мама Васи не может сравнить успехи своего сына и сына своей подруги, поэтому штрафной наряд выписан быть не может
Помогите Васе перемешать свои оценки и n-ки так, чтобы получить как можно меньше штрафных нарядов. Если существует несколько решений, выведите любое.
В школе N различных предметов, и по каждому из них Вася должен перемешать оценки.
В каждом тесте первое число N — это количество предметов, за которые получены оценки в этом триместре. В следующих 2N строках находятся N блоков по 2 строки. В каждом блоке в первой строке находятся оценки Васи, а во второй — оценки Пети. Для каждого блока в новой строчке нужно вывести такую перестановку номеров оценок и меток n, что ai означает, что Васина оценка под номером i должна занять позицию ai.
В первом тесте N = 30. Оценка за этот тест: 30 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 1 балл. Проверка осуществляется в режиме online (результат виден сразу).
Во втором тесте N = 35. Оценка за этот тест: 70 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 2 балла. Во время тура проверяется, что по каждому предмету сдана корректная перестановка. Проверка правильности ответа осуществляется в режиме offline (результат виден после окончания тура).
Примеры
№ Входные данные Выходные данные
1 3
5
4 4 3 4 4
5 5 4 5 5
4
n 3 4 n
4 n 4 n
4
1 3 2 4
3 2 1 5		 5 1 2 4 3
1 2 3 4
3 4 2 1

В первом примере Вася получит 4 наряда вне очереди. Во втором примере ничего никуда переставлять не надо, потому что на единственном уроке, на котором присутствовали оба ученика, они получили по 4 балла. В третьем примере Вася переставит оценки вот так: 4, 2, 1, 3 и получит один наряд вне очереди

 
жадные алгоритмыреализация
—Войти и решать
Том и Джерри#38275
В этой задаче мы снова возвращаемся в младшую группу детского сада «Телепузики». Чтобы окончательно успокоить детей, воспитательница решила включить им мультик про Тома и Джерри. Серия, которую сейчас смотрят дети, довольно-таки незамысловата — в ней Джерри развесил по потолку комнаты наковальни на веревках. Когда Том оказывается под очередной наковальней, Джерри перерезает веревку. Наковальня падает на Тома, Тому больно, всем остальным весело, дети смеются. В общем, вполне обычная серия.

А вам нужно по кадру из этой серии определить, упадет ли наковальня на Тома, если Джерри перережет веревку.

Входные данные
Вам дана ASCII-арт картинка, то есть картинка, нарисованная символами. На ней есть наковальня, привязанная веревкой к потолку, и кот Том. В первой строке даны числа N, M (4≤N≤100, 1≤M≤100 ). Следующие N строк состоят из M символов каждая, и представляют собой саму картинку. Картинка устроена следующим образом:
  • Первые K1 строк в одной и той же позиции X1 стоит символ «|», в остальных — пробел. Это веревка.
  • Следующие K2 строк в одних и тех же позициях с X2 по X3 стоит символ «#», в остальных — пробел. Это наковальня.
  • 2×X1=X2+X3, то есть наковальня подвешена за середину.
  • Следующие K3 строк содержат только пробелы. Это пустота между наковальней и котом.
  • Следующие N − K1 − K2 − K3 строк содержат произвольные символы. Любой символ, кроме пробела — часть кота. Существует хотя бы один непробельный символ.
Числа K1, K2, K3 и N − K1 − K2 − K3  ненулевые.
Выходные данные
Выведите «YES», если при падении наковальня заденет Тома, в противном случае выведите «NO».
 
Примеры
№ Входные данные Выходные данные
1 13 29 
          |                  
          |                  
          |                  
    #############            
    #############            
    #############            
                             
                             
            /\_/\            
            >^.^<.---.       
           _'-`-'     )\     
          (6--\ |--\ (`.`-.  
              --'  --'  ``-'
YES
2 16 30 
    |                         
 #######                      
 #######                      
 #######                      
 #######                      
                              
            ,                 
           \)\_               
          /    '. .---._      
        =P ^     `      '.    
         `--.       /     \   
         .-'(       \      |  
        (.-'   )-..__>   , ;  
        (_.--``    (__.-/ /   
                .-.__.-'.'    
                 '-...-'
NO
Задачи на моделированиереализация
—Войти и решать
Шифровка#23589
На контрольной по алгебре логики Филипп К. и Алла П. по ходу решения задачи хотят обмениваться наборами из 0 и 1, которые у них получаются. Но злобный учитель информатики очень строго следит за тем, чтобы в ходе контрольной ученики решали задачи самостоятельно. Правда, школьникам удалось воззвать к его человеческим чувствам, и он разрешил им обмениваться записками, содержание которых никак не связано с алгеброй логики.
 
К счастью, Филипп и Алла успели договориться, что они будут шифровать наборы из 0 и 1 предложениями русского языка. Слово четной длины будет обозначать 0, нечетной длины - 1, знаки препинания при расшифровке не учитываются.
 
Таким образом, расшифровать такую шифровку очень просто, а вот чтобы зашифровать какую-либо последовательность, требуется незаурядный литературный талант. Помогите им! Напишите программу, которая по введенной последовательности  из 0 и 1, строит текст, соответствующий правилам русского языка, имеющий с точки зрения языка хоть какой-то (минимальный!) смысл, и который кодирует заданную последовательность.
 
Входные данные
В файле INPUT.TXT записано сначала число N (1<=N<=100) - длина последовательности, а затем последовательность из N чисел, каждое из которых является 0 или 1.
 
Выходные данные
В файл OUTPUT.TXT выведите текст на русском языке, который кодирует заданную последовательность. Обратите внимание! В тексте не должно быть одинаковых предложений (предложения считаются одинаковыми, если они совпадают с точностью до знаков препинания, если же они различаются хотя бы порядком следования слов, они уже считаются различными). А в одном предложении ни одно из слов не должно повторяться.
 
Задача на реализациюреализация
—Войти и решать
The Cake is a Lie#21997
GLaDOS приготовила для Челл новое, последнее испытание! В его рамках ей предстоит найти торт. Но всё не так-то просто — у неё отобрали портальную пушку и завязали глаза. Единственное, что Челл известно, — что она находится в прямоугольной комнате, выложенной квадратной плиткой, и что где-то в этой комнате расположен торт. Всё что остаётся делать Челл, — слепо переходить с плитки на плитку в поисках торта.

Кроме того, так как действие происходит в Лаборатории Исследования Природы Порталов, на каждой стене комнаты расположен портал, связанный с противоположной стеной. Формально: рас- смотрим комнату как прямоугольную сетку размера W × H и введем систему координат так, чтобы левая нижняя ячейка сетки имела координаты (0, 0), а правая верхняя — (W − 1, H − 1). За один шаг Челл может перейти в одну из четырёх соседних ячеек, причём попытка пройти сквозь стену приводит к тому, что Челл появляется с противоположной стороны комнаты. Например, шаг вниз из ячейки (x, 0) приведёт в ячейку (x, H −1), а шаг влево из ячейки (0, y) приведёт в ячейку (W −1, y).

Чтобы сделать испытание сложнее, GLaDOS не сообщила Челл ни размеры комнаты, ни коорди- наты её изначального положения, ни координаты торта. Более того, так как у Челл завязаны глаза, а портальная технология достигла совершенства в своём развитии, Челл даже не может определить, прошла ли она очередным ходом через портал или нет.

Челл может найти торт, только оказавшись в одной клетке с ним. Помогите ей пройти последнее испытание! Формат взаимодействия с тестирующей системой Это интерактивная задача. Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже. Вам разрешается произвести не более 200 000 ходов. Чтобы переместиться в соседнюю ячейку, выведите строку, содержащую ровно один символ, задающий направление перемещения: «U» — вверх; «D» — вниз; «L» — влево; «R» — вправо. Затем вы должны считать строку, в которой будет находиться ровно один символ, обозначающий результат перемещения: • «Y» — после произведённого хода Челл оказалась в клетке с тортом; • «N» — после произведённого хода Челл оказалась в клетке, не содержащей торт; • «E» — служебный символ, обозначающий, что после произведённого хода Челл всё ещё не нашла торт, а ваша программа превысила ограничение на количество ходов. Обратите внимание, после считывания символа «Y» или «E» вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некор- ректным! Гарантируется, что в клетке, в которой исходно находится Челл, нет торта. В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасы- вайте буфер вывода — для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Задачи на моделированиеинтерактивреализация
✓ 0✗ 1—Войти и решать
Поделиться
Класснуть