1

Случайно нашел задачу, попытался решить, в итоге я получил ответ, но есть вопросы. Хочу провести работу над ошибками, уверен можно сделать решение граммотнее.

Снизу задание, источник: https://otvet.mail.ru/question/218944763

По каналу связи передаются данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух, признаком конца данных считается число 0. Нужно найти контрольное значение. Оно равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1. Использование массивов в данной задаче запрещено. Входные данные В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных). Выходные данные Программа должна вывести одно число - контрольное значение. Примеры Ввод 1 10 14 0 Вывод 140 Ввод 2 7 75 80 6 75 0 Вывод 560

Вот что у меня получилось, как по мне можно сделать лучше.

import numpy as np
sof = []
sof = str(input())
sof = sof.split(' ')
result = [int(item) for item in sof]
d = []
for item in result:
    for i in range(len(result)):
        z = item * result[i] 
        if (z % 7 == 0 and z % 49 != 0):
            d.append(z)
print(np.max(d))

Меня интересует можно ли в input приплести лямбда функцию? Или условную конструкцию, что-бы ввод кончался на 0. Вообщем хочу посмотреть как может решить эту задачу опытный пользователь.

1 ответ 1

2

Я так понимаю, что эта задача из ЕГЭ. Существует линейный алгоритм решения, суть в том, что получившееся максимальное произведение состоит из двух чисел.

Какими могут быть эти числа? Пусть это будет x и y. Тогда ни одно из них не может делиться на 49, то есть если мы встречаем число, делящееся на 49, то просто пропускаем его. Также не может быть так, что оба числа делятся на 7.

Тогда возможные варианты x и y(сразу учитывая, что ни одно из них не делится на 49): x % 7 == 0, y % 7 != 0 x % 7 != 0, y % 7 != 0

Тогда нужно хранить два максимума из чисел, не делящихся на 7, а также максимум из чисел, делящихся на семь.

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

Несмотря на язык, алгоритм должен быть ясен.

int mod7_0 = -1;
int mod1_0 = -1;
int x;
int answer = 1;
while (cin >> x)
{
   if (x == 0)
      break;
   if (x % 49 == 0)
      continue;
   else if (x % 7 == 0)
      mod7_0 = max(mod7_0, x);
   else
   {
      answer = max(answer, x * mod1_0);
      mod1_0 = max(x, mod1_0);
   }
}
answer = max(answer, mod1_0 * mod7_0);

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.