Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Участник олимпиады разбирается с программой, которая шифрует пароль входа в систему. После работы эта программа выдает два натуральных числа, причем второе число получено из первого в результате замены некоторой непустой группы подряд идущих цифр первого числа на их сумму. Известно, что пароль – это группа цифр первого числа, замененная на их сумму во втором числе. Требуется написать программу, которая по двум числам определяет номера позиций первой и последней цифры группы, являющейся искомым паролем.

Входные данные

Входной файл содержит две строки. В первой строке записано первое число, состоящее не более чем из 100 000 цифр, во второй строке – второе число. Гарантируется, что числа не начинаются с нуля.

Выходные данные

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

Примечание

В первом примере группа цифр 148 заменятся на число 13 = 1 + 4 + 8.

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

  1. (оценивается в 30 баллов) Первое число меньше 109.

  2. (оценивается в 30 баллов) Первое число меньше 101000.

  3. (оценивается в 40 баллов) Первое число меньше 10100 000.

Примеры
Входные данные
2148
213
Выходные данные
2 4
Входные данные
8
8
Выходные данные
1 1
Входные данные
1223
1223
Выходные данные
1 1
Входные данные
10002
1002
Выходные данные
1 2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Антивирусная IT-компания имеет официальную иерархическую структуру управления. В ней есть босс – единственный сотрудник, над которым нет начальника. Каждый из остальных сотрудников подчинён ровно одному сотруднику – своему начальнику. Начальник может иметь нескольких подчинённых и отдавать или передавать приказы любому из них. Приказы могут передаваться от одного сотрудника другому только по цепочке, каждый раз от начальника к его подчинённому. Сотрудник А главнее сотрудника Б в этой иерархии, если А может отдать или передать приказ сотруднику Б непосредственно, или через цепочку подчинённых. Босс главнее любого сотрудника. Оказалось, что все сотрудники объединены ещё в одну организованную подобным образом тайную иерархическую структуру, производящую компьютерные вирусы. В тайной структуре может быть другой босс, а у сотрудников – другие начальники. Будем называть пару сотрудников А и Б устойчивой, если А главнее Б и в основной, и в тайной иерархических структурах. Требуется написать программу, определяющую количество устойчивых пар в компании.

Входные данные

В первой строке задано число N – количество сотрудников компании (1 ≤ N ≤ 100 000). Во второй строке – N целых чисел ai, где ai = 0, если в официальной иерархии сотрудник с номером i является боссом, в противном случае ai равно номеру непосредственного начальника сотрудника номер i. В третьей строке – N целых чисел bi, где bi = 0, если в тайной иерархии сотрудник с номером i является боссом, в противном случае bi равно номеру непосредственного начальника сотрудника номер i. Нумерация сотрудников ведется с единицы в том порядке, в каком они упомянуты во входном файле.

Выходные данные

Выходной файл должен содержать единственное число – количество устойчивых пар.

Примечание

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

  1. (оценивается в 25 баллов) Количество сотрудников N не превосходит 100.

  2. (оценивается в 25 баллов) Количество сотрудников N не превосходит 2000.

  3. (оценивается в 50 баллов) Количество сотрудников N не превосходит 105.

Примеры
Входные данные
3
0 3 1
0 1 1
Выходные данные
2
Входные данные
5
2 0 1 3 4
3 1 0 2 4
Выходные данные
7
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В давние времена Золотая Орда ежегодно собирала дань золотыми монетами. Известный крымский хан Гирей решил схитрить: выплачивая дань из N золотых монет, он подложил среди них одну фальшивую – более легкую монету. Об этом донесли казначею Золотой Орды. Для обнаружения подделки он решил использовать магические весы, работающие на урюке. На чаши магических весов кладутся две кучи монет. Весы устанавливают, совпадает или различается вес этих куч. При этом, если кучи имеют разный вес, то весы указывают, какая из куч легче. При совпадении веса обеих куч весы требуют R плодов урюка, а при несовпадении – U плодов. Казначей, сам любитель урюка, хочет и фальшивую монету обнаружить, и сэкономить на урюке. Требуется написать программу, которая по заданному количеству монет N, при условии, что только одна из них легче других, укажет минимальное количество урюка, с помощью которого эта фальшивая монета гарантированно будет обнаружена.

