Ліміт часу: 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’.
Вхідні дані:Отже, два слова 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 градусів у обох напрямках.
Джерело живлення під’єднано до лівого верхнього кута сітки, лампа - до правого нижнього. Для того щоб увімкнути лампу можна повернути будь-яку плитку на 90 градусів у обох напрямках.
На зображені лампа вимкнута. Якщо повернути будь-яку плитку у другій cправа колонці, то лампа увімкнеться.
Напишіть програму, яка знаходить мінімальну кількість плиток, що треба перевернути для того, щоб увімкнути лампу.
Вхідні дані:
Перший рядок містить два цілих числа N та M - розміри сітки. Далі слідують N рядків по M символів -\ або /, що характеризують направлення дроту на даній плитці.
Вихідні дані:
Єдиний рядок має містити відповідь на задачу, або ж повідомлення "NO SOLUTION", в тому випадку, коли увімкнути лампу неможливо.
Обмеження: 1 ≤ N, M ≤ 500. 40 балів можна отримати, якщо Ваша програма працює при 1 ≤ N ≤ 4 та 1 ≤ M ≤ 5.
Напишіть програму, яка знаходить мінімальну кількість плиток, що треба перевернути для того, щоб увімкнути лампу.
Вхідні дані:
Перший рядок містить два цілих числа N та M - розміри сітки. Далі слідують N рядків по M символів -\ або /, що характеризують направлення дроту на даній плитці.
Вихідні дані:
Єдиний рядок має містити відповідь на задачу, або ж повідомлення "NO SOLUTION", в тому випадку, коли увімкнути лампу неможливо.
Обмеження: 1 ≤ N, M ≤ 500. 40 балів можна отримати, якщо Ваша програма працює при 1 ≤ N ≤ 4 та 1 ≤ M ≤ 5.
Приклад вхідних та вихідних даних.
| Приклад вхідних даних: | Приклад вихідних даних: |
| 3 5 \\/\\ \\/// /\\\\ | 1 |
