Разбор задач «Квеста на миллион» / forpes.ru

Главная
Разбор задач «Квеста на миллион»

Разбор задач «Квеста на миллион»

08.04.2024 07:36

tguev 1 1100 Источник

Друзья, разбираем задачи прошедшего квеста на миллион. Для простоты в разборе будем использовать формализованные формулировки. Ознакомиться с исходными формулировками задач можно в самом квесте по ссылке.

Задача 1. От начала суток прошла $\dfrac15$ того времени, что осталось до конца суток. Который сейчас час?

Решение. Пусть от начала суток прошлочасов. Составим и решим уравнение:

$x = \dfrac15\cdot(24-x) \iff 5x = 24-x \iff 6x = 24 \iff x = 4$

Ответ: .

Задача 2. Нарисуйте фигуру в соответствии с условиями и вычислите ее площадь:

отступиклеток слева иклеток сверху
поставь точку в узле квадратной сетки
клетки по диагонали вверх и вправо
клетки вправо
клетки по диагонали вниз и вправо
клетки по диагонали вверх и вправо
клетки вправо
клетки по диагонали вниз и вправо
клетки вниз
клеток по диагонали вниз и влево
клеток по диагонали вверх и влево
клетки вверх

Решение. Указанным условиям соответствует следующая фигура:

Ее площадь равна .

Ответ: .

Задача 3. Загадалиразличных положительных целых числа A, B, C, D, при этом A < B < C < D. Необходимо написать программу, которая получает на вход числа A, B, C, D, A × B, B × C, C × D, D × A (на одной строке). Программа должна вывести одно число D.

Решение. Ключевым моментом в решении этой задачи является сортировка. Приведенный ниже код решает поставленную задачу:

