Начало
1119. Делимость
Делимость
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 18/10/2008 | Занятие 5 (B) |
| 07/10/2014 | Занятие 6 (D) |
| 20/07/2016 | Лето 2016 - 12 (B) |
| 08/07/2019 | Лето 2019 - 4 (B) |
| 06/07/2022 | Лето 2022-5 (C) |
| 23/02/2023 | Базовый уровень: динамическое программирование 1 (проводит BOGAT) (C) |
| 12/07/2023 | Лето 2023-8 простые (D) |
| 27/02/2024 | Динамическое программирование 1 (проводит BOGAT) (C) |
| 10/07/2024 | Лето 2024-8 простые (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим последовательность целых чисел. Расставляя знаки операции + и - между этими числами мы получим разные результаты. Напишите программу, которая проверяет, можно ли расставить знаки операции + и - таким образом, чтобы результат делился на заданное число K.
Ввод: в первой троке содержатся два целых числа N и K (1 ≤ N ≤ 10000, 2 ≤ K ≤ 100), разделенных пробелом. Во второй строке последовательность из N целых чисел, разделенных пробелом. Все целые не превосходят по абсолютному значению 10000.
Вывод: Напечатайте слово "Divisible", если результат можно сделать делящимся на K, и "Not divisible", если нельзя.
Пример ввода
4 7 17 5 -21 15
Пример вывода
Divisible
Существует 8 способов расставить знаки + и –
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
Во втором и четвёртом варианте результат делится на 7 без остатка.
Источник: NEERC ACM ICPC, 1999
