По ка­на­лу связи пе­ре­да­ет­ся по­сле­до­ва­тель­ность по­ло­жи­тель­ных целых чисел … все числа не пре­вы­ша­ют 1000, их ко­ли­че­ство за­ра­нее не­из­вест­но. Каж­дое число пе­ре­да­ет­ся в виде от­дель­ной стро­ки, со­дер­жа­щей де­ся­тич­ную за­пись числа. При­зна­ком конца пе­ре­да­ва­е­мой по­сле­до­ва­тель­но­сти яв­ля­ет­ся число 0. Уча­сток по­сле­до­ва­тель­но­сти от эле­мен­та X_T до эле­мен­та на­зы­ва­ет­ся подъ­емом, если на этом участ­ке каж­дое сле­ду­ю­щее число боль­ше преды­ду­ще­го. Вы­со­той подъ­ема на­зы­ва­ет­ся раз­ность На­пи­ши­те эф­фек­тив­ную про­грам­му, ко­то­рая вы­чис­ля­ет наи­боль­шую вы­со­ту среди всех подъ­емов по­сле­до­ва­тель­но­сти. Если в по­сле­до­ва­тель­но­сти нет ни од­но­го подъ­ема, про­грам­ма вы­да­ет 0. Про­грам­ма долж­на на­пе­ча­тать отчет по сле­ду­ю­щей форме:

По­лу­че­но ... чисел Наи­боль­шая вы­со­та подъ­ема: …

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

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

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

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

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

Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

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

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

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

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

144

17

27

3

7

9

11

10

0

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

По­лу­че­но 8 чисел

Наи­боль­шая вы­со­та подъ­ема: 10

По ка­на­лу связи пе­ре­даётся по­сле­до­ва­тель­ность по­ло­жи­тель­ных целых чисел Х₁, Х₂, ... все числа не пре­вы­ша­ют 1000, их ко­ли­че­ство за­ра­нее не­из­вест­но. Каж­дое число пе­ре­даётся в виде от­дель­ной тек­сто­вой стро­ки, со­дер­жа­щей де­ся­тич­ную за­пись числа. При­зна­ком конца пе­ре­да­ва­е­мой по­сле­до­ва­тель­но­сти яв­ля­ет­ся число 0.

Уча­сток по­сле­до­ва­тель­но­сти от эле­мен­та Х_T до эле­мен­та X_T+N на­зы­ва­ет­ся подъёмом, если на этом участ­ке каж­дое сле­ду­ю­щее число боль­ше или равно преды­ду­ще­му, при­чем уча­сток нель­зя рас­ши­рить, т. е.

1)  Т = 1 или Х_T-1 > Х_T

2)  X_T+N  — по­след­ний эле­мент по­сле­до­ва­тель­но­сти или X_T+N > X_T+N+1. Вы­со­той подъёма на­зы­ва­ет­ся раз­ность X_T+N − Х_T. Подъём счи­та­ет­ся зна­чи­тель­ным, если вы­со­та подъёма боль­ше ве­ли­чи­ны ми­ни­маль­но­го эле­мен­та этого подъ­ема.

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

Про­грам­ма долж­на вы­ве­сти ре­зуль­та­ты в сле­ду­ю­щей форме:

По­лу­че­но чисел: ...

Най­де­но зна­чи­тель­ных подъ­емов: ...

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

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

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

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

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

Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

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

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

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

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

144

17

21

27

3

7

9

11

25

0

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

По­лу­че­но чисел: 9

Най­де­но зна­чи­тель­ных подъ­емов: 1