Задача ЕГЭ №27

8 Август 2019 - Время чтения: 23 минуты

Условие задачи: По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел может быть очень велико. Затем передаётся контрольное число R - наибольшее число, удовлетворяющее следующим условиям:

  1. R - произведение различных элементов последовательности. "Различных" означает, что мы не рассматриваем квадрат числа, но можем перемножить два одинаковых по значению члена последовательности.
  2. R делится на 10.
  3. Если такого числа нет, R полагается равным 0.

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

Решение: Как это часто бывает, задача не представляет никакой сложности с точки зрения программирования, главное - понять логику происходящего в ней и выразить её математически. Произведение двух чисел делится на 10 в двух случаях:

  1. Хотя бы одно из чисел делится на 10.
  2. Одно делится на 5, а другое - на 2.

Заметим, что делимость на 10 означает, что число делится одновременно и на 5, и на 2. Получается, что всё множество чисел удобно разделить на четыре квадранта: по признаку делимости на 2 - пополам, и по признаку делимости на 5 - ещё пополам. Числа, делящиеся на 5, идут направо, не делящиеся - налево. Делящиеся на 2 - вниз, не делящиеся - вверх. Например, число 100 делится и на 5, и на 2, значит идёт в нижнюю правую четверть.

Число py = p % 5 == 0
y = 0y = 1
x = p % 2 == 0x = 0p = 11p = 15
x = 1p = 16p = 100

Очень удобно представить все максимумы в виде двумерного массива 2x2. При этом нужно учесть два момента. Во-первых, нам не интересен максимум левой верхней четверти, т.е. самое большое число, не делящееся ни на 5, ни на 2. Число, кратное 10, получится при умножении любого числа на 10, поэтому нам нужен просто максимум, из всех чисел. Но можно его хранить в "лишней" ячейке массива - не пропадать же памяти зря. А во-вторых, мы не должны сразу обновлять общий максимум числом, делящимся на 10. Мы должны сделать это только когда встретится следующее такое число, чтобы не получилось так, что мы умножили один и тот же элемент последовательности на себя самого.


Программа на языке C99
#include <stdio.h>
#include <string.h>
 
int max(const int a, const int b)
{
    return a > b ? a : b;
}
 
int main(void)
{
    int m[2][2];
    memset(m, 0, sizeof(int) * 4);
    int n;
    scanf("%d", &n);
    int p;
    while (n-- > 0) {
        scanf("%d", &p);
        int x = p % 2 == 0;
        int y = p % 5 == 0;
        if (x && y) {
            m[0][0] = max(m[0][0], m[1][1]);
        }
        m[x][y] = max(m[x][y], p);
        m[0][0] = max(m[0][0], max(m[0][1], m[1][0]));
    }
    scanf("%d", &p);
    int r = max(m[0][0] * m[1][1], m[0][1] * m[1][0]);
    printf("%d\n%s\n", r, r == p ? "PASS" : "FAIL");
    return 0;
}

Программа на языке Python
m = [[0, 0], [0, 0]]
for _ in range(int(input())):
    p = int(input())
    x = p % 2 == 0
    y = p % 5 == 0
    if x and y:
        m[0][0] = max(m[0][0], m[1][1])
    m[x][y] = max(m[x][y], p)
    m[0][0] = max(m[0][0], m[0][1], m[1][0])
p = int(input())
r = max(m[0][0] * m[1][1], m[0][1] * m[1][0])
print(r, "PASS" if r == p else "FAIL", sep="\n")

Не вижу смысла писать на других языках - получится абсолютно то же самое, уверяю вас. Но если надо, особенно на каких-нибудь экзотических языках - пишите в комментариях, будем разбираться!

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории