menu
person

Задача №2914

На спут­ни­ке «Фотон» уста­нов­лен при­бор, пред­на­зна­чен­ный для из

Поиск задачи:

На спут­ни­ке «Фотон» уста­нов­лен при­бор, пред­на­зна­чен­ный для из­ме­ре­ния энер­гии кос­ми­че­ских лучей. Каж­дую ми­ну­ту при­бор пе­ре­даёт по ка­на­лу связи не­от­ри­ца­тель­ное ве­ще­ствен­ное число — ко­ли­че­ство энер­гии, по­лу­чен­ной за по­след­нюю ми­ну­ту, из­ме­рен­ное в услов­ных еди­ни­цах. Вре­ме­нем, в те­че­ние ко­то­ро­го про­ис­хо­дит пе­ре­да­ча, можно пре­не­бречь. Не­об­хо­ди­мо найти в за­дан­ной серии по­ка­за­ний при­бо­ра ми­ни­маль­ное про­из­ве­де­ние двух по­ка­за­ний, между мо­мен­та­ми пе­ре­да­чи ко­то­рых про­шло не менее 6 минут. Ко­ли­че­ство энер­гии, по­лу­ча­е­мое при­бо­ром за ми­ну­ту, не пре­вы­ша­ет 1000 услов­ных еди­ниц. Общее ко­ли­че­ство по­ка­за­ний при­бо­ра в серии не пре­вы­ша­ет 10 000. На­пи­ши­те на любом языке про­грам­ми­ро­ва­ния про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи. Ваша оцен­ка будет за­ви­сеть не толь­ко от пра­виль­но­сти про­грам­мы, но и от того, на­сколь­ко она эф­фек­тив­на. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству по­лу­чен­ных по­ка­за­ний при­бо­ра N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти, — 4 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, — 3 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, не­эф­фек­тив­ную ни по вре­ме­ни, ни по па­мя­ти, — 2 балла. Перед про­грам­мой ука­жи­те вер­сию языка и крат­ко опи­ши­те ис­поль­зо­ван­ный ал­го­ритм. В пер­вой стро­ке задаётся число N — общее ко­ли­че­ство по­ка­за­ний при­бо­ра. Га­ран­ти­ру­ет­ся, что N > 6. В каж­дой из сле­ду­ю­щих N строк задаётся одно не­от­ри­ца­тель­ное ве­ще­ствен­ное число — оче­ред­ное по­ка­за­ние при­бо­ра.

 

При­мер вход­ных дан­ных:

11

12

45

5

4

25

23

21

20

10

12

26

 

Про­грам­ма долж­на вы­ве­сти одно число — опи­сан­ное в усло­вии про­из­ве­де­ние.

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

48

 

По­яс­не­ние.

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

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

 

 

При­мер 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.

Категория: по информатике | Добавил: Просмотров: 1 | Теги: Об­ра­бот­ка символьных строк | Рейтинг: 0.0/0
Всего комментариев: 0