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

При включении нового результата в список лучших этот результат должен быть записан на соответствующее ему место, а более низкие результаты — сдвинуты на одну позицию вниз.

Ниже приводится пример правильной программы на алгоритмическом языке. В данной программе для каждой строки протокола просматривается полный текущий список лучших результатов. Допускается сокращение этого просмотра за счёт дополнительных проверок.

Пример правильной и эффективной программы на алгоритмическом языке

алг

нач

цел К, N

ввод К, N

целтаб суммы[1:К]

литтаб имена[1:К]

цел сум

лит имя

цел низ, верх, место

нц для место от 1 до К

суммы[место]:= 0

имена[место]:= ""

кц

нц N раз

ввод сум, имя

верх:= 0; низ:= К

нц для место от 1 до К

если сум>суммы[место] и верх=0 то верх:= место все

если имя=имена [место] то низ:= место все

кц

если 0<верх<= низ то

нц для место от низ до верх+1 шаг −1

суммы[место]:= суммы[место −1]

имена[место]:= имена[место −1]

кц

суммы[верх]:= сум

имена[верх]:= имя

все

кц

нц для место от 1 до К

если суммы[место]>0

то вывод не, место,".",имена[место],"(",суммы[место]

все

кц

кон

Основное подмножество состоит из всех значений сигналов, кроме 0, если он встречается, и кроме минимального нечётного значения, если таких значений чётное число.

Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен N. Во время чтения данных запоминается номер 0, если он встретится (по условию все значения различны, поэтому 0 встречается не больше одного раза), подсчитывается количество нечётных значений и ищется минимальное из них. После окончания ввода распечатываются все номера, кроме номера 0 и номера минимального нечётного значения, но только в случае, если их количество чётно.

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

var n,i,j,k,c,min,a: longint; 
begin 
 readln(n); 
 min := 1000000001; 
 k := 0; 
 j := 0; 
 c := 0; 
 for i := 1 to n do 
 begin 
 readln(a); 
 if a = 0 then j := i; 
 if a mod 2 <> 0 then 
 begin 
 c := c + 1; 
 if a < min then 
 begin 
 min := a; 
 k := i; 
 end 
 end 
 end; 
 for i :=1 to n do 
 if (i <> j) and ((c mod 2 <> 0) or (i <> k)) then 
 write(i,' '); 
end.

INPUT n 
 min = 0 
 k = 0 
 j = 0 
 c = 0 
 FOR i = 1 TO n 
 INPUT a 
 IF a = 0 THEN j = i 
 IF a MOD 2 <> 0 THEN 
 c = c + 1 
 IF (min = 0) OR (a < min) THEN 
 min = a 
 k = i 
 END IF 
 END IF 
 NEXT i 
 FOR i = 1 TO n 
 IF (i <> j) AND ((c MOD 2 <>0) OR (i <> k)) THEN 
 PRINT i 
 NEXT i 
 END

Пример решения задачи A на языке Паскаль.

var
  a: array[1..10000] of integer; {исходные данные}
  min: integer; {минимальное нечётное число}
  N: integer; {количество чисел}
  sum: integer; {максимальная сумма}
  i: integer;
begin
  readln(N);
  min := 1000000001;
  sum := 0;
  for i := 1 to N do readln(a[i]);
  for i := 1 to N do begin
    sum := sum + a[i];
    if (a[i] mod 2 <> 0) and (a[i]<min) then<p="">      min := a[i];
    end;
  if sum mod 2 = 0 then
    for i := 1 to N do
      if (a[i] <> min) and (a[i]<>0) then write(i, ' ');
  if sum mod 2 <> 0 then
    for i := 1 to N do
      if (a[i]<>0) then write(i, ' ');
end.

Программа читает все входные данные один раз, не запоминая их в массиве, размер которого равен N, а составляя только список встретившихся задач и количества запросов по каждой из них. Во время чтения данных об очередной задаче просматривается список ранее сохранённых задач; если она уже есть в списке, то количество запросов по ней увеличивается на 1, иначе задача добавляется в массив упомянутых в запросах задач (при корректных данных размер массива не может быть больше 12). После окончания ввода производится сортировка массивов задач и количества запросов, отданных за них, в порядке возрастания количества запросов; затем выводится список из трёх первых задач с указанием частоты встречаемости (или весь список, если его длина меньше трёх). Вместо сортировки можно применить и алгоритм поиска трёх минимальных элементов в массиве или три первых итерации сортировки. Затем выводятся три первые (или найденные наименее популярные) задачи. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программирования. Так, на языке C++ при считывании строковой переменной будет считано не всё название задачи, а только его первое слово, поэтому следует использовать функцию getline(cin,s); аналогичная проблема возникает и в языке Си

Var n, Num, i, j, t: integer;
 Count: array[1..12] of integer;
 s: string;
 Names: array[1..12] of string;
 Begin
 Num:=0; {Число различных задач в списке запросов} 
 ReadLn(N); {Считываем количество запросов}
 for i:=1 to N do
 begin 
 ReadLn(S); {считали очередную задачу}
 {Осуществляем её поиск в списке уже встретившихся}
 j:=1;
 while (j<=Num) and (s<>Names[j]) do j:=j+1;
 {Если она найдена}
 if j<=Num then {Увеличиваем счетчик числа запросов} 
 Count[j]:=Count[j]+1
 else begin {Иначе добавляем задачу в конец списка}
 Names[j]:=s;
 Count[j]:=1; 
 Num:=Num+1
 end
 end;
 {Сортируем массивы Names и Count в порядке возрастания значений массива Count}
 for i:=Num downto 2 do
 for j:=2 to i do if Count[j-1]>Count[j] then
 begin
 t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t;
 s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s;
 end;
 if Num >= 3 then Num := 3;
 for i:=1 to Num do
 WriteLn(Names[i], ' ', Count[i]);
 end.

DIM N, Num, i, j, t AS INTEGER
 DIM Count(12) AS INTEGER
 DIM Names$(12) 
 Num = 0 'Число различных задач в списке запросов
 INPUT N 'Считываем количество запросов
 FOR i = 1 TO N
 LINE INPUT s$ 'считали задачу
 'Осуществляем поиск задачи в списке уже встретившихся
 j = 1
 WHILE (j <= Num) AND (s$ <> Names$(j))
 j = j + 1 
 WEND
 'Если задача найдена
 IF j <= Num THEN 'Увеличиваем счетчик числа запросов 
 Count(j) = Count(j) + 1
 ELSE ' Иначе добавляем задачу в конец списка
 Names$(j) = s$
 Count(j) = 1 
 Num = Num + 1
 END IF 
 NEXT i
 'Сортируем массивы Names и Count в порядке возрастания значений
 'массива Count
 FOR i = Num TO 2 STEP -1
 FOR j = 2 TO i
 IF Count(j - 1) > Count(j) THEN
 t = Count(j): Count(j) = Count(j - 1): Count(j - 1) = t
 s$ = Names$(j): Names$(j) = Names$(j - 1): Names$(j - 1) = s$
 END IF
 NEXT j 
 NEXT i
 IF Num >= 3 THEN Num = 3
 FOR i = 1 TO Num
 PRINT Names$(i), Count(i) 
 NEXT i
 END

Произведение двух чисел делится на 29, если хотя бы один из сомножителей делится на 29.

При вводе чисел можно подсчитывать количество чисел, кратных 29, не считая четырёх последних. Обозначим их n29.

Примечание для проверяющего. Сами числа, кроме четырёх последних, при этом можно не хранить.

Очередное считанное число будем рассматривать как возможный правый элемент искомой пары. Если очередное считанное число делится на 29, то к ответу следует прибавить количество чисел до него, не считая четырёх последних (включая считанное). Если очередное считанное число на 29 не делится, то к ответу следует прибавить n29.

Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на четыре элемента ранее, достаточно хранить только четыре последних элемента или информацию о них. Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC).

Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.

const s = 4; {требуемое расстояние между элементами}
var
    n: longint;
    a: array[1..s] of longint; {хранение последних s значений}
    a_: longint; {очередное значение}
    n29: longint; {количество делящихся на 29 элементов, не считая s последних}
    cnt: longint; {количество искомых пар}
    i, j: longint;
begin
    readln(n); {Ввод первых s чисел}
    for i:=1 to s do
        readln(a[i]); {Ввод остальных значений, подсчет искомых пар}
    cnt := 0;
    n29 := 0;
    for i := s + 1 to n do
    begin
        if a[1] mod 29 = 0 then
            n29 := n29 + 1;
        readln(a_);
        if a_ mod 29 = 0 then
            cnt := cnt + i - s
        else
            cnt := cnt + n29;
{сдвигаем элементы вспомогательного массива влево}
        for j := 1 to s - 1 do
            a[j] := a[j + 1];
        a[s] := a_ {записываем текущий элемент в конец массива}
    end;
    writeln(cnt)
end.

