Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Одиннадцатая личная олимпиада"

Задача A. Золотые слитки

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

Теперь Джон и Боб хотят поделить слитки так, чтобы каждому из них досталось равное количество золота. Им не хотелось бы пилить слитки, но деваться некуда. Обсудив ситуацию, они решили, что если смогут, поделят добычу как есть, а если нет, то сумеют-таки распилить один слиток на две части. Распилить два или все три слитка они уже не смогут.

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

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

Входной файл INPUT.TXT содержит три целых числа: x1, x2 и x3 (1 ≤ xi ≤ 108, сумма весов слитков чётна).

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

В выходной файл OUTPUT.TXT выведите -1, если невозможно распилить один слиток таким образом, что после этого можно поделить золото поровну. Если Джон и Боб и так могут поделить золото поровну, выведите 0. В противном случае на первой строке выведите число 1, если следует распилить первый слиток, 2, если следует распилить второй слиток, либо 3, если следует распилить третий слиток. На второй строке выведите два положительных целых числа: веса частей, на которые следует распилить слиток. В сумме две части должны давать исходный вес слитка. Так как суммарный вес золота чётен, слиток всегда требуется распиливать на части, имеющие целый вес. Если возможных решений несколько, выведите любое.

Пример

INPUT.TXTOUTPUT.TXT
12 3 32
2 1

Задача B. Шахматная мастерская

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Хозяин мастерской по изготовлению шахматных досок гроссмейстер Хосе Раулевич Капабланка был очень зол. «Ну, кто так раскрашивает доски?! Ну скажи мне, Бобби, разве я тебя так учил раскрашивать доски?!» - спрашивал он у своего подмастерья.

А дело было вот в чем. Недавно его мастерская получила заказ на изготовление нестандартной шахматной доски размером N на M . Саму шахматную доску из дорогой породы дерева он изготовил, а раскрасить ее поля он поручил своему подмастерью и ученику Бобби. Бобби, однако, справился с этой задачей очень плохо. Он раскрасил доску так, что некоторые соседние поля оказались покрашенными в один цвет. А такого на шахматной доске никогда не было, и быть не может!

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

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

Соседними полями на шахматной доске Хосе Раулевич считает поля, имеющие общую сторону.

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

Первая строка входного файла INPUT.TXT содержит два целых числа: N и M (1 ≤ N, M ≤ 100). Далее идут N строк по M символов в каждой. j-ый символ i-ой из этих строк равен W, если Бобби покрасил соответствующее (т.е. находящееся на пересечении i-ой горизонтали и j-ой вертикали) поле в белый цвет, и B, если в черный.

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

В первой строке выходного файла OUTPUT.TXT выведите минимальное количество k полей, которые должен перекрасить Бобби.

Далее выведите k строк, описывающих поля, которые он должен перекрасить. Описание каждого поля должно состоять из двух чисел: i и j (1 ≤ i ≤ N, 1 ≤ j ≤ M), задающих горизонталь и вертикаль, на пересечении которых находится данное поле.

Ни одно поле не должно быть указано в этом списке дважды. Может оказаться так, что k = 0, и Хосе Раулевич зря кричал на Бобби. Впрочем, это объясняется тем, что гроссмейстер уже весьма стар и его зрение далеко не идеально.

Примеры

INPUT.TXTOUTPUT.TXT
14 4
BBBB
BBBB
BBBB
BBBB
8
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4
23 3
WBW
BWB
WBW
0

Задача C. Три буквы

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Напомним, что cтрока B = b1b2b3...bm, является подпоследовательностью строки A = a1a2a3...an, если существует строго возрастающая последовательность {i1, i2, i3, ... , im} индексов A, такая, что для всех j от 1 до m выполняется Aij=Bj. Например, B = ”aba” является подпоследовательностью строки A = ”abacaba”. Последовательность индексов в этом случае может быть такой: {1, 2, 3}.

Пусть Вам дана строка S, состоящая только из маленьких букв английского алфавита. Ваша задача заключается в том, чтобы посчитать количество ее подпоследовательностей “abc”.

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

Входной файл INPUT.TXT содержит строку S, длиной не более 105 символов.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
1abc1
2ab0

Задача D. Веревочный мост

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

Помогите путешественникам как можно быстрее перебраться через мост. Требуется написать программу, определяющую минимальное время, которое потребуется для такого перехода. Например, если N=4, а время, требуемое для перехода по мосту для каждого, составляет 5, 10, 20 и 25 минут соответственно, то наименьшее время, требуемое для пересечения моста, составит ровно 60 минут.

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

В первой строке входного файла INPUT.TXT содержится натуральное число N – количество путешественников (N ≤ 105). Во второй строке располагаются N натуральных чисел – скорости всех путников, разделенные пробелом и не превосходящие 106. Здесь под скоростью человека понимается время в минутах, необходимое для перехода через мост.

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

В выходной файл OUTPUT.TXT выведите одно целое число – минимально возможное время, необходимое путникам для пересечения моста.

Примеры

INPUT.TXTOUTPUT.TXT
12
10 20
20
24
5 10 20 25
60


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483