Для по­стро­е­ния про­грам­мы, эф­фек­тив­ной по вре­ме­ни, можно опре­де­лить для каж­до­го эле­мен­та вход­ных дан­ных ми­ни­маль­ное зна­че­ние от на­ча­ла дан­ных до этого эле­мен­та вклю­чи­тель­но. Затем нужно умно­жать каж­дый эле­мент,

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

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

алг

нач

цел s = 6 | тре­бу­е­мое рас­сто­я­ние между по­ка­за­ни­я­ми

цел N

ввод N

вещ а | оче­ред­ное по­ка­за­ние при­бо­ра

ве­щтаб мини[0:s - 1] | те­ку­щие ми­ни­му­мы

| по­след­них 6 эле­мен­тов

цел i

ввод мини[1]

нц для i от 2 до s

ввод а

мини[mod(i, s)] := min(а, мини[i - 1])

кц

вещ м | ми­ни­маль­ное зна­че­ние про­из­ве­де­ния

м := 1.0 * 1000 * 1000 + 1

нц для i от s + 1 до N

ввод а

м := min(м, а * мини[mod(i, s)])

мини[mod(i, s)] := min(а, мини[mod(i - 1, s)])

кц

вывод м

кон

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

алг

нач

цел s = 6 | тре­бу­е­мое рас­сто­я­ние между по­ка­за­ни­я­ми

цел N

ввод N

ве­щтаб а[0:s - 1] | k-е вве­ден­ное число

| за­пи­сы­ва­ем в ячей­ку а[mod(k, 6)]

вещ а_ | оче­ред­ное по­ка­за­ние при­бо­ра

цел i

| Про­лог. Ввод пер­вых шести чисел

нц для i от 1 до s

ввод а_

а[mod(i, s)] := а_

кц

| Ввод осталь­ных зна­че­ний,

| поиск ми­ни­маль­но­го про­из­ве­де­ния

вещ мини = 1001 | ми­ни­маль­ное вве­ден­ное число

| (не счи­тая 6 по­след­них)

вещ м | ми­ни­маль­ное зна­че­ние про­из­ве­де­ния

м := 1.0 * 1000 * 1000 + 1

нц для i от s + 1 до N

ввод а_

мини := min(мини, а[mod(i, s)])

м := min(м, а_ * мини)

а[mod(i, s)] := а_

кц

вывод м

кон

Далее при­ве­де­ны ана­ло­гич­ные про­грам­мы на язы­ках Python и Пас­каль. В ре­ше­нии на языке Python ис­поль­зу­ет­ся «за­цик­лен­ный» спи­сок prev_min из s = 6 эле­мен­тов, в ко­то­ром хра­нят­ся по­сле­до­ва­тель­ные ми­ни­му­мы счи­тан­ных чисел. Если про­грам­ма по­лу­ча­ет на вход по­сле­до­ва­тель­ность чисел a[0], a[1], … , a[N-1], то сна­ча­ла за­пол­ня­ют­ся эле­мен­ты спис­ка prev_min: a[2]), … , prev_min[s - 1] = min(a[0], a[1], … , a[s - 1]). При этом до­пу­сти­мых пар эле­мен­тов (рас­сто­я­ние между ко­то­ры­ми не мень­ше s) нет, по­это­му зна­че­ние пе­ре­мен­ной result, в ко­то­рой хра­нит­ся ответ, не об­нов­ля­ет­ся. Далее счи­ты­ва­ет­ся зна­че­ние эле­мен­та по­сле­до­ва­тель­но­сти a[s], рас­смат­ри­ва­ет­ся его про­из­ве­де­ние на prev_min[0] = a[0], при не­об­хо­ди­мо­сти (если по­лу­чен­ное про­из­ве­де­ние мень­ше зна­че­ния result) об­нов­ля­ет­ся зна­че­ние result. После этого в эле­мент спис­ка prev_min[0] за­пи­сы­ва­ет­ся ми­ни­мум из счи­тан­но­го числа a[s] и prev_min[s - 1], тем самым prev_min[0] ста­но­вит­ся рав­ным min(a[0], a[1], … , a[s]). Далее, на каж­дом шаге в пе­ре­мен­ную next_num счи­ты­ва­ет­ся оче­ред­ной эле­мент по­сле­до­ва­тель­но­сти a[i], он пе­ре­мно­жа­ет­ся с prev_min[i % s], в ко­то­ром в тот мо­мент хра­нит­ся min(a[0], a[1], … , a[i - s]), при не­об­хо­ди­мо­сти об­нов­ля­ет­ся пе­ре­мен­ная result, и далее в ре­зуль­та­те вы­пол­не­ния при­сва­и­ва­ния prev_min[i % s] = min(prev_min[(i - 1) % s], next_num) зна­че­ние prev_min[i % s] ста­но­вит­ся равно min(a[0], a[1], … , a[i]). Это зна­че­ние prev_min[i % s] будет затем ис­поль­зо­ва­но через s шагов вы­пол­не­ния внеш­не­го цикла, т. е. когда будет счи­тан эле­мент a[i + s]. При этом все эле­мен­ты счи­тан­ной по­сле­до­ва­тель­но­сти не со­хра­ня­ют­ся в спис­ке.

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

s = 6

result = 1000 * 1000

N = int(input())

prev_min = [0] * s

prev_min[0] = float(input())

for i in range(1, s):

prev_min[i] = min(float(input()), prev_min[i - 1])

for i in range(s, N):

next_num = float(input())

result = min(result, next_num * prev_min[i % s])

prev_min[i % s] = min(prev_min[(i - 1) % s], next_num)

print(result)

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

Про­грам­ма эф­фек­тив­на и по вре­ме­ни, и по па­мя­ти

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

program c4;

const s = 6; {тре­бу­е­мое рас­сто­я­ние между по­ка­за­ни­я­ми}

var

N: integer;

a: array[0..s - 1] of real; {хра­не­ние по­ка­за­ний при­бо­ра}

{k-е вве­ден­ное число за­пи­сы­ва­ем в ячей­ку a[k mod 6]}

a_: real; {ввод оче­ред­но­го по­ка­за­ния}

mn: real; {ми­ни­маль­ное вве­ден­ное число}

{не счи­тая 6 по­след­них}

m: real; {ми­ни­маль­ное зна­че­ние про­из­ве­де­ния}

i: integer;

begin

readln(N);

{ Про­лог. Ввод пер­вых шести чисел}

for i:=1 to s do

begin

readln(a_);

a[i mod s] := a_

end;

{Ввод осталь­ных зна­че­ний, поиск ми­ни­маль­но­го про­из­ве­де­ния}

mn := 1001; m := 1000 * 1000+1;

for i := s + 1 to N do

begin

readln(a_);

if a[i mod s] < mn then mn := a[i mod s];

if a_ * mn < m then m := a_ * mn;

a[i mod s] := a_

end;

writeln(m)

end.

При­мер 4. Ре­ше­ние за­да­чи А на языке Пас­каль.

var
  a: array[1..10000] of real; {ис­ход­ные дан­ные}
  N: integer; {ко­ли­че­ство по­ка­за­ний при­бо­ра в серии}
  min: real; {ми­ни­маль­ное про­из­ве­де­ние}
  i, j: integer;
begin
  readln(N);
  for i := 1 to N do read(a[i]);
  min := 1000*1000+1;
  for i := 1 to N-6 do
    for j := i+6 to N do
      if (a[i]*a[j] < min) then min := a[i]*a[j];
  writeln(min);
end.