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

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

Приваблива жадність
класифікація: "medium"
дата старту: 2009-04-08
дата завершення: 2009-04-14
турнір проводить: Зубик В.В.
к-ть учасників:  12 
результати турніру

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

«Жадность - не порок, а способ решения»

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

Петрик навчився добре додавати числа і тепер він поставив перед собою завдання: навчитися ще додавати їх дешево. Ціною додавання двох чисел Петрик визначив їх суму. Таким чином вартість додавання 1 і 10 буде рівна 11. З двома числами все виглядає достатньо просто, але якщо взяти більше чисел, то додати їх якнайдешевше виходить не зовсім легко.
Наприклад, додавати числа 1, 2 и 3 можна одним із трьох способів:

1 + 2 = 3, вартість 3
3 + 3 = 6, вартість 6
Загальна вартість 9

1 + 3 = 4, вартість 4
4 + 2 = 6, вартість 6
Загальна вартість 10

2 + 3 = 5, вартість 5
1 + 5 = 6, вартість 6
Загальна вартість 11

Неозброєним оком видно, що перший спосіб додавання є самим дешевим.
Напишіть програму, що допоможе Петрику визначити найменшу вартість додавання чисел.

Формат вхідних даних. Вхідного файла add.in містить декілька тестів. Перший рядок кожного тесту містить N (2 < N < 500) – кількість чисел у тесті. Другий рядок тесту містить N натуральних чисел, що не перевищують 100000. Останній рядок вхідного файлу містить N=0 і не обробляється.

Формат вихідних даних. Вихідний файл add.out для кожного тесту містить найменшу вартість додавання чисел.

Приклад вхідних та вихідних даних.
add.in
3
1 2 3
4
1 2 3 4
0

add.out
9
19

 

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

Група пластунів збирається вночі перейти річку через аварійний міст. Вони мають лише одного ліхтаря, а через міст може рухатися одночасно не більше двох пластунів і один із них несе ліхтар. Для кожного пластуна відомий час, за який він може перейти через міст. Якщо через міст рухається двоє пластунів, то час їх руху дорівнює часу більш повільного пластуна.
Необхідно знайти мінімальний час, за який всі пластуни зможуть перебратися через річку, а також вивести послідовність переходів у форматі, зазначеному у прикладі.

Формат вхідних даних. Перший рядок вхідного файлу scouts.in містить кількість тестів і за ним слідує порожній рядок. Тести також розділяються порожнім рядком. Перший рядок кожного тесту містить кількість пластунів N (N<=1000). У наступних N рядках задається час переходу мосту кожним із пластунів. Час не перевищує 100 с.

Формат вихідних даних. Вихідні дані слід виводити у файл scouts.out. Перший рядок для кожного тесту містить мінімальний час, за який пластуни зможуть перейти на наступний берег. Дальше в кожному рядку міститься стратегія переходу пластунів через міст. Так кожен рядок містить одне або два числа, що характеризують пластунів, які ідуть по мосту з ліхтарем. Якщо існує кілька рівноцінних стратегій, то слід виводити будь-яку із них. Дані для кожного із тестів слід розділяти порожнім рядком.

Приклад вхідних та вихідних даних.

scouts.in
1

4
1
2
5
10

scouts.out
17
1 2
1
5 10
2
1 2

 

задача 3. "Strings"
кількість балів: 30

Назвемо словом довільну послідовність символів латинського алфавіту. Треба по двох даних словах визначити чи є перше слово підпослідовністю другого.

Формат вхідних даних. Кожен рядок вхідного файлу strings.in містить один тест: два слова, довжиною не більших 10^6 символів. Слова розділені пропуском.

Формат вихідних даних. Для кожного тесту у вихідний файл strings.out вивести в окремому рядку 'Yes' або 'No' в залежності від того, чи є перше слово підпослідовністю другого.

Приклад вхідних та вихідних даних.

strings.in
sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

strings.out
Yes
No
Yes
No

 


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