Пример 2. Программа на языке Python. Программа эффективна по времени и памяти.

s = 4
a = [0]*s
n = int(input())
for i in range(s):
    a[i] = int(input())
cnt = 0
n29 = 0
for i in range(s, n):
    k = i % s
    if a[k] % 29 == 0:
        n29 = n29 + 1
    a_ = int(input())
    if a_ % 29 == 0:
        cnt = cnt + i - s + 1
    else:
        cnt = cnt + n29
    a[i % s] = a_
print(cnt)

Пример 3. Программа на языке С++. Программа эффективна по времени и памяти.

    #include 
    using namespace std;
    int main()
    {
        int s = 4; //требуемое расстояние между элементами
        int n;
        int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
        //хранение последних s счетчиков
        int a_; // очередное значение
        int cnt; // количество искомых пар
        cin >> n;
        cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> a_; // считано очередное значение
            if (i >= s)
            {
                if (a_ % 29 == 0)
                    cnt += i - s + 1;
                else
                    cnt += n4;
            }
            //сдвигаем элементы счетчиков
            n4 = n3;
            n3 = n2;
            n2 = n1;
            //обновляем счетчик кратных 29
            if (a_ % 29 == 0)
                n1 += 1;
        }
        cout << cnt;
        return 0;
    }

Пример 4. Программа на языке Паскаль. Программа эффективна по времени и неэффективна по памяти.

const s = 4; {требуемое расстояние между элементами}
var
    n: longint;
    a: array[1..1000] of longint;
    n29: longint;
    {количество делящихся на 29 элементов, не считая s последних}
    cnt: longint; {количество искомых пар}
    i, j: longint;
begin
    readln(n);
    {Ввод первых s чисел}
    for i:=1 to s do
        readln(a[i]);
    {Ввод остальных значений, подсчет искомых пар}
    cnt := 0;
    n29 := 0;
    for i := s + 1 to n do
    begin
        readln(a[i]);
        if a[i - s] mod 29 = 0 then
            n29 := n29 + 1;
        if a[i] mod 29 = 0 then
            cnt := cnt + i - s
        else
            cnt := cnt + n29;
    end;
    writeln(cnt)
end.

program C4_2;

uses crt;

type massiv=array[1..99] of integer;

var count:massiv;       //массив количества учеников,где индекс-номер школы

    sumball:massiv;     //массив суммы баллов

    ch:char;

    i,N,nomer,ball,max,nmax:integer;

Begin

for i:=1 to 99 do

    begin

         count[i]:=0;   //обнуляем массивы

         sumball[i]:=0;

    end;

write('Введите количество учеников: ');readln(n);

for i:=1 to n do

begin

Repeat

read(ch);

Until ch=' '; //фамилия считана

Repeat

read(ch);

Until ch=' ';//Имя

read(nomer);

read(ball);

count[nomer]:=count[nomer]+1;   //счетчик количества учеников данной школы

sumball[nomer]:=sumball[nomer]+ball; //сумма баллов

end;

for i:=1 to 99 do

if count[i]>0 then sumball[i]:=round(sumball[i] / count[i]); //вычисляется средний балл

// с точностью до целых

max:=1;

nmax:=1;

for i:=2 to 99 do

if sumball[i]>sumball[max] then       //поиск максимального среднего балла

   begin

   max:=i;

   nmax:=1;

   end

else if sumball[i]=sumball[max] then inc(nmax);

if nmax=1 then writeln(max,' ',sumball[max])

else writeln(nmax);

End.

Задание 1.

а) ≥14. При количестве камней в куче от 14 и больше Паше необходимо увеличить количество камней в пять раз, тем самым получив 70 или более камней.

б) 13. Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество камней в пять раз, получая 70, 85 или 325 камней в куче.

Задание 2.

9, 12. Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12 камней, и получить кучу из 13 камней. После чего игра сводится к стратегии, описанной в пункте 1б.

Задание 3.

8. Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша делает ход «увеличить в пять раз», тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.

Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2.

Данную стратегию можно представить в виде таблицы.

ИЛИ

11. Своим первым ходом Паша может сделать 12, 15 или 55 камней. Если количество камней в куче 15 или 55 Васе необходимо увеличить количество камней в 5 раз. Для случая 12 камней Вася использует стратегию, указанную в п.2. Представим стратегию в виде таблицы.

Программа читает текст до точки один раз, подсчитывая в массиве, хранящем 26 целых чисел, количество вхождений каждой из букв. Сам текст при этом не запоминается. Затем в этом массиве шлется первое вхождение максимального элемента. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, для строк, состоящих не более чем из 255 символов).

