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

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

HotLog


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

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

Задача A. Рыболовная сеть

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

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

Сеть имеет прямоугольную форму размером M×N узлов, все смежные узлы соединены леской. Под разрывом будем понимать только единичный обрыв лески между двумя смежными узлами сети.

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа M и N через пробел – размеры рыболовной сети (1 ≤ M, N ≤ 10 000).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12 21
22 32

Задача B. Ремонт

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

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

Давно ходят слухи, что бригадир в дядюшкиной фирме покупает лишнее количество стройматериалов, а остатки использует для отделки своей новой дачи. Ваш дядя заинтересовался, сколько в действительности банок краски необходимо для покраски стен в офисе длиной L метров, шириной – W и высотой – H, если одной банки хватает на 16м2, а размерами дверей и окон можно пренебречь? Заказов много, поэтому дядя попросил написать программу, которая будет все это считать.

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

Первая строка входного файла INPUT.TXT содержит три натуральных числа L, W, H через пробел – длину, ширину и высоту офиса в метрах соответственно. Каждое из них не превышает 1000.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
18 8 24
21 1 31

Задача C. NEERC

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

В полуфинале студенческого чемпионата мира по программированию NEERC (http://neerc.ifmo.ru) участвуют команды из n институтов. Участники для проведения соревнований распределяются по k залам, каждый из которых имеет размеры, достаточные для размещения всех команд от всех институтов. При этом по правилам соревнований в одном зале может находиться не более одной команды от института.

Многие институты уже подали заявки на участие в полуфинале. Оргкомитет полуфинала хочет допустить до участия максимально возможное количество команд. При этом, разумеется, должна существовать возможность рассадить их по залам без нарушения правил.

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

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

Первая строка входного файла INPUT.TXT содержит число n - число институтов, подавших заявки. Вторая строка входного файла содержит n чисел a1, …, an (ai - это количество команд, заявленных от института номер i). Последняя строка входного файла содержит число k - количество залов, в которых проходят соревнования.

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13
1 2 4
3
6
23
1 2 4
4
7

Задача D. Забор - 2

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

Времена Советского Союза уже давно стали историей. И к рассказам о событиях, происходивших тогда, только в России могут относиться не как к анекдотам. Попробуйте мысленно перенестись в те времена.

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

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

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

В первой строке входного файла INPUT.TXT записано натуральное число n, количество фрагментов на складе (n ≤ 100). На второй строке содержатся n натуральных чисел, не превосходящих 1000 - длины фрагментов забора.

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

В выходной файл OUTPUT.TXT выведите максимальное значение площади участка, который может соорудить директор и номера фрагментов, из которых может получиться максимальный участок в произвольном порядке. Ответ следует выводить с точностью, не меньшей, чем 6 знаков после запятой. В случае, если создать участок ненулевой площади нельзя, выведите -1.

Примеры

INPUT.TXTOUTPUT.TXT
13
1 1 1
0.4330127018922193
1 2 3
24
1 2 4 7
-1


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