Входные данные

Во входном файле в единственной строке находятся три целых числа N, R и U (2 ≤ N ≤ 1 000 000, 1 ≤ R, U ≤ 1 000 000), где N – количество монет, R – количество плодов урюка, затрачиваемых в случае совпадения веса куч монет, U – количество плодов урюка, затрачиваемых в случае их различия. Все числа разделены пробелом.

Выходные данные

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

Примечание

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

  1. (оценивается в 40 баллов) N, U, R не превосходят 200.

  2. (оценивается в 30 баллов) N, U, R не превосходят 2000.

  3. (оценивается в 30 баллов) N, U, R не превосходят 1 000 000.

Примеры
Входные данные
4 3 1
Выходные данные
2
Входные данные
3 3 1
Выходные данные
3
Входные данные
15 2 3
Выходные данные
8
Входные данные
10 2 1
Выходные данные
3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Как известно, в 2012 году человечество с повышенным вниманием относится к древним календарям. Особый интерес представляют те из них, которые не заканчиваются 2012 годом. Потрясающее открытие в этом направлении сделано археологами Татарстана. В древних захоронениях oни обнаружили прямоугольную табличку, которая после расшифровки сохранившихся знаков была записана в виде таблицы, состоящей из N строк по M десятичных цифр в каждой. Но полностью расшифровать табличку не удалось, так как некоторые цифры стерлись. Утраченные цифры в таблице были заменены символами «*». По мнению археологов, найденная табличка представляет собой древний календарь, а записанные в ней M-значные числа являются номерами последовательных дней некоторого периода. Первое число является номером первого дня этого периода, а каждое следующее число на единицу больше предыдущего. По этому календарю конец света отсутствует, и после дня, обозначаемого с помощью M девяток, следует номер дня из M нулей. Требуется написать программу, которая восстанавливает утраченные цифры так, чтобы число в каждой строке таблицы, начиная со второй, было на единицу больше предыдущего, и выводит номер первого дня в найденном календаре.

Входные данные

В первой строке входного файла записаны натуральные числа N и M – количество строк в таблице и длина каждой строки соответственно (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000, M × N ≤ 100 000). Далее следуют N строк по M символов в каждой, состоящих только из десятичных цифр от 0 до 9 и символов «*».

Выходные данные

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

Примечание

Данная задача содержит три подзадачи.

  1. (оценивается в 40 баллов) 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100. В этой подзадаче исходные данные таковы, что в каждом столбце таблицы есть, по крайней мере, одна сохранившаяся цифра. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

  2. (оценивается в 30 баллов) 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100. В этой подзадаче хотя бы один столбец содержит только символы «*». Каждый тест в этой подзадаче оценивается отдельно.

  3. (оценивается в 30 баллов) 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000, M × N ≤ 100 000. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Примеры
Входные данные
1 2
23
Выходные данные
23
Входные данные
3 3
1**
*1*
**1
Выходные данные
109
Входные данные
2 3
9**
00*
Выходные данные
999
Входные данные
3 4
****
*0**
01**
Выходные данные
0098
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.

Входные данные

В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа Ai и Bi , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ Ai, Bi ≤ 109, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N1 и N2 – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ $N_1$ < $N_2$ ≤ N).

Выходные данные

Выходной файл должен содержать K строк, каждая из которых содержит два разделённых пробелом числа – номера элементов мозаики, образующих негармоничную пару в соответствующем наборе. Если решений несколько, можно вывести любое из них. Если в наборе негармоничная пара отсутствует, требуется вывести в соответствующей строке 0 0.

Примечание

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

  1. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 100, число наборов K ≤ 100.

  2. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 1000, число наборов K ≤ 1000.

  3. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 5000, число наборов K ≤ 5000.

  4. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 100 000, число наборов K ≤ 100 000.

Примеры
Входные данные
4
2 2
1 2
1 3
2 3
2
2 3
2 4
Выходные данные
0 0
4 2

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест