Задача А-Коефіцієнт
Ліміт часу: 1 с Ліміт пам'яті: 64 Мбт
Фермер Василь зібрав гарний врожай і вирішив відсвяткувати «Свято урожаю» у місцевій корчмі. Після гарно проведеного часу він вирішив розрахуватись із господарем. У Василя була всього одна велика купюра, а у господаря – кілька дрібних монет. Так, як господар завжди економив дрібні монети, то здачу вирішив дати найменшою кількістю монет. Оскільки господар не друже з математикою, та й Василь кілька раз пригостив, то точно визначити, яку кількість монет йому прийдеться повернути Василю він не в змозі. Допоможіть розв’язати цю проблему.
Вхідні дані:
У першому рядку записано число N (1 ≤ N ≤ 10) – кількість різних номіналів, які є у господаря. Вважатимемо, що монет кожного номіналу є достатньо. У другому рядку записані N цілих чисел ai (0 < ai ≤ 2000) – номінали монет. Третій рядок містить одне число k (1 ≤ k ≤1000000) – суму, яку потрібно набрати господарю.
Вихідні дані:
Вивести одне число – мінімальну кількість монет, яку господар віддасть Василю, або –1, якщо господар не зможе дати здачу.
Приклад вхідних та вихідних даних.
Приклад вхідних даних: | Приклад вихідних даних: | 3
1 2 5
14 | 4
| 4
9 5 6 7
8 | -1
|
Задача В-Степан на уроці англійської мови
Ліміт часу: 1 с Ліміт пам'яті: 64 Мбт
Сьогодні на уроці англійської мови Степан вивчив нову тему – подібні слова. Йому настільки сподобався вивчений матеріал, що він вирішив підготувати задачу на дану тему. Отже, два слова s і t називаються подібними, якщо вони однакові (s=t), або ж однаковими є слова s і t’(s =t’), де t’ – слово отримане із t записом символів у зворотному порядку. Наприклад, слова ‘baba’ і ‘abab’ подібні, а слова ‘aba’ і ‘abb’ ні. Необхідно порахувати максимально можливе число попарно неподібних слів довжини n над першими k символами алфавіту. Наприклад, при n=3 і k=2 є максимум шість попарно неподібних слів: ‘aaa’,’aab’,’aba’,’abb’,’bab’,’bbb’.
Вхідні дані:
У першому рядку записано число n (1 ≤ n ≤ 109) і k (1 ≤ k ≤ 109).
Вихідні дані:
Оскільки Степан не запам’ятовує великі числа, то виведіть залишок від ділення шуканої кількості на 109+7.
Приклад вхідних та вихідних даних.
Приклад вхідних даних: | Приклад вихідних даних: | 3 2
| 6
|
Задача В-Степан на уроці фізики
Ліміт часу: 1 с Ліміт пам'яті: 64 Мбт
Степан розробляє електронну схему на прямокутній сітці розміром N*M. Усього N*M квадратних плиток. Два (з чотирьох) протилежних кути кожної плитки з'єднані дротом. Джерело живлення під’єднано до лівого верхнього кута сітки, лампа - до правого нижнього. Для того щоб увімкнути лампу можна повернути будь-яку плитку на 90 градусів у обох напрямках.
На зображені лампа вимкнута. Якщо повернути будь-яку плитку у другій cправа колонці, то лампа увімкнеться. Напишіть програму, яка знаходить мінімальну кількість плиток, що треба перевернути для того, щоб увімкнути лампу. Вхідні дані: Перший рядок містить два цілих числа N та M - розміри сітки. Далі слідують N рядків по M символів -\ або /, що характеризують направлення дроту на даній плитці. Вихідні дані: Єдиний рядок має містити відповідь на задачу, або ж повідомлення "NO SOLUTION", в тому випадку, коли увімкнути лампу неможливо. Обмеження: 1 ≤ N, M ≤ 500. 40 балів можна отримати, якщо Ваша програма працює при 1 ≤ N ≤ 4 та 1 ≤ M ≤ 5.
Приклад вхідних та вихідних даних.
Приклад вхідних даних: | Приклад вихідних даних: | 3 5 \\/\\ \\/// /\\\\
| 1
|
|