На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Rust
  
> ЕГЭ по информатике 2020, часть 2, № 27, программирование
    ЕГЭ по информатике 2020, вариант Москва
    Часть 2, № 27
    Программирование
    Задание взято с сайта
    http://kotolis.ru/realegeinf_2020
    (программу, приведённую на сайте, не проверяла)

    user posted image

    Условие.
    На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности, у которых различные остатки от деления на d=160 и хотя бы одно из чисел делится на р=7. Среди таких пар, необходимо найти и вывести пару с максимальной суммой элементов.
    Описание входных и выходных данных.
    В первой строке входных данных задаётся количество чисел N
    (1<= N <= 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000. В качестве результата программа должна напечатать элементы искомой пары. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Если таких пар нет, то вывести два нуля.
    Пример входных данных:
    4
    168
    7
    320
    328
    Пример выходных данных для приведённого выше примера входных данных:
    168 320
    Пояснение: Из 4 чисел можно составить 6 пар. В данном случае условиям удовлетворяют пары: 168 и 320, 168 и 7, 320 и 7, 328 и 7. Максимальную сумму дает пара 168 и 320.
    Программа считается эффективной по времени, если при увеличении количества исходных чисел N в к раз время работы программы увеличивается не более чем в к раз. При увеличении d в к раз время работы программы должно не увеличиваться.
    Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
    Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
    Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
    Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности. — 2 балла.
    Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.

    Решение.
    Нужно найти пару (a, b) с максимальной суммой.
    Числа a и b должны удовлетворять следующим условиям:
    1) быть разные: a <> b;
    2) остатки от деления на 160 у этих чисел тоже должны быть разные:
    a mod 160 <> b mod 160;
    3) хотя бы одно из чисел должно быть кратно 7:
    (a mod 7 = 0) or (b mod 7 = 0).

    Во время чтения элементов последовательности находим значение четырёх переменных: max1, max2, k1, k2.
    Инициализация: max1:= 0; max2:= 0; k1:= 0; k2:= 0.
    max1 – самое большое число в последовательности,
    max2 – второе по величине при условии, что остатки от деления на 160 у них разные: max1 mod 160 <> max2 mod 160.
    κ1 – самое большое число в последовательности, кратное 7,
    k2 – второе по величине кратное 7 при условии, что остатки от деления на 160 у них разные: k1 mod 160 <> k2 mod 160.

    После того, как чтение элементов закончиться, делаем следующие проверки.
    Если max2=0 (у всех элементов остатки деления на 160 одинаковы ), то печать 0 0
    Иначе если max1 или max2 кратно 7, то печать max1 max2
    Иначе если k1 = 0 (нет элементов, кратных 7), то печать 0 0
    Иначе если k2 =0 (у всех элементов, кратных 7, остатки от деления на 160 одинаковы), то
    begin
    если у max1 и k1 остатки от деления на 160 разные, то печать max1 k1
    иначе печать max2 k1
    end
    Иначе если у max1 и k1 остатки от деления на 160 разные, то печать max1 k1
    Иначе если max1+k2 > max2+k1, то печать max1 k2
    Иначе печать max2 k1.

    Программа на Паскале

    ExpandedWrap disabled
      const N= 4;
      var a,i,max1,max2,k1,k2,ost160: integer;
      begin
        max1:= 0; max2:= 0; k1:= 0; k2:= 0;
        for i:= 1 to N do begin
           readln(a);    
           ost160:= a mod 160;
           if max1 = 0 then max1:= a    
           else if a > max1 then
             begin
                if ost160 <> (max1 mod 160) then
                  begin
                     max2:= max1;
                     max1:= a
                 end
              else max1:= a
            end //a > max1
           else if a > max2 then
             begin if ost160 <> (max1 mod 160) then max2:= a end;
          
           if a mod 7 = 0 then begin
            if k1 = 0 then k1:= a
            else if a > k1 then
              begin
                if ost160 <>(k1 mod 160) then
                  begin k2:= k1; k1:= a end
                else k1:= a
              end // a > k1
           else if a > k2 then  
             begin if ost160 <> (k1 mod 160) then k2:= a end
           end; //a mod 7 = 0
        end;//for
       
        if max2=0 then writeln('0 0')
        else if (max1 mod 7 = 0)or(max2 mod 7 = 0) then writeln(max1, ' ', max2)
        else if k1=0 then writeln('0 0')
        else if k2=0 then
          begin
            if (max1 mod 160)<>(k1 mod 160) then writeln(max1, ' ', k1)
            else writeln(max2, ' ', k1)
          end
        else if (max1 mod 160)<>(k1 mod 160) then writeln(max1, ' ', k1)
        else if max1+k2 > max2+k1 then writeln(max1, ' ', k2)
        else writeln(max2, ' ', k1);
        readln;
      end.
    Сообщение отредактировано: swf -
    1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
    0 пользователей:


    Рейтинг@Mail.ru
    [ Script execution time: 0,0160 ]   [ 14 queries used ]   [ Generated: 25.07.21, 04:09 GMT ]