Задачи командных соревнований областной олимпиады школьников по информатике 2004

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

Во входном файле содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`) – количество камней в кучке.

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

4

1

3

0

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

Во входном файле в первой строке содержится целое число `N` (`1\ ≤\ N\ ≤\ 1000`) – количество карточек на столе. Далее следует `N` строк, каждая из которых содержит четыре разделенных пробелами целых числа `x`, `y`, `w`, `h`, – координаты левого нижнего угла карточки, ширина и высота карточки (все числа целые и находятся в диапазоне от 1 до 10000). Координаты (0,0) соответствуют левому нижнему углу стола. Координаты и размеры карточек перечисляются в том порядке, в котором они выкладывались на стол, т.е. координаты и размеры искомой карточки находятся по второй строке входного файла.

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

3
10 10 25 20
20 5 30 15
15 15 25 25

125

2
10 10 20 30
10 10 20 30

0

Определите максимальный размер шара, который можно спрятать под "колпаком" – круглым прямым конусом (основание является кругом, ось конуса перпендикулярна основанию).

Во входном файле в первой строке содержится два числа, разделенных пробелом – длина образующей конуса `L` (`1\ ≤\ L\ ≤\ 100`) и диаметр основания `D` (`1\ ≤\ D\ <\ 2*L`).

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

5.0 6.0

1.5000

Однажды, сидя на диване после очередного чаепития, Мартовский Заяц лениво опустил взгляд вниз на пол. "О Боже, сколько у нас забывчивых гостей. Весь пол завален тапочками, разных размеров, левых, правых… ужас. Надо навести порядок" – подумал Заяц.

Помогите Мартовскому Зайцу собрать как можно больше пар тапочек из этой кучи. Одна пара состоит из двух тапок (левого и правого) одинакового размера.

Во входном файле в первой строке содержится число `N` (`0\ <\ N\ ≤\ 10^5`) – количество тапочек. Далее следует `N` строк, каждая описывает один тапок и содержит одно целое число `R` (`0\ <\ |R|\ ≤\ 10000`), описывающее один тапок. Размер тапка равен модулю числа `R`. Если число `R` положительно, то тапок левый, а если отрицательно, то правый.

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

10
1
-2
5
-10
-5
-5
2
-7
-7
-1

3

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть задана строка, в которой записано слово `S`, состоящее из `N` прописных букв латинского алфавита. Путем вычеркивания из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно пустого) набора символов, чтобы образованные таким образом строки являлись палиндромами. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми. Палиндромы, образованными даже одинаковыми буквами, стоящими на разных позициях исходной строки, считаются различными.

Во входном файле в первой строке записано слово `S` (`1\ ≤\ N\ ≤\ 60`).

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

BAOBAB

22

Некоторые города имеют сеть метро в форме дерева, т.е. для любой пары станций есть один и только способ добраться с одной станции на другую. Такие сети метро имеют уникальную центральную станцию. Представьте, что вы турист в таком городе и хотите изучить всю сеть метро. Вы стартуете на центральной станции, выбираете случайно одно из направлений и едете в вагоне на следующую станцию. Всякий раз, прибывая на станцию, вы выбираете одну из веток, по которой еще не ездили. Если таких веток на текущей станции не осталось, вы отправляетесь назад на ту станцию, откуда приехали на эту станцию в первый раз. Так продолжается до тех пор, пока вы не проедете по всем веткам дважды (по разу в каждом направлении). В этот момент вы должны быть на центральной станции. Такое путешествие можно закодировать как двоичную строку следующим образом. Цифрой 0 кодируется поездка, которая отдаляет нас от центральной станции, а цифрой 1 – поездка, которая приближает к центральной станции. Существует несколько возможных кодирующих строк для одной и той же сети метро, так как "неисследованные" ветки выбираются случайным образом.

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

В первой строке входного файла содержится целое число `N` (`1\ ≤\ N\ ≤\ 20`) – количество тестов. Далее следует `N` пар строк, состоящих из цифр 0 и 1, длиной не более 3000 символов. В каждой строке закодировано одно корректное обследование сети метро.

В выходной файл для каждой пары строк вывести сообщение "same", если обе строки кодируют обследование одной и той же сети метро, или сообщение "different", если исследованные сети метро являются различными.

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

same
different

Маг в маске: "Назовите два целых числа, больших десяти и не содержащих нулей".

Зрители: "126 и 4138".

Маг в маске: "Хорошо, теперь переставьте цифры произвольным образом в каждом из этих чисел и найдите с помощью калькулятора произведение новых чисел. Сделали? Вычерните любую ненулевую цифру из результата и назовите оставшиеся цифры в любом порядке".

Зрители: "608981" (Были перемножены числа 612 и 3184, и получен результат 1948608)

Маг в маске: "Вы зачеркнули цифру 4".

Разгадайте секрет фокуса и напишите программу, которая покажет этот трюк не хуже фокусника.

Во входном файле в первой строке содержится первое названное число `A` (`10\ <\ A\ <\ 10^100`), во второй строке второе число `B` (`10\ <\ B\ <\ 10^100`), в третьей строке цифры результата в произвольном порядке после вычеркивания цифры.

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

126
4138
608981

4