a, b, c1, c2, _, _, _, cd = sorted(map(int, input().split()))
print(cd // c2 if a * b == c1 else cd // c1)

Задача 4. Необходимо написать программу, которая получает на вход два положительных целых числа А и В. Программа должна вывести разность между суммами всех четных и нечетных чисел от А до В включительно. Считайте, что числа A и B не превосходят $2\cdot 10^9$ .

Решение. Переборное решение не пройдет из-за больших значений чисел A и B. Используя суммы двух арифметических прогрессий, можно решить задачу за константное время . Приведенный ниже код решает поставленную задачу:

a = int(input())
b = int(input())

a2 = a + a % 2
b2 = b - b % 2
even = (b2 + a2) // 2 * ((b2 - a2) // 2 + 1)

a1 = a + (1 - a % 2)
b1 = b - (1 - b % 2)
odd = (b1 + a1) // 2 * ((b1 - a1) // 2 + 1)

print(even - odd)

Задача 5. Дан следующий набор данных, содержащий информацию о расстоянии между различными объектами в городе:

от дома Джонатана (Д) до офиса Гвидо (Г) — км
от Автомастерских (А) до офиса Гвидо (Г) — км
от офиса Гвидо (Г) до Башни интернет-вещания (Б) — км
от Автомастерских (А) до Башни интернет-вещания (Б) — км
от Вирусологического центра (В) до офиса Гвидо (Г) — км

Расстояние считается по дорогам, соединяющим городские объекты между собой (смотри картинку). На каком расстоянии от дома Джонатана находится Вирусологический центр?

Решение. Сложим расстояния от дома Джонатана (Д) до офиса Гвидо (Г) и от Вирусологического центра (В) до офиса Гвидо (Г): . Будет посчитана основная дорога и дважды ответвление от нее к офису Гвидо (Г).

К полученной сумме добавим расстояние от Автомастерских (А) до Башни интернет-вещания (Б): . Будут посчитаны все три ответвления (к офису Гвидо — дважды), основная дорога тоже будет посчитана, причем участок на ней между первым и третьим ответвлением — дважды.

Вычтем из полученного значения два оставшихся расстояния: от Автомастерских (А) до офиса Гвидо (Г) и от офиса Гвидо (Г) до Башни интернет-вещания (Б): . Теперь будет посчитана только основная дорога. Таким образом, расстояние от дома Джонатана до Вирусологического центра равно 19 км.

Ответ..

Задача 6. Продолжите последовательность и укажите в ответе значение под номером.

Решение. Указанные на картинке последовательности связаны с троичной системой счисления. Если заменить букву X на цифру , букву Y — на цифру , а букву Z — на цифру , то получится такая последовательность:

То есть в строке номерзаписано представление в троичной системе счисления числа , дополненного нулями до пяти цифр. Переведем числов троичную систему счисления. Получится число, поэтому ответом на вопрос задачи будет строка ZXYZY.

Ответ: ZXYZY.

Задача 7. В далеком году в одном из отделений банка сломался автомат выдачи талонов электронной очереди. Менеджер Джеймс стал выдавать талоны вручную, вводя номера на клавиатуре для последующей печати. На следующий день головной офис затребовал у Джеймса информацию о количестве клиентов банка за прошедший день, ведь автоматика не смогла сформировать отчет. Джеймс схватился за голову: список выданных талонов не сохранился! Однако компьютер зафиксировал количество нажатий каждой клавиши от до на клавиатуре. Он показал значения, которые ты видишь сейчас на экране терминала. Так сколько клиентов было в банке в тот злополучный день, если в начале рабочего дня выдача талонов началась с номера ?

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

Приведенный ниже код:

n = 10000
digits = dict.fromkeys(range(10), 0)

for num in range(1, n):
    for i in map(int, str(num)):
        digits[i] += 1
    if digits[0] == 1229 and digits[9] == 1237:
        print(digits)
        print(num)

выводит:

{0: 1229, 1: 2338, 2: 2240, 3: 2240, 4: 1438, 5: 1240, 6: 1240, 7: 1240, 8: 1239, 9: 1237}
4197

Ответ: .

Задача 8. Требуется нажать пять клавиш на клавиатуре так, чтобы набор символов, набранных на клавиатуре, совпадал с набором символов, которые были нажаты на сенсоре.

Решение. Если на клавиатуре нажать клавиши 74852, то на сенсоре будет отображен такой же набор: 48527.

Ответ: 74852 (цифры могут располагаться в любом порядке).

Задача 8. Требуется ускорить следующий код:

n = int(input())

result = 0
for i in range(n):
    for j in range(2*n):
        result += j + i

print(result)

Решение. Приведенный код имеет квадратичную сложность . Его несложно переписать так, чтобы он имел константную сложность :

n = int(input())

result = n**2 * (3 * n - 2)

print(result)

Задача 9. Необходимо написать программу, которая получает на вход одно целое неотрицательное число s. Программа должна вывести одно число — количество целых чисел от до $10^{12}$ с суммой цифр s.

Решение. Участники квеста решали эту задачу разными способами. Приведем три основных.

Динамическое программирование:

def count_numbers(s):
    dp = [[0 for _ in range(s + 1)] for _ in range(13)]
    dp[0][0] = 1
    for i in range(1, 13):
        for j in range(s + 1):
            for k in range(10):
                if j >= k:
                    dp[i][j] += dp[i - 1][j - k]
    return dp[12][s]

s = int(input())
print(count_numbers(s))

Рекурсия:

from functools import lru_cache


@lru_cache(maxsize=None)
def func(digit_sum: int, number_length: int):
    if number_length == 0:
        return 0
    if 0 <= digit_sum <= 9 and number_length == 1:
        return 1

    res = 0
    for d in range(10):
        if digit_sum - d >= 0:
            res += func(digit_sum - d, number_length - 1)

    return res


s = int(input())
print(func(s, 12))

Meet in the middle:

from collections import defaultdict

def get_sum(num):
    return sum(map(int, str(num)))


n = 10**6

s = int(input())
di = defaultdict(int)

for i in range(n):
    di[get_sum(i)] += 1

total = 0

for i in range(n):
    ss = get_sum(i)
    if s - ss >= 0:
        total += di[s - ss]

print(total)

Задача 10. Необходимо разгадать кроссворд и указать слово по вертикали.

Методика синтеза изображения или голоса, основанная на искусственном интеллекте. Видеоролики с использованием этой технологии легко найти на Youtube или Tiktok.
Четкая последовательность шагов, которая приводит к желаемому результату.
Метод машинного обучения, при котором компьютерная программа имитирует работу человеческого мозга.
Впишите пропущенное слово: "OpenAI разработала __ машинного обучения, которую все знают как ChatGPT".
Деятельность по интерпретации смысла текста на одном языке и созданию нового эквивалентного ему текста на другом языке.
Программа, которая выполняет автоматические заранее настроенные повторяющиеся задачи. Такие программы особенно популярны в Telegram.

Решение. Слово по вертикали — ПРОМПТ.

Ответ: ПРОМПТ.

Задача 11. Необходимо написать программу, которая получает на вход одно целое положительное число n. Программа должна вывести количество целых положительных чисел, не превосходящих n, которые не делятся ни на одно из чисел и .

Решение. Приведенный ниже код решает поставленную задачу за константное время:

n = int(input())

print(n - n//2 - n//3 - n//5 + n//6 + n//10 + n//15 - n//30)

Задача 12. В следующей картинке зашифрована задача. Требуется ее найти и решить.

Решение. На картинке зашифрован текст: ДЖОНАТОН НАПИШИТЕ В ОТВЕТЕ ПЕРВЫЕ ВОСЕМНАДЦАТЬ ЦИФР ЧИСЛА ПИ ПОСЛЕ ЗАПЯТОЙ. Для расшифровки используется кривая Пеано, о которой говорится в оригинальном условии задачи.

Ответ:.

Задача 13. Та самая магическая задача. Ее разбор был опубликован на прошлой неделе в отдельном посте на Хабре.

Задача 14. Требуется решить ребус.

Решение. В ребусе зашифровано слово ХЕШИРОВАНИЕ.

Ответ: ХЕШИРОВАНИЕ.

Задача 15. Необходимо собрать из чисел наибольшее простое число.

Решение. После правильного решения каждой из задач №1-14 давалось некоторое число. Список чисел выглядит так: 0, 9, 7, 3, 5, 3, 8, 3, 7, 97, 4, 2, 9, 61, 5. Наибольшее простое число, составленное из этих чисел — это .

Ответ:.

Победители квеста опубликованы в нашем телеграм-канале. ?

Комментарии (1)

Alexandroppolus
08.04.2024 08:21
#26699937
в задаче 11 использован "принцип включения-исключения"

Разбор задач «Квеста на миллион»

Комментарии (1)

Alexandroppolus