Турніри Школи Олімпійського Резерву "Step by Step"

Рекомендуємо ознайомитися з правилами участі у турнірах Школи Олімпійського Резерву "Step by Step"
Рейтинг учасників турнірів

Проблемний дует
класифікація: "medium"
дата старту: 2009-11-04
дата завершення: 2009-11-07
турнір проводить: Мельник В.І., Зубик В.В.
к-ть учасників:  19 
результати турніру

опис турніру:

Два автори, дві задачі, дві мови… Випробуйте свої сили на наших задачах. Даний турнір немає ніякого відношення до турів заочної олімпіади, яка зараз проводиться на нашому сайті.

Завдання на турнір >>
задача 1. "Hay"
кількість балів: 50

Наш спільний знайомий, Сергій Дмитрович, нагадав мені про існування процвітаючої ферми на Хмельниччині по відгодівлі кроликів і я вирішив озвучити для вас одну із проблем фермера Дієтенка.
Цього року літо видалося посушливим і на зиму Дієтенко не заготовив сіна. Як у нас уже прийнято, він звернувся по допомогу до фермера Джона з країни, де сіна є вдосталь. Дієтенко замовив контейнер ємністю O для закупівлі сіна. Джон може продати К в’язок сіна кожна об’ємом Vi. В’язки сіна гнучкі і можуть заповнювати будь-який вільний простір такого ж об’єму.
Дієтенко хоче знати, яку найбільшу кількість сіна він зможе привезти в своєму контейнері. Допоможете? Напишіть програму, що вирішить цю сінну проблему Дієтенка.

Формат вхідних даних. У першому рядку вхідного файлу hay.in міститься два цілих числа О (1 <= О <= 50000) та К (1 <= К <= 5000). У наступних К рядках містяться наявні об’єми в’язок Джона Vi (1 <= Vi <= О).

Формат вихідних даних. У вихідний файл hay.out вивести одне число – максимальний об’єм сіна, що зможе вивезти Дієтенко.

Приклад вхідних та вихідних даних.
hay.in
8 3
3
6
4

hay.out
7

 

задача 2. "Schools"
кількість балів: 50

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

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

Входные данные
В первой строке входного файла SCHOOLS.IN находятся два натуральных числа, разделенных пробелом: N (3 <= N <= 100), количество школ в городе, и M - количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1 <= Ci <= 300) от школы Ai до школы Bi (i=1,2, ...,N).

Пример входного файла
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

Выходные данные
В единственной строке выходного файла SCHOOLS.OUT должны содержаться два натуральных числа S1 и S2, разделенных пробелом - две наименьшие стоимости схем (S1<=S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.

Пример выходного файла
110 121

 


назад у розділ "Турніри"