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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое число, по аб­со­лют­ной ве­ли­чи­не не пре­вы­ша­ю­щее 10⁹.

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

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

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

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

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

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

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

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

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

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

5

123

2

-1000

0

10

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

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

1 2 5

На уско­ри­те­ле для боль­шо­го числа ча­стиц про­из­во­дят­ся за­ме­ры ско­ро­сти каж­дой из них. Ско­рость ча­сти­цы  — это целое число (по­ло­жи­тель­ное, от­ри­ца­тель­ное или 0). Ча­стиц, ско­рость ко­то­рых из­ме­ре­на, может быть очень много, но не может быть мень­ше трёх. Ско­ро­сти всех ча­стиц раз­лич­ны. В серии обя­за­тель­но при­сут­ству­ет хотя бы одна ча­сти­ца с от­ри­ца­тель­ной ско­ро­стью.

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

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое число, по аб­со­лют­ной ве­ли­чи­не не пре­вы­ша­ю­щее 10⁹. Все N чисел раз­лич­ны.

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

5

123

2

−1000

0

10

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

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

1 2 3 5

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое число, по аб­со­лют­ной ве­ли­чи­не не пре­вы­ша­ю­щее 10⁹.

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

5

123

2

-1000

0

10

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

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

1 2 5

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

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 10⁹. Все N чисел раз­лич­ны. Хотя бы одно из чисел нечётно.

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

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

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

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

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

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

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

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

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

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

3

123

0

2

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

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

1 3

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно не­от­ри­ца­тель­ное ве­ще­ствен­ное число с точ­но­стью до 1 знака после де­ся­тич­ной точки. При­мер вход­ных дан­ных:

5

123.4

0.2

7.2

0.0

314 .1

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

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

3 7.2

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

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое число, по аб­со­лют­ной ве­ли­чи­не не пре­вы­ша­ю­щее 10⁹.

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

5

123

2

-1000

0

10

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

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

1 2 5

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

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 10⁹. Все N чисел раз­лич­ны. Хотя бы одно из чисел нечётно.

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

5

123

2

1000

0

10

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

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

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

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

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

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

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство ча­стиц N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 10⁹. Все N чисел раз­лич­ны. Хотя бы одно из чисел нечётно.

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

5

123

2

1000

0

10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3

123

0

2

Про­грам­ма долж­на вы­ве­сти в по­ряд­ке воз­рас­та­ния но­ме­ра сиг­на­лов, ко­то­рые при­над­ле­жат ос­нов­но­му под­мно­же­ству дан­но­го участ­ка. Ну­ме­ра­ция эле­мен­тов по­сле­до­ва­тель­но­сти ведётся с еди­ни­цы. При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных: 1 3.

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

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

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

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

5

123

2

1000

0

10

Про­грам­ма долж­на вы­ве­сти в по­ряд­ке воз­рас­та­ния но­ме­ра сиг­на­лов, ко­то­рые при­над­ле­жат ос­нов­но­му под­мно­же­ству дан­но­го участ­ка. Ну­ме­ра­ция эле­мен­тов по­сле­до­ва­тель­но­сти ведётся с еди­ни­цы. При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных: 2 3 5.

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

1)  все вер­ши­ны тре­уголь­ни­ка при­над­ле­жат за­дан­но­му мно­же­ству;

2)  ни одна вер­ши­на не лежит на осях ко­ор­ди­нат;

3)  тре­уголь­ник не пе­ре­се­ка­ет­ся с осью Ox, но пе­ре­се­ка­ет­ся с осью Oy.

На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по ис­поль­зу­е­мой па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

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

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

Вход­ные дан­ные

В пер­вой стро­ке задаётся N – ко­ли­че­ство точек в за­дан­ном мно­же­стве. Каж­дая из сле­ду­ю­щих строк со­дер­жит два целых числа x и y – ко­ор­ди­на­ты оче­ред­ной точки. Га­ран­ти­ру­ет­ся, что 1 ≤ N ≤ 10000, –1000 ≤ x, y ≤ 1000, ни­ка­кие две точки не сов­па­да­ют, ни­ка­кие три не лежат на одной пря­мой.

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

4

6 6

−8 8

−9 −9

7 5

Вы­ход­ные дан­ные

Не­об­хо­ди­мо вы­ве­сти един­ствен­ное число: ко­ли­че­ство удо­вле­тво­ря­ю­щих тре­бо­ва­ни­ям тре­уголь­ни­ков.

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

1

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

1)  все вер­ши­ны тре­уголь­ни­ка при­над­ле­жат за­дан­но­му мно­же­ству;

2)  ни одна вер­ши­на не лежит на осях ко­ор­ди­нат;

3)  тре­уголь­ник не пе­ре­се­ка­ет­ся с осью Oy, но пе­ре­се­ка­ет­ся с осью Ox.

На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по ис­поль­зу­е­мой па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

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

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

Вход­ные дан­ные

