| Завдання 1 туру 2018 |
|
| Написав Ковальчук Максим | ||||||||||||||||||
| Неділя, 11 листопада 2018, 22:04 | ||||||||||||||||||
|
1 тур - з 11.11 по 19.11.2018 точка входу для відправлення розв'язків (скачати) Задача 1. (100 балів) Обмеження по пам'яті: 64Мб Обмеження по часу: 1с Ми в країні Ізічляндії, а це значить, що задачі будуть суперпрості. У першій задачі нам задано рядок з букв англійського алфавіту довжини n. Серед них нам потрібно вибрати k букв так, що: · Кожну з вибраних букв можна брати лише один раз · Різниця між довільними двома вибраними буквами повинна бути більша одиниці, тобто не можна брати сусідні або рівні по алфавіту букви · Серед всіх варіантів вибору, потрібно вибрати такий варіант, коли сума всіх букв (їх позицій в алфавіті) мінімальна Нумерація букв починається з одиниці (a=1, b=2, ..., z=26). Букви можна вибирати в довільному порядку Вхідні дані: Перший рядок містить два числа n і k (1≤k≤n≤50) – довжина рядка і кількість букв, які потрібно вибрати. Другий рядок містить рядок з малих літер англійського алфавіту довжини n. Вихідні дані: Виведіть одне число – суму всіх вибраних букв або -1, якщо вибрати k букв, описаним вище способом, неможливо. Приклади:
Задача 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. Інкаше, виведіть мінімальну кількість палива, необхідну для польоту, заокруглену до трьох знаків після коми. Приклади:
|