Олимпиада по информатике 2010

II этап Всеукраинской олимпиады по информатике для 8-11 классов.

Содержание



Зернышки

В банке находятся белые и черные зернышки. Каждый раз из банки вынимают наугад два зернышка. Если они одинакового цвета, то их выбрасывают, а в банку кладут черное зернышко (черных зернышек достаточное количество). Если же зернышки разного цвета, то черное зернышко выбрасывают, а белое возвращают в банку. Эти действия повторяют, пока не останется одно зернышко.

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

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

В единственной строке записаны два числа — количество белых и черных зернышек.

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

Единственная строка выходного текстового файла должна содержать цвет оставшегося зернышка: white — если зернышко белое, black — если зернышко черное.

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

input.txt output.txt
4 3 black

Наибольшее произведение

Дано N целых чисел.
Необходимо выбрать из N целых чисел три таких числа, произведение которых максимально.

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

Первая строка входного файла содержит одно число N — количество чисел в последовательности (3≤N≤106). Во второй строке записана сама последовательность: N целых чисел, которые по модулю не превышают 30000.

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

В выходной файл выведите три искомых числа в произвольном порядке. Если существует несколько разных троек чисел, которые дают максимальное произведение, то выведите произвольную из них.

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

input.txt output.txt
9
3 5 1 7 9 0 9 -3 10
9 10 9
3
-5 -30000 -12
-5 -30000 -12

Покупка билетов

За билетами на премьеру нового мюзикла собралась очередь из N лиц, каждое из которых хочет купить 1 билет. На всю очередь работала только одна касса, потому продажа билетов продвигалась очень медленно, от чего «клиенты» очереди впадали в отчаяние. Самые сообразительные быстро приметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким людям, которые стоят рядом, отдавать деньги первому из них, чтобы он купил билеты на всех.

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

Известно, что на продажу i лицу из очереди одного билета кассир тратит Аi, секунд, на продажу двух билетов — Вi секунд, трёх билетов — Сi секунд.

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

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

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

Первая строка входного файла содержит единственное число N — количество покупателей в очереди (1≤N≤5000). В каждой из следующих N строк записана тройка натуральных чисел Аi, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.

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

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

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

input.txt output.txt
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
12
2
3 4 5
1 1 1
4

Оставить комментарий