В пер­вой стро­ке задаётся N – ко­ли­че­ство точек в за­дан­ном мно­же­стве. Каж­дая из сле­ду­ю­щих строк со­дер­жит два целых числа x и y – ко­ор­ди­на­ты оче­ред­ной точки. Га­ран­ти­ру­ет­ся, что 1 ≤ N ≤ 10000, –1000 ≤ x, y ≤ 1000, ни­ка­кие две точки не сов­па­да­ют, ни­ка­кие три не лежат на одной пря­мой.

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

4

6 6

−8 8

−9 −9

−7 5

Вы­ход­ные дан­ные

Не­об­хо­ди­мо вы­ве­сти един­ствен­ное число: ко­ли­че­ство удо­вле­тво­ря­ю­щих тре­бо­ва­ни­ям тре­уголь­ни­ков.

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

1

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

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

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

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

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

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

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

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

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

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

За­да­ча А. Ко­ли­че­ство пар из­вест­но за­ра­нее и равно 6. Числа не пре­вы­ша­ют 30 000.

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

5 4

3 2

1 1

18 3

11 12

2 5

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

23

За­да­ча Б. Ко­ли­че­ство пар N не из­вест­но за­ра­нее и может при­ни­мать зна­че­ния 2 <= N <= 200 000. На вход по­да­ет­ся сна­ча­ла ко­ли­че­ство пар, затем сами пары. Числа по мо­ду­лю не пре­вы­ша­ют 30 000.

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

6

5 4

3 2

1 1

18 3

11 12

2 5

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

23

На вход даны пары чисел. Нужно вы­брать из каж­дой пары по од­но­му числу так, чтобы сумма всех вы­бран­ных чисел не была крат­на 4 и при этом была мак­си­маль­но воз­мож­ной. На­пи­ши­те про­грам­му, вы­во­дя­щую такую сумму на экран. Если же ее не­воз­мож­но по­лу­чить, вы­ве­ди­те 0. Баллы на­чис­ля­ют­ся за ту из под­за­дач, что ре­ше­на на боль­шее ко­ли­че­ство бал­лов. За­да­ча А дает 2 балла, за­да­ча Б - 4 балла. В за­да­че А при­ве­ди­те не­эф­фек­тив­ный ал­го­ритм. При ре­ше­нии ука­зы­вай­те, какую под­за­да­чу де­ла­е­те. За ал­го­ритм, не­эф­фек­тив­ный по вре­ме­ни ИЛИ па­мя­ти, да­ет­ся 3 балла, по вре­ме­ни И па­мя­ти - 2 балла.

За­да­ча А. Ко­ли­че­ство пар из­вест­но за­ра­нее и равно 6. Числа не пре­вы­ша­ют 30 000.

За­да­ча Б. Ко­ли­че­ство пар N не из­вест­но за­ра­нее и может при­ни­мать зна­че­ния 2 <= N <= 200 000. На вход по­да­ет­ся сна­ча­ла ко­ли­че­ство пар, затем сами пары. Числа по мо­ду­лю не пре­вы­ша­ют 30 000.

Дан набор из N целых по­ло­жи­тель­ных чисел. Не­об­хо­ди­мо вы­брать из на­бо­ра про­из­воль­ное ко­ли­че­ство чисел так, чтобы их сумма была как можно боль­ше и при этом не де­ли­лась на 6. В от­ве­те нужно ука­зать ко­ли­че­ство вы­бран­ных чисел и их сумму, сами числа вы­во­дить не надо. Если по­лу­чить нуж­ную сумму не­воз­мож­но, счи­та­ет­ся, что вы­бра­но 0 чисел и их сумма равна 0.

На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если при уве­ли­че­нии ко­ли­че­ства ис­ход­ных чисел N в k раз время ра­бо­ты про­грам­мы уве­ли­чи­ва­ет­ся не более чем в k раз.

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

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

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

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

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

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

Опи­са­ние вход­ных и вы­ход­ных дан­ных

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 1000).

В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000.

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

3

1

2

3

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

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

2 5

В дан­ном слу­чае из пред­ло­жен­но­го на­бо­ра нужно вы­брать два числа (2 и 3), их сумма равна 5.

Дан набор из N целых по­ло­жи­тель­ных чисел. Не­об­хо­ди­мо вы­брать из на­бо­ра про­из­воль­ное ко­ли­че­ство чисел так, чтобы их сумма была как можно боль­ше и при этом не де­ли­лась на 8. В от­ве­те нужно ука­зать ко­ли­че­ство вы­бран­ных чисел и их сумму, сами числа вы­во­дить не надо. Если по­лу­чить нуж­ную сумму не­воз­мож­но, счи­та­ет­ся, что вы­бра­но 0 чисел и их сумма равна 0.

На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если при уве­ли­че­нии ко­ли­че­ства ис­ход­ных чисел N в k раз время ра­бо­ты про­грам­мы уве­ли­чи­ва­ет­ся не более чем в k раз.

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

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

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

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

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

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

Опи­са­ние вход­ных и вы­ход­ных дан­ных

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 1000).

В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000.

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

3

1

2

5

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

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

2 7

В дан­ном слу­чае из пред­ло­жен­но­го на­бо­ра нужно вы­брать два числа (2 и 5), их сумма равна 7.