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

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

HotLog


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

Задачи олимпиады "2й тур школьной олимпиады по Красноярскому краю"

Задача A. Гулливер

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

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

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

Входной файл INPUT.TXT содержит два целых числа, которые разделены пробелом: K – коэффициент, отражающий во сколько раз Гулливер больше лилипутов, и M – количество слоев матрацев (2 ≤ K, M ≤ 100).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12 28
212 4576

Задача B. Кипячение чая

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

В эту субботу у Васи день рождения и через 15 минут к нему придут гости. Ему срочно надо вскипятить чай, для того чтобы напоить им гостей. У Васи дома есть много литровых чайников (можно считать, что их бесконечное количество), а розетка всего одна. Т.к. вода кипятится очень долго, за 15 минут она успеет вскипятиться максимум один раз. Но Вася – мальчик не промах, он достал из кладовки N тройников, в i-том тройнике ai разъемов. Теперь Вася ломает голову: как ему соединить тройники и воткнуть эту систему в розетку, чтобы максимизировать количество чайников, которые он сможет поставить кипятить.

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

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

В первой строке входного файла INPUT.TXT содержится число N (1 ≤ N ≤ 105) – количество тройников. Во второй строке через пробел перечислены числа ai (1 ≤ ai ≤ 1000, 1 ≤ i ≤ N) – информация о тройниках.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
11
1
1
23
2 5 4
9

Задача C. Система пересекающихся множеств

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

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

Структура данных должна хранить n множеств, в каждое из которых могут входить натуральные числа от 1 до m, при этом одно и то же число может принадлежать нескольким множествам одновременно. Необходимо реализовать операции добавления элемента в множество, вывода всех элементов множества и вывода номеров всех множеств, в которых лежит данный элемент.

Реализуйте описанную структуру данных.

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

Первая строка входного файла INPUT.TXT содержит натуральные числа m и n (1 ≤ m, n ≤ 100). Вторая строка входного файла содержит натуральное число k –количество операций со структурой данных, которые необходимо выполнить (0 ≤ k ≤ 105).

Последующие k строк описывают эти операции. Описание операции может иметь один из трех форматов:

  • ADD element set – добавить элемент element (1 ≤ element ≤ m) в множество номер set (1 ≤ set ≤ n);
  • LISTSET set – вывести все элементы множества номер set (1 ≤ set ≤ n);
  • LISTSETSOF element – вывести номера всех множеств, содержащих элемент element (1 ≤ element ≤ m).

Общее количество операций LISTSET и LISTSETSOF не превышает 1000.

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

Для каждой операции LISTSET или LISTSETSOF в выходной файл OUTPUT.TXT выведите соответствующий список элементов (или номеров множеств) в порядке возрастания. Если список пуст, выведите -1. Порядок вывода должен соответствовать порядку, в котором операции заданы во входном файле.

Примеры

INPUT.TXTOUTPUT.TXT
110 10
5
ADD 1 1
ADD 1 2
ADD 2 1
LISTSET 1
LISTSETSOF 1
1 2
1 2
210 10
3
ADD 1 1
LISTSET 10
LISTSET 1
-1
1

Задача D. Игра «Flip-Flop»

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

В игре «Flip-Flop» используется прямоугольное поле 4×4 с двухсторонними фишками, расположенными на каждом из 16 квадратов. Одна сторона каждой фишки имеет черный цвет, а другая – белый. При каждом ходе происходит выбор клетки, рядом с которой (слева, справа, сверху, снизу и в центре) происходит инверсия от 3х до 5ти фишек таким образом, что они меняют свой цвет на противоположный.

Рассмотрим в качестве примера следующую позицию:

   bwbw
   wwww
   bbwb
   bwwb

Здесь «b» обозначает черный цвет лицевой стороны фишки, а «w» - белый. Если мы в качестве хода выбираем поле, расположенное в 3й строке и 1м столбце, то результат будет следующим:

   bwbw
   bwww
   wwwb
   wwwb

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

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

Входной файл INPUT.TXT содержит 4 строки по 4 символа «w» или «b» в каждой, описывающие цвета фишек.

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

В выходной файл OUTPUT.TXT выведите одно целое число – минимальное количество ходов, необходимых для достижения цели. Если исходная доска уже имеет набор фишек одинакового цвета, то следует вывести 0. Если решения не существует, то следует вывести слово «Impossible».

Примеры

INPUT.TXTOUTPUT.TXT
1 wbww
bbww
wwbb
wwbw
2
2 bwbw
wwww
bbwb
bwwb
Impossible


Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru