Задачи из ЕГЭ

Здесь представлен разбор задач из вариантов ЕГЭ - часть С4 с подробными рассуждениями и несколькими вариантами решения. 

Эти задачи также можно использовать на олимпиадах школьного уровня.
Все задачи из этого раздела используют либо работу со строками, либо с записями, либо с массивами. Кроме этого нужно оптимизировать программу. Что под этим понимается? Во-первых, использование минимально возможного объема памяти и времени выполнения программы (т.е. нужно использовать как можно меньше вложенных циклов, быстрые алгоритмы сортировки и поиска, алгоритмы, которые за один проход считывают и решают задачу).

Задания пробного ЕГЭ 2015:
Вариант 3 
Вариант 2

Задания ЕГЭ 2013.

Задача 1. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям:
1)R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2)R делится на 22.
Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: …
Контроль пройден (или – Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
55
997
22
7
9
400
22000

Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 22000
Контроль пройден

Решение:
Вариант 1 (почти правильно)
Число может делиться на 11 и 2, или на 22. Будем искать из введенных чисел максимальное, которое делится на 2, на 11 или на 22. Затем определим максимальное произведение, учитывая, что максимальных может и не быть (в этом случае произведение =0).

var
N,i:integer;
R,a,prmax,pr12,pr13,pr23,max1,max2,max3:longint;

begin
readln(n);
max1:=0;{максимальное число, которое делится на 2}
max2:=0;{максимальное число, которое делится на 11}
max3:=0;{максимальное число, которое делится на 22}

for i:=1 to n do begin
readln(a);
if (a mod 22=0)and(a>max3) then max3:=a
else
  if (a mod 11=0)and(a>max2) then max2:=a
  else
    if (a mod 2=0)and(a>max1) then max1:=a;
end;
pr12:=max1*max2;
pr13:=max1*max3;
pr23:=max2*max3;
{ищем максимальное произведение}
prmax:=pr12;
if (pr13>prmax) then prmax:=pr13;
if (pr23>prmax) then prmax:=pr23;

readln(r);
writeln('Вычисленное контрольное значение: ',prmax);
if (prmax<>0) and (r=prmax) and (r mod 10=0) then
write('Контроль пройден')
else write('Контроль не пройден');
readln;
end.                            

Вариант 2 Программа ученика (не оптимизировано)
var
N,i,j:integer;
R:0..1000;
a:array[1..100000] of 0..1000;
b:boolean;
begin
readln(N);
for i:=1 to N do readln(a[i]);
readln(R);
if R mod 22=0 then
  for i:=1 to N-1 do begin
    for j:=i+1 to N do
      if a[i]*a[j]=R then begin
        b:=true;
        break;
       end;
    if b then break;
  end;
if b=false then R:=0;
writeln('Вычисленное контрольное значение: ',R);
if b then write('Контроль пройден')
else write('Контроль не пройден')
end.

Вариант 3. Правильная программа (из inf.reshuege.ru)

Про­из­ве­де­ние двух чисел де­лит­ся на 22, если:
- один из со­мно­жи­те­лей де­лит­ся на 22 (вто­рой может быть любым) либо
- ни один из со­мно­жи­те­лей не де­лит­ся на 22, причём один из со­мно­жи­те­лей де­лит­ся на 2, а дру­гой — на 11.

По­это­му про­грам­ма, вы­чис­ля­ю­щая ко­до­вое число, может ра­бо­тать так. Про­грам­ма чи­та­ет все вход­ные дан­ные один раз, не за­по­ми­ная все дан­ные в мас­си­ве. Про­грам­ма для про­чи­тан­но­го фраг­мен­та вход­ной по­сле­до­ва­тель­но­сти хра­нит зна­че­ния четырёх ве­ли­чин: М2 — самое боль­шое чётное число, не крат­ное 11; M11 — самое боль­шое число, крат­ное 11, но не крат­ное 2; М22 — самое боль­шое число, крат­ное 22; МАХ — самое боль­шое число среди всех эле­мен­тов по­сле­до­ва­тель­но­сти, от­лич­ное от М22 (если число М22 встре­ти­лось более од­но­го раза и оно же яв­ля­ет­ся мак­си­маль­ным, то МАХ = М22). После того как все дан­ные про­чи­та­ны, ис­ко­мое кон­троль­ное зна­че­ние вы­чис­ля­ет­ся как мак­си­мум из про­из­ве­де­ний М22*МАХ и М2*М11.
var М2,M11,М22,R,MAX,dat,res,i,N: longint;
begin
М2 := 0;
Mil := 0;
М22 := 0;
MAX := 0;
readln(N);
for i := 1 to N do
begin
readln(dat);
if ((dat mod 2) = 0) and ((dat mod 11) > 0)and (dat > M2) then
M2 :=dat;
if ((dat mod 11) = 0) and ((dat mod 2) > 0) and (dat > Mil) then
Mil :=dat;
if (dat mod 22 = 0) and (dat > M22) then
begin
if M22 > MAX then MAX := M22;
M22 :=dat
end
else
if dat >MAX then
MAX := dat;
end;
readln(R);
if (M2*M11< M22*MAX) then
res := M22*MAX
else
res := M2 *M11;
writeln('Вы­чис­лен­ное кон­троль­ное зна­че­ние: 1,res);
if R = res then writeln('Кон­троль прой­ден') else writeln('Кон­троль не прой­ден');
end.


Задача 2. На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы – это целое неотрицательное число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны.
При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это непустое подмножество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), такое, что сумма значений скоростей у него чётна и максимальна среди всех возможных непустых подмножеств с чётной суммой. Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.

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

На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 10^9. Все N чисел различны.
Пример входных данных:
5
123
2
1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных:
2 3 5

Решение: 

Вариант 1. (почти правильно)
Нужно вывести все номера по порядку возрастания для всех чисел, не равных 0, сумма которых четна и максимальна. Нужно ли считать сумму? Скорее всего нет, так как сумма всех четных или двух нечетных равна четному числу. Если появился еще один нечетный (третий или первый), то его номер не записываем до тех пор пока не найдем ему пару. Если все-таки пары не нашлось и он один, то его не записываем. Если их несколько, то находим минимальный из них и его номер не записываем.
Вопрос: если мы найдем это минимальное нечетное число, которое будет лишним (т.е. первым или третьим лишним), как его номер потом выкинуть из последовательности номеров (индексов)?
Т.е. вывести сразу все индексы не получится. Но при вводе чисел можно сразу найти номер минимального нечетного числа (учитывая, что первоначальное значение такой переменной должно быть максимальным из заданного диапазона или присвоено первому нечетному числу, что проблематично) и их количество.
Если использовать массив, то мы заранее не знаем сколько таких номеров будет и придется выделять память под массивы динамически или использовать очередь (в очереди первый номер будет минимальным, а дальше все номера выстраиваются по возрастанию, при этом номер минимального нечетного можно выбросить, если количество нечетных чисел нечетно, и не выводить).

Пример программы с очередью:
type
prq=^q;
q=record
i:longint;
next:prq;
end;

var
N,i,k,a,min,imin:longint;
topB,B:prq;
procedure push(i:longint; var top, a:prq);
begin
   if a<>nil then
      begin
         new(a^.next);
         a:=a^.next;
         a^.i:=i;
         a^.next:=nil;
      end
   else begin
     new(a);
     a^.i:=i;
     a^.next:=nil;
     top:=a;
   end;
end;
function pop(var top:prq):integer;
begin
   if top<>nil then begin
      pop:=top^.i;
      top:=top^.next;
   end;
end;

begin
b:=nil;{очередь из номеров чисел}
readln(n);
min:=1000000001; {минимальное нечетное}
imin:=0;  {его индекс}
k:=0; {количество нечетных чисел}
for i:=1 to n do
begin
  readln(a);
  if odd(a) then begin {если число нечетное}
     k:=k+1;          {считаем количество}
     push(i,topb,b);  {и добавляем в конец очереди}
     if a<min then begin imin:=i;min:=a; end; {находим минимальное и запоминаем индекс}
  end else
  if a<>0 then push(i,topb,b); {если не ноль, то добавляем в конец очередь}
end;
if (k mod 2>0) then begin {если k нечетно, то при выводе убираем номер минимального нечетного из списка}
   while (topb<>nil) do begin
     i:=pop(topb);
     if i=imin then continue;
     write(i,' ');
   end;
end else
   while (topb<>nil) do write(pop(topb),' ');
readln;
end.

Пример с динамическим массивом:
var
N,i,k,m,a,min,imin:longint;
B:array of longint; {динамический массив}
begin
readln(n);
setlength(b,n);
min:=1000000001; {минимальное нечетное}
imin:=0;  {его индекс}
k:=0; {количество нечетных чисел}
m:=0; {количество всех индексов по возрастанию}
for i:=1 to n do
begin
  readln(a);
  if odd(a) then begin {если число нечетное}
     k:=k+1;          {считаем количество}
     b[m]:=i;inc(m);  {и добавляем в массив}
     if a<min then begin imin:=i;min:=a; end; {находим минимальное и запоминаем индекс}
  end else
  if a<>0 then begin
     b[m]:=i;inc(m); {если не ноль, то добавляем в массив}
  end;
end;
if (k mod 2>0) then begin {если k нечетно, то при выводе убираем номер минимального нечетного из списка}
  for i:=0 to m-1 do begin
     if b[i]=imin then continue;
     write(b[i],' ');
   end;
end else
  for i:=0 to m-1 do write(b[i],' ');
readln;
end.      

Вариант 2. Пример программы ученика.
type
  sumType = array[1..2] of longint;
  amount = 1..100000;

var
  N,i,j:integer;
  sKey,R:amount;
  a:array[amount] of 0..1000000000;
  sumObj:sumType;
  sum:array[amount] of sumType;
  sequenceObj:string;
  sequence:array[amount] of string;

procedure setSums(i:integer;sumObj:sumType;seq:string);
var
  j:integer;
  tempSumObj:sumType;
begin
  tempSumObj:=sumObj;
  inc(tempSumObj[1],a[i]);
  inc(tempSumObj[2]);
  inc(sKey);
  sum[sKey]:=tempSumObj;
  seq:=Concat(seq,' '+i);
  sequence[sKey]:=seq;
  for j:=i+1 to N do begin
    if j=N then begin
      inc(sKey);
      inc(tempSumObj[1],a[j]);
      inc(tempSumObj[2]);
      sum[sKey]:=tempSumObj;
      sequence[sKey]:=Concat(seq,' '+j);
    end else
      setSums(j,tempSumObj,seq);
  end;
end;

begin
readln(N);
for i:=1 to N do readln(a[i]);
for i:=1 to N do begin
  sumObj[1]:=0;
  sumObj[2]:=0;
  setSums(i,sumObj,'');
end;
for i:=1 to sKey do
  for j:=sKey downto i+1 do
    if(sum[j-1][1]<sum[j][1]) then begin
      sumObj:=sum[j-1];
      sum[j-1]:=sum[j];
      sum[j]:=sumObj;
      sequenceObj:=sequence[j-1];
      sequence[j-1]:=sequence[j];
      sequence[j]:=sequenceObj;
    end;
R:=1;
while sum[R][1] mod 2<>0 do inc(R);
i:=R+1;
while sum[i-1][1]=sum[i][1] do begin
  if sum[R][2]>sum[i][2] then R:=i;
  inc(i);
end;
write(Copy(sequence[R],2,Length(sequence[R])));
end.

Вариант 3. Правильный вариант (из inf.reshuege.ru)

Ос­нов­ное под­мно­же­ство со­сто­ит из всех зна­че­ний сиг­на­лов, кроме 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.

Демоверсия КЕГЭ 2012.
Будем называть разделителем символ '.' (точка) или ' '(пробел).
Будем называть словом любую непустую последовательность идущих подряд
букв и  (или)  цифр,  не содержащую разделителей,  и ограниченную слева
началом строки или разделителем, а справа — разделителем.
Например, строка
AsdF 10 AS42   AS        77qqq.
содержит 5 слов: AsdF, 10, AS42, AS, 77qqq
Будем называть подходящим словом слово,  являющееся записью целого
числа в системе счисления с основанием 5.
Например, слова
10, 44444, 0013, 0 – подходящие, а слова
 46, two, один,  33а, 3z4z не являются подходящими.
Составьте программу, которая вводит строку символов длиной не менее 2 и
не более 32, заканчивающуюся символом '.'  (точка),  а затем выводит на
экран для всех подходящих слов входной строки,   сумму соответствующих
чисел. Значение суммы должно выводиться в десятичной системе счисления. 
Например, для входной строки
100 у3 AS42   AS   22  77w.
программа должна вывести 37.
Ничего, кроме суммы чисел, программа выводить не должна.

Решение с рассуждениями:
Из текста задачи можно определить, что решение состоит из следующих этапов:
1. считать строку
2. выделить слова
3. проверить, что слово - число в пятеричной системе
4. прибавить число к итоговой сумме
5. перевести итоговую сумму в десятичное число.
Но нам нужен оптимизированный вариант решения задачи. Давайте ответим на несколько вопросов. Как и где храниить данные? У нас строка длинной не более 32 и заканчивается точкой. Значит можно использовать тип строка. Но, как быть при выделении слов? Использовать последовательно вызов процедур и функций для работы сос троками:
 i:=i+1; p:=pos(' ',s), a[i]:=copy(s,1,p-1); delete(s,1,p);
Может быть считывать по-символьно и сразу обрабатывать и проверять? И стоит ли хранить в массиве все слова сразу? Ведь нужны только те, которые представимы как числа в пятеричной системе. Кроме этого нам нужна только сумма этих чисел, причем в десятичной системе. Так не лучше ли сразу перевести число в десятичную систему и накапливать сумму?
Итак, путем логической цепочки рассуждений пришли к следующему алгоритму:
обнуляем сумму и строку для слова;
пока нет конца строки
повторяем:
  считываем каждый символ и проверяем на разделитель (точка, пробел, перевод строки - код 10 и 13);
  если это разделитель,
         то
              если строка не пустая,
                     то  обрабатываем строку
                           если это возможно, то переводим в десятичное число, 
                           прибавляем число к сумме,
              обнуляем строку;
         иначе
             добавляем в строку.             
Теперь вспомним как перевести число из пятеричной системы в десятичную. Используем формулу перевода в виде многочлена, не забывая перевсти символ в число, например так: ord(a[i])-ord('0')). При этом нам нужно знать, сколько разрядов в чисде, т.е. длина строки A. Для перемножения на степени пятерки нам не нужна функция возведения в степень. Можно обойтись временной переменной Y (равную сначала 1), которую каждый раз будем умножать на 5. В этом случае числа нужно перебирать с конца, т.е. с нулевого разряда.
p:=0;y:=1;
for i:=length(a) downto do begin
p:=p+y*(ord(a[i])-ord('0'));
y:=y*5;
end;
Получим следующий код программы:
var c:char;s:string;
    code,sum,p,y,i:integer;
begin
  s:='';sum:=0;p:=0;
  while not eof() do begin
    read(c);
    if c in [' ','.',#10,#13] then begin
      if s<>'' then begin
        val(s,p,code);
        if code=0 then begin
          p:=0;y:=1;

          for i:=length(s) downto 1 do begin
             p:=p+y*(ord(s[i])-ord('0'));
             y:=y*5;
          end;
          sum:=sum+p;
        end;
      end;
      s:='';
      end
      else s:=s+c;
   end;
 write(sum);
end.
 
Есть другой способ получения числа по схеме Горнера - это итеративная формула получения значения многочлена степени n):
a[n]*x^n+...+a[1]*x+a[0]=((...((a[n]*x+a[n-1])*x+a[n-2])*x+...+a[1])*x+a[0],
где a[n], a[n-1], ... , a[1], a[0] - коэффициенты многочлена степени n или цифры в системе счисления х, n - старший разряд числа.
Из приведенной формулы можно выразить рекуррентное соотношение:
p:=(p+a[i])*x;
которое выполняется n раз для i от n до 1 при начальном значении p=0. В конце к результату добавляем a[0]. В наших обозначениях вместо кода перевода числа из пятеричной системы в десятичную получим следующий код:
p:=0;
for i:=1 to length(a)-1 do
 p:=(p+ord(s[i])-ord('0'))*5;
p:=p+ord(s[i+1])-ord('0');
Этот вариант эффективнее, так как в процессе проверки и получения числового символа его можно сразу добавлять к сумме, учитывая, что последний числовой символ нужно просто сложить без умножения. Тогда количество вложенных циклов уменьшается. Получим следующий код программы:
Var p,sum,a,code:integer;
    c:char;
    s:string;
begin
    sum:=0;p:=0;s:='';
    while not eof() do begin
       read(c);
       if c in ['.',' ',#10,#13] then begin
           if s<>'' then begin
              val(s,a,code);
              if code=0 then begin
              p:=p/5;
              sum:=sum+p;end;
           end;

           S:='';p:=0;
       end
       else begin
         s:=s+c;
         if c in ['0'..'4'] then p:=(p+ord(c)-ord('0'))*5;
       end;
    end;
    write(sum);
end.


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

Задачи из сборника по ЕГЭ.
Разберем одну из таких задач (задачи и решения можно посмотреть на сайте kpolyakov.narod.ru). Наша цель - не просто решить задачу, а показать как ее можно оптимизировать, показать "правильные" рассуждения, которые приведут к верному решению задачи, т.е. рассмотреть различные варианты решения.

8) На вход программе подаются сведения о телефонах всех сотрудников некоторого учреждения. В первой строке сообщается количество сотрудников N, каждая из следующих N строк имеет следующий формат:

<Фамилия> <Инициалы> <телефон>
где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> - строка, состоящая не более чем из 4-х символов (буква, точка, буква, точка), <телефон> – семизначный номер, 3-я и 4, я, а также 5-я и 6-я цифры которого разделены символом «–». <Фамилия> и <Инициалы>, а также <Инициалы> и <телефон> разделены одним пробелом. Пример входной строки:
Иванов П.С. 555-66-77
Сотрудники одного подразделения имеют один и тот же номер телефона. Номера телефонов в учреждении отличаются только двумя последними цифрами. Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, сколько в среднем сотрудников работает в одном подразделении данного учреждения.

Решение с рассуждениями:
Из условия задачи видно, что требуется определить только последние два числа, чтобы посчитать сколько подразделений есть в учреждении. Это можно сделать разными способами:
1. считаем строку S и выделим последние цифры, затем переведем в число K:
readln(s);
l:=length(s);
s:=copy(s,l-1,2);
val(s,k,code);

или

readln(s);
p:=pos('-',s);delete(s,1,p);
p:=pos('-',s);delete(s,1,p);
val(s,k,code);

или

readln(s);
l:=ord(s[0]);//расчет длины строки
k:=ord(s[l])-ord('0')+(ord(s[l-1])-ord('0'))*10;

2. считываем символы C до второго знака тире и потом прочитаем число K:

read(c); while (c<>'-') do read(c);
read(c); while (c<>'-') do read(c);
    readln(k);

или 

repeat
  read(c);
until c='-';
repeat 
  read(c);
until c='-';
readln(k);

или 

for i:=1 to 2 do {на самом деле для оптимизации цикл не требуется}
 repeat
   read(c);
 until c='-';
readln(k);

Как видно из приведенных фрагментов программы - есть что использовать и над чем можно еще поработать.

Теперь нужно понять, как и где хранить эти найденные номера подразделений. Здесь тоже есть несколько вариантов:
1. запомним найденный номер в массив A (var A:array [1..100]of byte;), предварительно проверив, есть ли уже такой номер в массиве или нет. На это требуется дополнительный вложенный цикл. Количество элементов в массиве даст нам нужное количество подразделений M.

m:=0;
for i:=1 to n do begin
... //выделение последних двух цифр одним из предложенных методов
f:=true;
for j:=1 to m do 
      //если такое число есть
  if k=A[j] then begin f:=false; break end;
//если такого числа нет, то добавим в массив
if f then begin inc(m);A[m]:=k;end;
end;

2. зададим массив A логических значений (var A:array [0..99]of boolean;) или целых чисел (var A:array [0..99]of integer;) с индексами подразделений от 0 до 99 (больше номеров не потребуется), если номер подразделения К, то индекс массива К, значит элемент массива меняет значение с False на True или c 0 на 1. При этом массив предварительно нужно обнулить, например, используя процедуру FillChar(A, sizeof(A), 0).

fillchar(A,sizeof(A),0);
m:=0;
for i:=1 to n do begin
... //выделение последних двух цифр одним из предложенных методов
 if A[k]=0 then inc(m);{можно сразу считать количество подразделений}
A[k]:=1;
end;
3. Так как чисел не много, то для проверки "есть ли  уже такой номер в списке или нет" можно использовать тип данных множество A: set of byte. Тогда совсем просто: проверить есть ли номер во множестве A, если нет, то добавим этот номер в него. Одновременно считаем количество подразделений M.

m:=0;
A:=[];//пустое множество
for i:=1 to n do begin
... //выделение последних двух цифр одним из предложенных методов
 if not (k in A) then begin A:=A+[k]; inc(m); end;
end;

4. Вместо множества можно использовать строки с пробелами, но нужно учесть перевод чисел в строку. При этом максимально возможное количество символов из чисел и пробелов будет равно 2*10+3*90=290. Это больше разрешенного количества символов в строке 255. Если использовать всю строку из последних цифр, то понадобится 2*100=200 символов. Тогда не нужно переводить в число, но поиск нужного номера SK в строке S1 должен учитывать, чтобы подстрока начинается с нечетной позиции, иначе это может быть неверно. Например, ищем число 11, но в строке ее нет, но есть '0110', т.е. 1 и 10. Тогда нужно искать попарно в цикле:

sk:='';
for i:=1 to n do begin
 readln(s);
 l:=length(s);
 s1:=copy(s,l-1,2); 
 f:=true;
 for j:=1 to length(sk) div 2 do
   //если такое число уже есть
       if (s1[1]=sk[2*j-1]) and (s1[2]=sk[2*j]) then f:=false;

//если такого числа нет, то добавляем в строку
 if f then sk:=sk+s1; 
end;
m:=length(sk) div 2;

Последним моментов является вычисление среднего показателя. И здесь нужно учесть, что половинок из людей не бывает. Поэтому нужно результат округлить:

count:=round(n/m);

Итак, какой метод более оптимизированный? Скорее всего тот, где нет вложенных циклов и все считается за один проход ввода данных. Это вариант 2 и 3. Обработка строк и выделение числа - не сильно оптимизирован. Но нужно учесть, что циклы While и Repeat делают проверку каждый раз в отличие от цикла for. Сами процедуры со строками тоже требуют некоторого времени выполнения. Поэтому лучше выбрать способ третий из пункта 1. Для большей оптимизации можно сохранить код нуля в какую нибудь переменную или константу и в формуле только вычесть

kod0:= ord('0');
k:=ord(s[l])-kod0+(ord(s[l-1])-kod0)*10;

Для оптимизации всей программы рекомендуется использовать типы, близкие по разрядности процессора, ввиду того, что для чтения данных разного размера требуется перескочить через разность в разрядах, что для процессоров означает дополнительное время.
Так, лучше использовать integer вместо byte, так как в новых компиляторах это тип longint, который требует 32 бита - это разрядность большинства процессоров. Для процессоров нового поколения разрядность 64, поэтому для быстроты выполнения программы лучше использовать тип int64. Быстрота выполнения программы и минимальный размер памяти все время борются за оптимизацию!



Комментариев нет:

Отправить комментарий