Страница: << 78 79 80 81 82 83 84 >> Отображать по:

#111182

Числа

Темы: [Сортировка подсчетом]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача B ]

Саша и Катя учатся в начальной школе. Для изучения арифметики при этом используются карточки, на которых написаны цифры (на каждой карточке написана ровно одна цифра). Однажды они пришли на урок математики, и Саша, используя все свои карточки, показал число A, а Катя показала число B. Учитель тогда захотел дать им такую задачу, чтобы ответ на нее смогли показать и Саша, и Катя, каждый используя только свои карточки. При этом учитель хочет, чтобы искомое число было максимально возможным.

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

Во входном файле записано два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100 000 цифр.

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

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

Примеры тестов

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

280138
798081

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

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

123
456

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

-1

Примечание

Online-группа тестов оценивается в 60 баллов, в этой группе числа A и B содержат не более 1000 цифр каждое. При этом решения, правильно работающие для случая, когда A и B содержат не более 6 цифр, будут оценены не менее, чем в 20 баллов. Решения, правильно работающие для случая, когда A и B содержат не более 9 цифр, будут оценены не менее, чем в 40 баллов.

Offline-группа тестов оценивается в 40 баллов.

#111184

Питон

Темы: [Строки]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача D ]

Витя изучает новый язык программирования Питон. Пока он только успел изучить арифметические операции и условную инструкцию «if», но он уже полюбил этот язык за красоту и лаконичность синтаксиса.

Отличительной особенностью языка Питон является то, что блоки после инструкций «if» и «else» (а также в циклах «for» и «while», но Витя еще не успел изучить циклы) выделяются не ключевыми словами (например, в языке Паскаль используются слова «begin» и «end») и не скобками (например, в языке C используются фигурные скобки), а величиной отступа от начала строки, то есть количеством пробелов, которые идут в начале строки. Например, в такой программе:


if a < 0:
    print("Число a - отрицательное")
    a = -a
print("Теперь a - положительное")

если условие «a < 0» будет истинно, то выполнятся две следующие строки «print("Число a - отрицательное")» и «a = -a», а вот следующая строка «print("Теперь a - положительное")» уже находится вне блока условной инструкции «if» и будет выполнена после этой условной инструкции независимо от истинности проверенного условия.

Более формально правила расстановки пробелов в программе такие. Первая строка программы, а также все инструкции в программе, если они не находятся внутри блоков условных инструкций, не содержат отступа, то есть пробелов в начале строки. Если в программе встречается условная инструкция «if», то блок после этой инструкции пишется с отступом. Величина отступа может быть произвольной (1, 2, 3 и более пробелов), но для всех инструкций внутри блока отступ должен быть одинаковым. Если после инструкции «if» идет инструкция «else», то она должна иметь такой же отступ, что и соответствующая ей инструкция «if», после инструкции «else» идет блок из одной и более инструкций с дополнительным отступом. При этом отступ у блока «if» и блока соответствующего ему «else» может быть различным (смотрите примеры верных программ ниже), но внутри одного блока отступ должен быть одинаковым.

Каждой инструкции «if» может соответствовать не более одной инструкции «else». Не допускаются инструкции «else», перед которыми нет инструкции «if». После каждой инструкции «if» и «else» обязательно следует хотя бы одна инструкция с отступом.

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

Правильно (разрешается разный отступ в блоках «if» и «else») Правильно (вложенные условные инструкции) Неправильно (разный отступ в одном блоке) Неправильно (нет блока с отступом после инструкции «if»)

if x > 0: print("x > 0") print(x) else: print("x < 0") print(-x) print("Bye")

if a > b: if a > c: print(a) else: print(c) else: if b > c: print(b) else: print(c)

if x > 0: print(x) print("x > 0")

if x > 0: else: print(x)

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

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

Во входном файле записан некоторый текст, содержащий не более 100 строк. Длина каждой строки не превосходит 100 символов. Каждая строка состоит из символов, ASCII-коды которых не менее 32 и не более 126.

Строка считается инструкцией «if», если первыми непробельными символами строки является слово «if», после которого идет пробел, а затем — любое число любых символов. Строка считается инструкцией «else», если она содержит только одно слово «else:» (с двоеточием после него) и, возможно, отступ в начале строки.

Любая строка содержит хотя бы один непробельный символ. Последняя строка программы обязательно содержит ровно одно слово «exit()» без пробелов, завершающееся символом конца строки.

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

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

Примеры тестов

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

a, b, c = map(int, input().split())
if a > b:
    if a > c:
        print(a)
    else:
        print(c)
else:
    if b > c:
      print(b)
    else:
          print(c)
exit()

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

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

x = int(input())
if x < 0:
  print("Negative")
    x = -x
else:
    print("Positive")
exit()

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

Примечание

Online-группа тестов оценивается в 50 баллов. Тесты этой группы не содержат инструкции «else».

Offline-группа тестов оценивается в 50 баллов.

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

#111185

K-квест

Темы: [Быстрая сортировка] [Бинарный поиск в массиве]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2012, Задача E ]

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

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

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

В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 10⁹, K ≠ 0). Во второй строке через пробел записаны N целых чисел a₁, a₂, ..., a_N — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

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

Примеры тестов

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

5 3
-2 2 -1 2 4

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

2 4

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

7 1
1 -1 1 -1 1 -1 2

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

5 5

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

4 3
2 2 2 2

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

-1

Примечание

Тесты по этой задачи разбиты на группы. На 1-3 группах тестов проверка проводится во время тура (online), на последней группе — после окончания тура (offline).

В первой группе тестов 1 ≤ N ≤ 100, |a_i| ≤ 100. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

Во второй группе тестов 1 ≤ N ≤ 2000, |a_i| ≤ 1 000 000. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

В третьей группе тестов 1 ≤ N ≤ 200 000, 0 ≤ a_i ≤ 10⁹. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

В четвертой группе тестов 1 ≤ N ≤ 200 000, |a_i| ≤ 10⁹. Каждый тест этой группы оценивается отдельно. Общее число баллов за тесты этой группы равно 40.

#111222

Вирусы и антивирусы

Темы: [Обход в глубину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача B ]

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

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

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

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

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

Примечание

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

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

Примеры

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

3
0 3 1
0 1 1

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

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

5
2 0 1 3 4
3 1 0 2 4

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

#111225

Мозаика

Темы: [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача E ]

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

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

В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа A_i и B_i , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ A_i, B_i ≤ 10⁹, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N₁ и N₂ – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ \(N_1\) < \(N_2\) ≤ N).

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

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

Примечание

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

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

Примеры

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

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

0 0
4 2

Страница: << 78 79 80 81 82 83 84 >> Отображать по:

Выбрано

Отменить

Добавить в контест

Правильно (разрешается разный отступ в блоках «if» и «else»)	Правильно (вложенные условные инструкции)	Неправильно (разный отступ в одном блоке)	Неправильно (нет блока с отступом после инструкции «if»)
if x > 0: print("x > 0") print(x) else: print("x < 0") print(-x) print("Bye")	if a > b: if a > c: print(a) else: print(c) else: if b > c: print(b) else: print(c)	if x > 0: print(x) print("x > 0")	if x > 0: else: print(x)