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

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

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

Вам пред­ла­га­ет­ся два за­да­ния, свя­зан­ных с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние  — 0 бал­лов.

За­да­ние Б яв­ля­ет­ся усложнённым ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме.

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

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния А. Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А  — 2 балла.

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик). Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству по­лу­чен­ных по­ка­за­ний при­бо­ра N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.

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

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния Б. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти,  — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти,  — 3 балла.

На­по­ми­на­ем! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

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

6

123.4

0.2

200.2

0.0

6.7

218.0

Про­грам­ма долж­на вы­ве­сти в одной стро­ке сна­ча­ла ко­ли­че­ство эле­мен­тов в ос­нов­ном мно­же­стве, а затем  — его ми­ни­маль­ный эле­мент.

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