Страница: << 101 102 103 104 105 106 107 >> Отображать по:

#111183

Расписание турнира

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

Как известно, командные спортивные соревнования часто проводятся по круговой системе, когда любые две команды должны сыграть между собой ровно один матч. Круговой турнир проводится в несколько туров, в одном туре каждая команда может сыграть не более одного матча. Например, если в турнире участвуют 4 команды, то турнир можно провести в три тура: в первом туре команда 1 играет с командой 2, а команда 3 играет с командой 4, во втором туре 1 играет с 3, а 2 играет с 4, в третьем туре — 1 играет с 4, а 2 играет c 3.

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

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

Во входном файле записано одно натуральное число N — количество команд, участвующих в турнире (2 ≤ N ≤ 100).

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

В первой строке выведите минимальное количество туров K, необходимых для проведения кругового турнира из N команд. Каждая из K следующих строк содержит описание одного тура. В начале строки выведите количество игр n_i, которое необходимо сыграть в i-м туре. Далее идет n_i пар чисел — команды, которые играют в этом туре. Команды, играющие между собой, разделяются символом «-» (минус), а разные игры разделяются пробелом.

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

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

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

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

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

Примечание

Online-группа тестов содержит тесты для N ≤ 10 и оценивается в 40 баллов.

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

#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.

#111221

Пароль

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

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

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

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

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

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

Примечание

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

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

(оценивается в 30 баллов) Первое число меньше 10⁹.
(оценивается в 30 баллов) Первое число меньше 10¹⁰⁰⁰.
(оценивается в 40 баллов) Первое число меньше 10^100 000.

Примеры

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

2148
213

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

2 4

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

8
8

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

1 1

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

1223
1223

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

1 1

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

10002
1002

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

1 2

#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

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

Страница: << 101 102 103 104 105 106 107 >> Отображать по:

Выбрано

Отменить

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

Правильно (разрешается разный отступ в блоках «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)