Застраховать квартиру в Ингосстрахе

I тур

Задача 1. “ПРОБИРКИ”.

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

Изначально одна из пробирок с рисками наполнена 100 миллилитрами кваса, а остальные две пустые. Требуется написать программу, которая выясняет, можно ли поместить в пробирку без рисок один миллилитр кваса, и если да, то находит минимально необходимое для этого число переливаний. Квас можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо вторая из пробирок (если она с рисками) не окажется заполненной до какой-либо риски.

Технические требования:

Входной файл: INPUT.TXT.

Выходной файл: OUTPUT.TXT.

Ограничение времени: 20 секунд.

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

В первой строке входного файла содержится число рисок N (1<=N<=20) на каждой из первых двух пробирок. Затем в порядке возрастания следуют N целых чисел V1, ..., VN (1<=Vi<=100), приписанных рискам. Последняя риска считается сделанной на верхнем крае пробирки (VN=100). Все числа разделяются пробелами и/или символами перевода строки.

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

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

Пример файлов входных и выходных данных

INPUT.TXT

 

OUTPUT.TXT

4

13 37 71 100

  Yes

10

Максимальное количество баллов за задачу – 35.

Задача 2. “КУСКИ”.

На плоскости задано N прямых. Напишите программу, которая определяет, на сколько кусков разбивают плоскость эти прямые.

Технические требования:

Входной файл: INPUT.TXT.

Выходной файл: OUTPUT.TXT.

Ограничение времени: 20 секунд.

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

Исходные данные во входном файле записаны в следующем порядке: N, a1, b1, c1, d1, ..., aN, bN, cN, dN, где 1<=N<=100, а пары чисел (ai, bi) и (ci, di) – вещественные координаты двух различных точек, через которые проходит прямая с номером i. Все данные разделяются пробелами и/или символами перевода строки.

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

В выходной файл необходимо вывести одно целое число – искомое количество кусков.

Пример файлов входных и выходных данных

INPUT.TXT

 

OUTPUT.TXT

3

0 0 0 2

0 2 2 0 2 0 0 0

  7

Максимальное количество баллов за задачу – 30.

Задача 3. “АБРАКАДАБРА”.

Последовательность из латинских букв строится следующим образом. Вначале она пуста. На каждом последующем шаге последовательность удваивается, после чего к ней слева дописывается очередная буква латинского алфавита (a, b, c, ...). Ниже приведены первые шаги построения последовательности:

Вначале. Пустая последовательность.

Шаг 1. a.

Шаг 2. baa.

Шаг 3. cbaabaa.

Шаг 4. dcbaabaacbaabaa.

....................................................................

Задача состоит в том, что по заданному числу N определить символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага.

Технические требования:

Входной файл: INPUT.TXT.

Выходной файл: OUTPUT.TXT.

Ограничение времени: 20 секунд.

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

Во входном файле записано одно натуральное число N (1<=N<226).

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

Запишите в выходной файл символ, стоящий в позиции N получившейся последовательности.

Пример файлов входных и выходных данных

INPUT.TXT

 

OUTPUT.TXT

4   w

Максимальное количество баллов за задачу – 35.

II тур

Задача 4. “ДВА КОНВЕЙЕРА”

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

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

Б) Находит такую перестановку заданных бутылок, при которой суммарное время разлива и закупорки бутылок было бы минимально, и определяет это время.

Технические требования:

Входной файл: INPUT.TXT.

Выходной файл: OUTPUT.TXT.

Ограничение времени: 20 секунд.

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

В первой строке входного файла содержится целое число N (1<=N<=1000) – количество бутылок. Далее идут N пар чисел X1 Y1 X2 Y2 .... XN YN. Здесь Xi означает время разлива, а Yi – время закупорки бутылки с номером i. Xi и Yi – неотрицательные целые числа, не превосходящие 1000000. Все числа разделяются пробелами и/или символами перевода строки.

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

Первая строка выходного файла должна содержать время, требуемое для исходной последовательности бутылок, вторая – минимально возможное время для пункта Б задачи. Третья строка должна содержать перестановку номеров бутылок от 1 до N, для которой достигается минимальное время.

Пример файлов входных и выходных данных

INPUT.TXT

 

OUTPUT.TXT

3

200 40

100 100

30 90

  490

370

3 2 1

Максимальное количество баллов за задачу – 30.

Задача 5. “НОК”.

Заданы два натуральных числа A и B (1<=A<=B<=10000). Требуется вычислить наименьшее общее кратное (НОК) всех целых чисел от A до B включительно, т.е. найти минимальное натуральное число, которое делится на A, A+1, ..., B.

Технические требования:

Входной файл: INPUT.TXT.

Выходной файл: OUTPUT.TXT.

Ограничение времени: 20 секунд.

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

Файл исходных данных содержит два числа A и B, разделенных пробелом.

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

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

Пример файлов входных и выходных данных

INPUT.TXT

 

OUTPUT.TXT

10 14   60060

Максимальное количество баллов за задачу – 35.

Задача 6. “СООБЩЕНИЕ”.

Из пункта А в пункт Б с помощью двух курьеров было отправлено сообщение, состоящее из символов 0 и 1. Каждый из курьеров шутки ради проделал несколько раз следующее преобразование сообщения: любую часть, содержащую две единицы записал в обратном порядке (перевернул). Например, в сообщении 11010100 курьер мог перевернуть подстроку, составленную из символов со 2 по 5 позиции, и тогда получалось сообщение 10101100. Получив два сообщения в пункте Б решили проверить их эквивалентность, т.е. можно ли получить одно из другого с помощью описанных преобразований.

Написать программу, которая:

Определяет эквивалентность сообщений;

Если сообщения эквивалентны, находит способ (достаточно только один) преобразования одного сообщения в другое.

Технические требования:

Входной файл: INPUT.TXT.

Выходной файл: OUTPUT.TXT.

Ограничение времени: 20 секунд.

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

Входной файл состоит из двух строк – полученных сообщений. Их длина не превышает 100 символов.

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

Если сообщения не эквивалентны, то выходной файл должен содержать только строку “No”. Если сообщения эквивалентны, то в первую строку выходного файла нужно вывести слово “Yes”, в последующие последовательность преобразований первого сообщения во второе. Каждое преобразование записывается в отдельной строке в виде пары чисел i, j (разделенных пробелом), означающей, что переворачивается подстрока, составленная из символов с номерами i, i+1, ..., j.

Пример файлов входных и выходных данных

INPUT.TXT

 

OUTPUT.TXT

100011100

001011001

  Yes

6 9

3 8

1 5

Максимальное количество баллов за задачу – 35.