|
1 тур - з 11.11 по 19.11.2018
точка входу для відправлення розв'язків
http://134.249.159.199//cgi-bin/new-client?contest_id=62
(скачати)
Задача 1. (100 балів)
Обмеження по пам'яті: 64Мб
Обмеження по часу: 1с
Ми в країні Ізічляндії, а це значить, що задачі будуть суперпрості.
У першій задачі нам задано рядок з букв англійського алфавіту довжини n. Серед них нам потрібно вибрати k букв так, що:
· Кожну з вибраних букв можна брати лише один раз
· Різниця між довільними двома вибраними буквами повинна бути більша одиниці, тобто не можна брати сусідні або рівні по алфавіту букви
· Серед всіх варіантів вибору, потрібно вибрати такий варіант, коли сума всіх букв (їх позицій в алфавіті) мінімальна
Нумерація букв починається з одиниці (a=1, b=2, ..., z=26). Букви можна вибирати в довільному порядку
Вхідні дані:
Перший рядок містить два числа n і k (1≤k≤n≤50) – довжина рядка і кількість букв, які потрібно вибрати.
Другий рядок містить рядок з малих літер англійського алфавіту довжини n.
Вихідні дані:
Виведіть одне число – суму всіх вибраних букв або -1, якщо вибрати k букв, описаним вище способом, неможливо.
Приклади:
|
Input.txt
|
Output.txt
|
|
1 1
a
|
1
|
|
7 4
problem
|
34
|
|
50 2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
|
-1
|
Задача 2. (100 балів)
Обмеження по пам'яті: 64Мб
Обмеження по часу: 1с
В Ізічляндії все настільки просто, що навіть експерименти робляться уявно. Один з таких експериментів зробимо і ми.
Нам потрібно пролетіти n планет і повернутися на початкову. Літати ми будемо на ракеті. Маршрут буде виглядати наступним чином: виліт з 1 планети – посадка на 2 – виліт з 2 – ... – посадка на планету n – виліт з планети n – посадка на планету 1.
Маса ракети складається з двох частин, а саме власне маси ракети і маси палива. Також, кожна планета має два коефіцієнта, які показують, скільки тонн ракети можна підняти або опустити, використавши одну тонну палива. Наприклад, якщо коефіцієнт вильоту або посадки рівний 6, а маси ракети і палива рівні 3 і 9, то потрібно буде витратити 2 тони палива на посадку або виліт. Після кожної такої операції, використане пальне викидається, відповідно маса зменшується. В нашому випадку, загальна маса була 12, а стала 10.
Ви хочете на ізі пролетіти всі планети, тому вам потрібно мінімізувати кількість пального, яке потрібно взяти з самого початку. Зверніть увагу, що кількість пального може бути нецілим числом.
Вхідні дані:
Перший рядок містить одне число n(1≤n≤1000) – кількість планет.
Другий рядок містить одне число m (1≤m≤1000) – маса власне ракети.
Третій рядок місить n чисел a1, a2, ..., an, (1≤ai≤1000) – маса, яку може підняти одна тонна палива на відповідній планеті.
Третій рядок місить n чисел b1, b2, ..., bn, (1≤bi≤1000) – маса, яку може посадити одна тонна палива на відповідній планеті.
Вихідні дані:
Якщо пролетіти всі планети неможливо або для цього потрібно більше ніж 109 тонн палива, виведіть -1. Інкаше, виведіть мінімальну кількість палива, необхідну для польоту, заокруглену до трьох знаків після коми.
Приклади:
|
Input.txt
|
Output.txt
|
|
4
4
2 3 2 2
2 3 4 3
|
284.000
|
|
3
3
1 2 1
2 2 2
|
-1
|
|
6
4
8 7 3 7 10 6
5 3 3 17 5 11
|
47.133
|
|
3
3
7 11 17
19 31 33
|
1.601
|
|
