Question

Задача B. Делится? Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на 8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ. Формат входных данных В первой строке дано цело число n (1 ⩽ n ⩽ 103 ) - длинна числа. Во второй строка дана строка состоящая из цифр s - число которое надо проверить. Формат выходных данных Выведите YES если число делится на 8 по правилам ОМЫ иначе NO Примеры стандартный ввод стандартный вывод 2 23 YES 3 101 NO Замечание Перестановка числа х - это число, состоящее из тех же цифр, что и х, но в другом порядке. Например, числа, которые можно получить путем перестановки цифр числа 123: 132, 213, 231, 312, 321 В первом примере из числа 23 можно получить делящееся на 8 число 32, ответ YES. Во втором примере из числа 101 невозможно получить число делящееся на 8, ответ NO. Subtask 1: (n ⩽ 100) Subtask 2: (n ⩽ 1000)

Answer 1

Удачи, чел, на этой олимпиаде, все куплено. Я уже свалил оттуда

Answer 2

Для решения этой задачи, мы должны проверить, существует ли перестановка цифр в числе такая, что новое число без лидирующих нулей делится на 8.

Чтобы решить задачу, мы можем перебирать все возможные перестановки цифр данного числа и проверять каждую на делимость на 8. Если хотя бы одна перестановка делится на 8, то выводим "YES", в противном случае - "NO".

Если значение числа n не очень большое, мы можем использовать рекурсивную функцию для генерации всех перестановок и проверять их на делимость на 8. Если же n достаточно велико, то такой подход станет неэффективным, и нам понадобится другое решение.

Вот пример кода на Python для решения задачи:

pythonCopy code
def is_divisible_by_8(number):
    return int(number) % 8 == 0

def generate_permutations(digits, n, visited, current, result):
    if len(current) == n:
        result.append(int(''.join(current)))
        return

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            generate_permutations(digits, n, visited, current + [digits[i]], result)
            visited[i] = False

def check_divisibility(n, number_str):
    if n == 1:
        number = int(number_str)
        if is_divisible_by_8(number):
            return "YES"
        else:
            return "NO"

    digits = list(number_str)
    visited = [False] * n
    permutations = []
    generate_permutations(digits, n, visited, [], permutations)

    for perm in permutations:
        if is_divisible_by_8(perm):
            return "YES"
    
    return "NO"

# Чтение входных данных
n = int(input())
number_str = input().strip()

# Вывод результата
print(check_divisibility(n, number_str))

Выше представлены функции для проверки делимости числа на 8 и для генерации всех перестановок. Затем мы проверяем число n и в зависимости от его значения вызываем соответствующую функцию. Если n равно 1, то просто проверяем данное число на делимость на 8. В противном случае, генерируем все перестановки и проверяем каждую из них на делимость на 8.

Оценка времени работы данного решения зависит от значения числа n и может быть неэффективной для больших n. Если требуется решение с более высокой эффективностью для больших значений n, потребуется использовать другой подход, например, используя математические свойства делимости на 8.