DIM i, imах, с, a(26) AS INTEGER
OPEN "TEXT.DAT" FOR INPUT AS #1
S$ = INPUT$(1,#1)
DO WHILE NOT (S$ = ".")
c = ASC(S$)
IF(c>=ASC("A")AND c<=ASC("Z")) THEN
с = с - ASC("A") + 1
ENDIF
IF(c>=ASC("a")AND c<=ASC("z")) THEN
с = с - ASC("a") + 1
ENDIF
IF(c >=1 AND c<=26) THEN a(c)=a(c)+l
S$ = INPUT$(1,#1)
LOOP
imax = 1
FOR i = 2 TO 26
IF a(i) > a(imax) THEN imax = i
NEXT i
PRINT CHR$(imax + 64), a(imax)
END

var a:array['A'..'Z'] of integer;
с, cmax: char;
begin
assign(input'text. dat');
reset(input);
for c:='A'to'Z' do a[c]:=0;
repeat
read(input, c);
c:=upcase(c);
if c in['A'...'Z']then
a[c]:=a[c]+l
until c='.';
cmax := 'A';
for c:='B'to'Z'do
if a[c] > a[cmax] then
cmax := c;
writeln(cmax,' ',a[cmax])
end.

type uchenik =record

Fam:string[20];

name:string[15];

b1,b2,b3:integer;

end;

var

srB:array [1..100] of real;

i,k,l,p,N,m1,m2,m3:integer;

max1,max2,max3,sr:real;

c:char;

a:array[1..100] of uchenik;

begin

read(n); //считали количество учеников

if n>=10 then begin

for I:=1 to n do

begin

a[i].fam:='';

repeat read(c);

a[i].fam:= a[i].fam+c;

until c=' '; //считали фамилию

repeat read(c);

a[i].name:= a[i].name+c;

until c=' '; //считали имя

read(m1); a[i].b1:=m1;

read(m2); a[i].b2:=m2;

read(m3); a[i].b3:=m3;

end; //считали балы

for i:= 1 to n do

srB[i]:= a[i].b1+a[i].b2+a[i].b3; //создали массив, содержащий средние балы

max1:=srB[1]; max2:=0;max3:=0;

for i:= 2 to n do begin //нашли три максимума

if srB[i]>max1 then begin max3:=max2; max2:=max1; max1:=srB[i]; k:=i; end

else if srB[i]>max2 then begin max3:=max2; max2:=srB[i]; l:=i; end

else if srB[i]>max3 then begin max3:=srB[i]; p:=i; end;

end;

for i:=1 to n do

if srB[i]>= max3 then writeln(a[i].fam, a[i].name);

end

else writeln('учеников не может быть меньше 10');

end.

Программа верно читает входные данные, сразу запоминая только время окончания хранения багажа в массиве, соответствующем ячейкам камеры хранения. Подходящая ячейка определяется путём последовательного просмотра элементов этого массива до первого свободного или такого, в котором записано время окончания хранения, не превосходящее текущего времени сдачи очередного багажа. В случае удачного выбора ячейки фамилия и номер ячейки распечатываются. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая. Время можно как переводить в минуты, так и хранить в виде строки, сравнивая затем строки непосредственно. В последнем случае упрощается ввод данных.

Пример правильной программы на языке Паскаль:

var p:array[1..1000] of integer;

c,c1:char;

i,j,N,K:integer;

name:string;

time1,time2:integer;

begin

readln(N,K);

for i:=1 to K do

p[i]:=0;

for i:=1 to N do

begin

name:='';

repeat

read(c);

name:=name+c

until c=' '; {считана фамилия}

read(c,c1); {считаны часы первого времени}

time1:=60*((ord(c)-ord('0'))*10+ ord(c1)-ord('0'));

read(c,c,c1); {пропущено двоеточие, и считаны минуты}

time1:=time1+(ord(c)-ord('0'))*10+ord(c1)-ord('0');

read(с,c,c1); {считаны часы второго времени}

time2:=60*((ord(c)-ord('0'))*10+ ord(c1)-ord('0'));

readln(c,c,c1); {пропущено двоеточие, и считаны минуты}

time2:=time2+(ord(c)-ord('0'))*10+ord(c1)-ord('0');

for j:=1 to K do

if p[j]<=time1 then

begin

p[j]:=time2;

writeln(name,' ',j);

break;

end;

end;

end.

Пример правильной программы на языке Бейсик:

DIM p(1000) AS INTEGER

DIM s AS STRING

DIM nm AS STRING

INPUT n

INPUT k

FOR i = 1 TO k

p(i) = 0

NEXT i

FOR j = 1 TO n

LINE INPUT s

c$ = MID$(s, 1, 1)

i = 1

WHILE NOT (c$ = " ")

i = i + 1

c$ = MID$(s, i, 1)

WEND

nm = MID$(s, 1, i)

time1 = (ASC(MID$(s, i + 1, 1)) - ASC("0")) * 60 * 10

time1 = time1 + (ASC(MID$(s, i + 2, 1)) - ASC("0")) * 60

time1 = time1 + (ASC(MID$(s, i + 4, 1)) - ASC("0")) * 10

time1 = time1 + (ASC(MID$(s, i + 5, 1)) - ASC("0"))

time2 = (ASC(MID$(s, i + 7, 1)) - ASC("0")) * 60 * 10

time2 = time2 + (ASC(MID$(s, i + 8, 1)) - ASC("0")) * 60

time2 = time2 + (ASC(MID$(s, i + 10, 1)) - ASC("0")) * 10

time2 = time2 + (ASC(MID$(s, i + 11, 1)) - ASC("0"))

FOR i = 1 TO k

IF time1 >= p(i) THEN

p(i) = time2

PRINT nm, i

GOTO 10

ENDIF

NEXT i

10 NEXT j

END

Наименьшая возможная сумма цифр числа в заданном диапазоне равна 0, наибольшая — 27. Необходимо создать массив с индексами от 0 до 27 и использовать его для подсчёта встречающихся сумм. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение минимального элемента этого массива и вывести его индекс. Ниже приведены реализующие описанный выше алгоритм программы на языке Паскаль (использована система программирования PascalABC) и языке Java (версия языка 5.0 или выше). Программы отличаются способом вычисления суммы цифр очередного числа: в программе на Паскале использован обычный цикл разложения числа на цифры десятичной записи, в программе на Java сумма вычисляется по формуле, учитывающей, что число содержит не более трёх цифр. Оба способа допустимы

Далее последует пример кода, который работает за линейное время.

Язык — PascalABC.

var     
  N: integer;     {количество чисел}     
  a: integer;     {очередное число}     
  s: integer;     {сумма цифр числа}    
  k: array [0..27] of integer; {подсчёт сумм}    
  mn: integer;    {минимум в массиве k}    
  imn: integer;   {самая редкая сумма}   
  i: integer; 
begin     
  for i:=0 to 27 do k[i]:=0;     
  readln(N);    
  for i:=1 to N do begin        
    readln(a);       
    s := 0;         
    while a>0 do begin    
          s := s + a mod 10;
          a := a div 10;
    end;         
    k[s] := k[s]+1;     
  end;     
  mn := N+1;     
  for i:=0 to 27 do begin        
     if (k[i]>0) and (k[i]<=mn) then begin       
         mn := k[i];           
         imn := i;        
     end;   
  end;        
  write(imn); 
end.

import java.util.Scanner;
 
public class P27B {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int k[] = new int[28];
		for (int i = 0; i < N; ++i) {
			int a = in.nextInt();
			int s = a / 100 + a / 10 % 10 + a % 10;
			++k[s];
		}
		int mn = N + 1;
		int imn = 0;
		for (int i = 0; i < k.length; ++i) {
			if (k[i] > 0 && k[i] <= mn) {
				mn = k[i];
				imn = i;
			}
		}
		System.out.print(imn);
	}
}
 

Пример правильной, но неэффективной программы на языке Паскаль.

var 
  N: integer; {количество чисел}
  val: integer; {самая редкая сумма}
  a: array [1..10000] of integer;
  max_lenght: integer;
  i, j, k, lenght: integer;
begin
  readln(N);
  for i:=1 to N do read(a[i]);
  for i:=1 to N do a[i] := a[i] mod 10 + a[i] div 10 mod 10 + a[i] div 100 mod 10;
  for i:=1 to N-1 do
    for j:=1 to N-i do
      if a[j] < a[j+1] then begin
        k := a[j];
        a[j] := a[j+1];
       a[j+1] := k;
     end;
  max_lenght := N+1;
  lenght := 0;
  val := a[1];
  for i := 1 to N do 
    if a[i]=a[i+1] then
     lenght := lenght + 1
    else begin
    if lenght<max_lenght then="" begin<p="">      max_lenght := lenght;
      val := a[i];
    end;
    lenght := 0;
    end;
  writeln(val);
end.