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

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство пар N (1 ≤ N ≤ 100 000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

6

1 3

5 12

6 9

5 4

3 3

1 1

Для ука­зан­ных вход­ных дан­ных зна­че­ни­ем ис­ко­мой суммы долж­но быть число 32.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла А, затем для файла B.

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

Ответ:

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

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство чисел N (1 ≤ N ≤ 100 000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 1000.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

5

40

1000

7

28

55

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

28000 В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мо­го про­из­ве­де­ния для файла А, затем для файла B.

Ответ:

На вход про­грам­мы по­сту­па­ет по­сле­до­ва­тель­ность из N целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары раз­лич­ных эле­мен­тов по­сле­до­ва­тель­но­сти (эле­мен­ты пары не обя­за­ны сто­ять в по­сле­до­ва­тель­но­сти рядом, по­ря­док эле­мен­тов в паре не важен). Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство пар, для ко­то­рых про­из­ве­де­ние эле­мен­тов де­лит­ся на 26.

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 60 000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 10 000. В ка­че­стве ре­зуль­та­та про­грам­ма долж­на на­пе­ча­тать одно число: ко­ли­че­ство пар, в ко­то­рых про­из­ве­де­ние эле­мен­тов крат­но 26.

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство чисел N (1 ≤ N ≤ 60 000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

4

2

6

13

39

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

4

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла А, затем для файла B.

Ответ:

По­яс­не­ние. Из четырёх за­дан­ных чисел можно со­ста­вить 6 по­пар­ных про­из­ве­де­ний: 2 · 6, 2 · 13, 2 · 39, 6 · 13, 6 · 39, 13 · 39 (ре­зуль­та­ты: 12, 26, 78, 78, 234, 507). Из них на 26 де­лят­ся 4 про­из­ве­де­ния (2 · 13  =  26; 2 · 39  =  78; 6 · 13  =  78; 6 · 39  =  234).

Дана по­сле­до­ва­тель­ность N целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары эле­мен­тов по­сле­до­ва­тель­но­сти, раз­ность ко­то­рых чётна, и в этих парах, по край­ней мере, одно из чисел пары де­лит­ся на 17. По­ря­док эле­мен­тов в паре не­ва­жен. Среди всех таких пар нужно найти и вы­ве­сти пару с мак­си­маль­ной сум­мой эле­мен­тов. Если оди­на­ко­вую мак­си­маль­ную сумму имеет не­сколь­ко пар, можно вы­ве­сти любую из них. Если под­хо­дя­щих пар в по­сле­до­ва­тель­но­сти нет, нужно вы­ве­сти два нуля.

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

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

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

5

34

12

51

52

51

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

51 51 В от­ве­те ука­жи­те че­ты­ре числа: сна­ча­ла зна­че­ние ис­ко­мой пары для файла А (два числа через про­бел), затем для файла B (два числа через про­бел). Числа пар впи­ши­те в по­ряд­ке убы­ва­ния.

Ответ:

По­яс­не­ние. Из дан­ных пяти чисел можно со­ста­вить три раз­лич­ные пары, удо­вле­тво­ря­ю­щие усло­вию: (34, 12), (34, 52), (51, 51). Наи­боль­шая сумма по­лу­ча­ет­ся в паре (51, 51). Эта пара до­пу­сти­ма, так как число 51 встре­ча­ет­ся в ис­ход­ной по­сле­до­ва­тель­но­сти два­жды.

На вход про­грам­мы по­сту­па­ет по­сле­до­ва­тель­ность из N на­ту­раль­ных чисел. Рас­смат­ри­ва­ют­ся все пары раз­лич­ных эле­мен­тов по­сле­до­ва­тель­но­сти, у ко­то­рых раз­лич­ные остат­ки от де­ле­ния на d  =  160 и хотя бы одно из чисел де­лит­ся на p  =  7. Среди таких пар не­об­хо­ди­мо найти и вы­ве­сти пару с мак­си­маль­ной сум­мой эле­мен­тов.

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

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 1000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000. В ка­че­стве ре­зуль­та­та про­грам­ма долж­на на­пе­ча­тать эле­мен­ты ис­ко­мой пары. Если среди най­ден­ных пар мак­си­маль­ную сумму имеют не­сколь­ко, то можно на­пе­ча­тать любую из них. Если таких пар нет, то вы­ве­сти два нуля.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

4

168

7

320

328

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

168 320 В от­ве­те ука­жи­те че­ты­ре числа: сна­ча­ла зна­че­ние ис­ко­мой пары для файла А (два числа через про­бел по воз­рас­та­нию), затем для файла B (два числа через про­бел по воз­рас­та­нию).

Ответ:

Дана по­сле­до­ва­тель­ность N целых по­ло­жи­тель­ных чисел. Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство пар эле­мен­тов этой по­сле­до­ва­тель­но­сти, сумма ко­то­рых де­лит­ся на m  =  80 и при этом хотя бы один эле­мент из пары боль­ше b  =  50.

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

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

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

6

40

40

120

30

50

110

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

3 В от­ве­те ука­жи­те два числа: сна­ча­ла ко­ли­че­ство пар для файла А, затем для файла B.

Ответ:

По­яс­не­ние. Из дан­ных шести чисел можно со­ста­вить три пары, удо­вле­тво­ря­ю­щие усло­вию: (40, 120), (40, 120), (50, 110). У пар (40, 40) и (30, 50) сумма де­лит­ся на 80, но оба эле­мен­та в этих парах не пре­вы­ша­ют 50.

На вход про­грам­мы по­сту­па­ет по­сле­до­ва­тель­ность из n целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары эле­мен­тов по­сле­до­ва­тель­но­сти a_i и a_j, такие, что i < j и a_i > a_j (пер­вый эле­мент пары боль­ше вто­ро­го; i и j  — по­ряд­ко­вые но­ме­ра чисел в по­сле­до­ва­тель­но­сти вход­ных дан­ных). Среди пар, удо­вле­тво­ря­ю­щих этому усло­вию, не­об­хо­ди­мо найти и на­пе­ча­тать пару с мак­си­маль­ной сум­мой эле­мен­тов, ко­то­рая де­лит­ся на m  =  120. Если среди най­ден­ных пар мак­си­маль­ную сумму имеют не­сколь­ко, то можно на­пе­ча­тать любую из них.

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

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел n (2 ≤ n ≤ 12 000).

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

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

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

6

60

140

61

100

300

59

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

140 100 В от­ве­те ука­жи­те че­ты­ре числа: сна­ча­ла ис­ко­мую пару чисел для файла А (два числа через про­бел), затем для файла B (два числа через про­бел).

Ответ:

По­яс­не­ние. Из шести за­дан­ных чисел можно со­ста­вить три пары, сумма эле­мен­тов ко­то­рых де­лит­ся на m  =  120: 60 + 300, 140 + 100 и 61 + 59. Во вто­рой и тре­тьей из этих пар пер­вый эле­мент боль­ше вто­ро­го, но во вто­рой паре сумма боль­ше.

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

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

Пер­вая стро­ка вход­но­го файла со­дер­жит число N  — общее ко­ли­че­ство пар в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

6

1 3

5 10

6 9

5 4

3 3

1 1

Для ука­зан­ных дан­ных ис­ко­мая сумма равна 30.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла А, затем для файла B.

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

Ответ:

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

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

Пер­вая стро­ка вход­но­го файла со­дер­жит число N  — общее ко­ли­че­ство троек в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит три на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.

При­мер вход­но­го файла:

3

1 2 3

5 12 4

6 9 7

Для ука­зан­ных дан­ных ис­ко­мая сумма равна 24, она со­от­вет­ству­ет та­ко­му рас­пре­де­ле­нию чисел по груп­пам: (1, 5, 6), (2, 4, 7), (3, 12, 9).

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла A, затем для файла B.

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

Ответ:

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

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

Пер­вая стро­ка вход­но­го файла со­дер­жит число N  — общее ко­ли­че­ство пар в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.

При­мер вход­но­го файла:

5

15 8

5 11

6 3

7 2

9 14

Для ука­зан­ных дан­ных надо вы­брать числа 15, 11, 6, 7 и 14. Боль­шин­ство из них нечётны, сумма вы­бран­ных чисел равна 53 и тоже нечётна. В от­ве­те надо за­пи­сать число 53.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла A, затем для файла B.

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

Ответ:

В тек­сто­вом файле за­пи­сан набор на­ту­раль­ных чисел, не пре­вы­ша­ю­щих 10⁸. Га­ран­ти­ру­ет­ся, что все числа раз­лич­ны. Из на­бо­ра нужно вы­брать три числа, сумма ко­то­рых де­лит­ся на 3. Какую наи­боль­шую сумму можно при этом по­лу­чить?

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число.

При­мер вход­но­го файла:

4

5

8

14

11 В дан­ном слу­чае есть че­ты­ре под­хо­дя­щие трой­ки: 5, 8, 11 (сумма 24); 5, 8 14 (сумма 27); 5, 14 11 (сумма 30) и 8, 14, 11 (сумма 33). В от­ве­те надо за­пи­сать число 33.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла A, затем для файла B.

Ответ:

В тек­сто­вом файле за­пи­сан набор пар на­ту­раль­ных чисел, не пре­вы­ша­ю­щих 10 000. Не­об­хо­ди­мо вы­брать из на­бо­ра не­ко­то­рые пары так, чтобы пер­вое число в каж­дой вы­бран­ной паре было нечётным, сумма бо́льших чисел во всех вы­бран­ных парах была нечётной, а сумма мень­ших  — чётной. Какую наи­боль­шую сумму чисел во всех вы­бран­ных парах можно при этом по­лу­чить?

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство пар в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит пару чисел.

При­мер вход­но­го файла:

4

5 2

8 15

7 14

11 9 В дан­ном слу­чае есть три под­хо­дя­щие пары: (5, 2), (7, 14) и (11, 9). Пара (8, 15) не под­хо­дит, так как в ней пер­вое число чётное. Чтобы удо­вле­тво­рить тре­бо­ва­ния, надо взять пары (7, 14) и (11, 9). Сумма бо́льших чисел в этом слу­чае равна 25, сумма мень­ших равна 16. Общая сумма равна 41. В от­ве­те надо ука­зать число 41.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла A, затем для файла B.

Ответ:

Име­ет­ся набор дан­ных, со­сто­я­щий из троек по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой трой­ки ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на k  =  109 и при этом была мак­си­маль­но воз­мож­ной. Га­ран­ти­ру­ет­ся, что ис­ко­мую сумму по­лу­чить можно. Про­грам­ма долж­на на­пе­ча­тать одно число  — мак­си­маль­но воз­мож­ную сумму, со­от­вет­ству­ю­щую усло­ви­ям за­да­чи.

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство троек N (1 ≤ N ≤ 1 000 000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит три на­ту­раль­ных числа, не пре­вы­ша­ю­щих 20 000.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

6

1 3 7

5 12 6

6 9 11

5 4 8

3 5 4

1 1 1

Для ука­зан­ных вход­ных дан­ных, в слу­чае, если k  =  5, зна­че­ни­ем ис­ко­мой суммы яв­ля­ет­ся число 44.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла А, затем для файла B.

Ответ:

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

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство чисел N (2 ≤ N ≤ 68000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 10000. Про­грам­ма долж­на вы­ве­сти длину най­ден­ной по­сле­до­ва­тель­но­сти.

При­мер вход­но­го файла:

8

2

3

4

93

42

34

5

95

Для де­ли­те­ля 50 при ука­зан­ных вход­ных дан­ных зна­че­ни­ем ис­ко­мой суммы долж­но быть число 100 (3 + 4 + 93 или 5 + 95). Сле­до­ва­тель­но, ответ на за­да­чу  — 2. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой длины для файла A, затем для файла B.

Ответ:

Дана по­сле­до­ва­тель­ность из N на­ту­раль­ных чисел. Рас­смат­ри­ва­ют­ся все её не­пре­рыв­ные под­по­сле­до­ва­тель­но­сти, такие что сумма эле­мен­тов каж­дой из них крат­на k  =  43. Най­ди­те среди них под­по­сле­до­ва­тель­ность с мак­си­маль­ной сум­мой, опре­де­ли­те её длину. Если таких под­по­сле­до­ва­тель­но­стей най­де­но не­сколь­ко, в от­ве­те ука­жи­те ко­ли­че­ство эле­мен­тов самой ко­рот­кой из них.

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых со­дер­жит в пер­вой стро­ке ко­ли­че­ство чисел N (1 ≤ N ≤ 10 000 000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

14

1

2

1

4

93

8

5

95

6

4

3

2

8

6 В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой длины для файла А, затем  — для файла B. Для при­ве­ден­но­го при­ме­ра ответ  — 7.

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

Дана по­сле­до­ва­тель­ность на­ту­раль­ных чисел. Не­об­хо­ди­мо найти мак­си­маль­но воз­мож­ную сумму её не­пре­рыв­ной под­по­сле­до­ва­тель­но­сти, в ко­то­рой ко­ли­че­ство чётных эле­мен­тов крат­но k  =  10.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число. Га­ран­ти­ру­ет­ся, что общая сумма всех чисел не пре­вы­ша­ет 2 · 10⁹.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла A, затем для файла B.

Ответ:

На каж­дом 3-⁠м ки­ло­мет­ре коль­це­вой ав­то­до­ро­ги с дву­сто­рон­ним дви­же­ни­ем уста­нов­ле­ны кон­тей­не­ры для му­со­ра. Длина коль­це­вой ав­то­до­ро­ги равна 3N ки­ло­мет­ров. Ну­ле­вой ки­ло­метр и 3N-⁠й ки­ло­метр ав­то­до­ро­ги на­хо­дят­ся в одной точке. Из­вест­но ко­ли­че­ство му­со­ра, ко­то­рое на­кап­ли­ва­ет­ся еже­днев­но в каж­дом из кон­тей­не­ров. Из каж­до­го пунк­та мусор вы­во­зит от­дель­ный му­со­ро­воз. Сто­и­мость до­став­ки му­со­ра вы­чис­ля­ет­ся как про­из­ве­де­ние ко­ли­че­ства му­со­ра на рас­сто­я­ние от пунк­та до цен­тра пе­ре­ра­бот­ки. Центр пе­ре­ра­бот­ки от­хо­дов от­кры­ли в одном из пунк­тов сбора му­со­ра таким об­ра­зом, чтобы общая сто­и­мость до­став­ки му­со­ра из всех пунк­тов в этот центр была ми­ни­маль­ной.

Опре­де­ли­те ми­ни­маль­ные рас­хо­ды на до­став­ку му­со­ра в центр пе­ре­ра­бот­ки от­хо­дов.

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

Дано два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (1 ≤ N ≤ 10 000 000)  — ко­ли­че­ство пунк­тов сбора му­со­ра на коль­це­вой ав­то­до­ро­ге. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся число  — ко­ли­че­ство му­со­ра в кон­тей­не­ре (все числа на­ту­раль­ные, ко­ли­че­ство му­со­ра в каж­дом пунк­те не пре­вы­ша­ет 1000). Числа ука­за­ны в по­ряд­ке рас­по­ло­же­ния кон­тей­не­ров на ав­то­ма­ги­стра­ли, на­чи­ная с пер­во­го ки­ло­мет­ра.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла B.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле:

6

8

20

5

13

7

19

При таких ис­ход­ных дан­ных, если кон­тей­не­ры уста­нов­ле­ны на каж­дом ки­ло­мет­ре ав­то­до­ро­ги, не­об­хо­ди­мо от­крыть центр пе­ре­ра­бот­ки в пунк­те 6. В этом слу­чае сумма транс­порт­ных за­трат со­ста­вит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.

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

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

Ответ:

Дана по­сле­до­ва­тель­ность на­ту­раль­ных чисел. Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство её не­пре­рыв­ных под­по­сле­до­ва­тель­но­стей, сумма эле­мен­тов ко­то­рых крат­на 999.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число. Га­ран­ти­ру­ет­ся, что общая сумма всех чисел и число в от­ве­те не пре­вы­ша­ют 2 · 10⁹ по аб­со­лют­ной ве­ли­чи­не.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой суммы для файла A, затем для файла B.

Ответ:

У ме­ди­цин­ской ком­па­нии есть N пунк­тов приёма био­ма­те­ри­а­лов на ана­лиз. Все пунк­ты рас­по­ло­же­ны вдоль ав­то­ма­ги­стра­ли и имеют но­ме­ра, со­от­вет­ству­ю­щие рас­сто­я­нию от ну­ле­вой от­мет­ки до кон­крет­но­го пунк­та. Из­вест­но ко­ли­че­ство про­би­рок, ко­то­рое еже­днев­но при­ни­ма­ют в каж­дом из пунк­тов. Про­бир­ки пе­ре­во­зят в спе­ци­аль­ных транс­пор­ти­ро­воч­ных кон­тей­не­рах вме­сти­мо­стью не более 36 штук. Каж­дый транс­пор­ти­ро­воч­ный кон­тей­нер упа­ко­вы­ва­ет­ся в пунк­те приёма и вскры­ва­ет­ся толь­ко в ла­бо­ра­то­рии.

Сто­и­мость пе­ре­воз­ки био­ма­те­ри­а­лов равна про­из­ве­де­нию рас­сто­я­ния от пунк­та до ла­бо­ра­то­рии на ко­ли­че­ство кон­тей­не­ров с про­бир­ка­ми. Общая сто­и­мость пе­ре­воз­ки за день равна сумме сто­и­мо­стей пе­ре­во­зок из каж­до­го пунк­та в ла­бо­ра­то­рию. Ла­бо­ра­то­рию рас­по­ло­жи­ли в одном из пунк­тов приёма био­ма­те­ри­а­лов таким об­ра­зом, что общая сто­и­мость до­став­ки био­ма­те­ри­а­лов из всех пунк­тов ми­ни­маль­на.

Опре­де­ли­те ми­ни­маль­ную общую сто­и­мость до­став­ки био­ма­те­ри­а­лов из всех пунк­тов приёма в ла­бо­ра­то­рию.

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

Дано два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (1 ≤ N ≤ 10 000 000)  — ко­ли­че­ство пунк­тов приёма био­ма­те­ри­а­лов. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся два числа: номер пунк­та и ко­ли­че­ство про­би­рок в этом пунк­те (все числа на­ту­раль­ные, ко­ли­че­ство про­би­рок в каж­дом пунк­те не пре­вы­ша­ет 1000). Пунк­ты пе­ре­чис­ле­ны в по­ряд­ке их рас­по­ло­же­ния вдоль до­ро­ги, на­чи­ная от ну­ле­вой от­мет­ки.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла B.

При­мер ор­га­ни­за­ции ис­ход­ных дан­ных во вход­ном файле:

6

1 100

2 200

5 4

7 3

8 2

10 190

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

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

Дана по­сле­до­ва­тель­ность на­ту­раль­ных чисел. Назовём парой любые два числа из по­сле­до­ва­тель­но­сти. Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство пар, в ко­то­рых сумма чисел в паре де­лит­ся без остат­ка на 3, а их про­из­ве­де­ние  — на 1024.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее 40 000. Га­ран­ти­ру­ет­ся, что число в от­ве­те не пре­вы­ша­ет 2 · 10¹⁰.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла ис­ко­мое зна­че­ние для файла A, затем  — для файла B.

Ответ:

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

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее 1 000 000 000. Га­ран­ти­ру­ет­ся, что число в от­ве­те не пре­вы­ша­ет 2 · 10⁹.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла ис­ко­мое ко­ли­че­ство пар для файла A, затем  — для файла B.

Ответ:

Ме­тео­ро­ло­ги­че­ская стан­ция ведёт на­блю­де­ние за ко­ли­че­ством вы­пав­ших осад­ков. По­ка­за­ния за­пи­сы­ва­ют­ся каж­дую ми­ну­ту в те­че­ние N минут.

Опре­де­ля­ет­ся пара из­ме­ре­ний, между ко­то­ры­ми про­шло не менее K минут. Най­ди­те мак­си­маль­ную сумму по­ка­за­ний среди таких пар.

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

Даны два вход­ных файла (A и B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N  — ко­ли­че­ство из­ме­ре­ний, во вто­рой стро­ке K  — ми­ни­маль­ное ко­ли­че­ство минут между ис­ко­мы­ми из­ме­ре­ни­я­ми. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся число: ко­ли­че­ство вы­пав­ших осад­ков.

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла B.

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

Ответ:

Дана по­сле­до­ва­тель­ность на­ту­раль­ных чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

Назовём парой любые два числа из по­сле­до­ва­тель­но­сти, рас­сто­я­ние между ко­то­ры­ми не мень­ше 18. Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство пар, в ко­то­рых сумма чисел в паре де­лит­ся без остат­ка на 8, а их про­из­ве­де­ние  — на 2187.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее 100 000. Га­ран­ти­ру­ет­ся, что число в от­ве­те не пре­вы­ша­ет 2 · 10⁹.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла ис­ко­мое зна­че­ние для файла A, затем  — для файла B.

Ответ:

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

Опре­де­ли­те два таких пе­ре­дан­ных числа, чтобы между мо­мен­та­ми их пе­ре­да­чи про­шло не менее K мин., а их сумма была мак­си­маль­но воз­мож­ной. Ука­жи­те най­ден­ное сум­мар­ное ко­ли­че­ство осад­ков.

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит на­ту­раль­ное число K  — ко­ли­че­ство минут, ко­то­рое долж­но прой­ти между двумя пе­ре­да­ча­ми по­ка­за­ний, а во вто­рой  — ко­ли­че­ство пе­ре­дан­ных по­ка­за­ний N (1 ≤  N ≤ 10 000 000, N > K). В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 100 000, обо­зна­ча­ю­щее ко­ли­че­ство осад­ков за со­от­вет­ству­ю­щую ми­ну­ту.

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла B.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле:

3

5

15

10

200

0

30

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

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

Ответ:

Дана по­сле­до­ва­тель­ность на­ту­раль­ных чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее. Назовём парой любые два числа из по­сле­до­ва­тель­но­сти. Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство пар, в ко­то­рых сумма эле­мен­тов и рас­сто­я­ние между ними имеют рав­ные остат­ки от де­ле­ния на 9.

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

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

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла ис­ко­мое ко­ли­че­ство пар для файла A, затем  — по­след­ние 6 цифр ис­ко­мо­го ко­ли­че­ства пар для файла B.

Ответ:

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

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

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит на­ту­раль­ное число К  — ми­ни­маль­ное ко­ли­че­ство минут, ко­то­рое долж­но прой­ти между мо­мен­та­ми пе­ре­да­ча­ми любых двух из трёх по­ка­за­ний, а во вто­рой  — ко­ли­че­ство пе­ре­дан­ных по­ка­за­ний N (1 ≤  N 10 000 000, N > K). B каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000 000, ко­то­рое обо­зна­ча­ет зна­че­ние силы тока в со­от­вет­ству­ю­щую ми­ну­ту.

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла В.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле:

2

6

15

14

20

23

21

10

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

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

Ответ:

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

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

Пер­вая стро­ка файла со­дер­жит число k  — рас­сто­я­ние между эле­мен­та­ми, вто­рая стро­ка файла со­дер­жит со­дер­жит ко­ли­че­ство эле­мен­тов в файле.

Ответ:

В пер­вых двух стро­ках по­да­ют­ся два на­ту­раль­ных числа: сна­ча­ла N  — ко­ли­че­ство на­ту­раль­ных чисел в по­сле­до­ва­тель­но­сти, затем K  — ми­ни­маль­ное рас­сто­я­ние, до­пу­сти­мое между лю­бы­ми двумя эле­мен­та­ми.

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

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

Ответ:

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

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

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

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

Даны два вход­ных файла (файл А и файл В), каж­дый из ко­то­рых в пер­вой стро­ке вход­ных дан­ных задаётся про­тя­жен­ность до­ро­ги N (1 ≤ N ≤ 10 000), а во вто­рой  — на­ту­раль­ное число К  — ми­ни­маль­но до­пу­сти­мое рас­сто­я­ние (в мет­рах) между двумя от­мет­ка­ми до­ро­ги (N > К).

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

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла В.

Ответ:

Дана по­сле­до­ва­тель­ность целых чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними

равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

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

В от­ве­те за­пи­ши­те най­ден­ную сумму

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1 < 2K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

При­мер вход­но­го файла:

2

6

6

7

8

2

3

5

Из этого файла в со­от­вет­ствии с усло­ви­я­ми можно вы­брать числа 7, 8 и 5. Мак­си­маль­ное рас­сто­я­ние в дан­ном слу­чае равно 4 (между чис­ла­ми 7 и 5). Числа 6, 7 и 8 взять нель­зя, так как мак­си­маль­ное рас­сто­я­ние в этом слу­чае равно 2, а по усло­вию оно долж­но быть не мень­ше 4. В от­ве­те для этого при­ме­ра надо на­пи­сать число 20.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

За­да­ние вы­пол­ня­ет­ся с ис­поль­зо­ва­ни­ем при­ла­га­е­мых фай­лов.

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

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

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

Даны два вход­ных файла (файл А и файл В), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит на­ту­раль­ное число K  — ми­ни­маль­ное ко­ли­че­ство минут, ко­то­рое долж­но прой­ти между  — двумя пе­ре­да­ча­ми по­ка­за­ний, а во вто­рой  — ко­ли­че­ство пе­ре­дан­ных по­ка­за­ний N (1 ≤  N ≤ 10 000 000, N > K). В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно целое число, по мо­ду­лю не пре­вы­ша­ю­щее 100 000, обо­зна­ча­ю­щее чис­ло­вое зна­че­ние за­ря­да ча­стиц в ми­ну­ту.

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

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла B.

Ответ:

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

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

Даны два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит на­ту­раль­ное число K  — ко­ли­че­ство минут, ко­то­рое долж­но прой­ти между двумя пе­ре­да­ча­ми по­ка­за­ний, а во вто­рой  — ко­ли­че­ство пе­ре­дан­ных по­ка­за­ний N (1 ≤ N ≤ 10 000 000, N > K). В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 10 000 000, обо­зна­ча­ю­щее ко­ли­че­ство осад­ков за со­от­вет­ству­ю­щую ми­ну­ту.

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

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла B.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле:

3

5

15

10

200

0

30

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

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

Ответ:

Дана по­сле­до­ва­тель­ность целых чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

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

В от­ве­те за­пи­ши­те най­ден­ную сумму.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1 < 3K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

При­мер вход­но­го файла:

1

5

6

7

8

2

3

Из этого файла в со­от­вет­ствии с усло­ви­я­ми можно вы­брать числа 7, 8 и 3. Мак­си­маль­ное рас­сто­я­ние в дан­ном слу­чае равно 3 (между чис­ла­ми 7 и 3). Числа 6, 7 и 8 взять нель­зя, так как мак­си­маль­ное рас­сто­я­ние в этом слу­чае равно 2, а по усло­вию оно долж­но быть не мень­ше 3. В от­ве­те для этого при­ме­ра надо на­пи­сать число 18.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

Дана по­сле­до­ва­тель­ность целых чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними

равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

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

В от­ве­те за­пи­ши­те най­ден­ную сумму

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1 < 2K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

При­мер вход­но­го файла:

2

6

6

7

8

2

3

5

Из этого файла в со­от­вет­ствии с усло­ви­я­ми можно вы­брать числа 7, 8 и 5. Мак­си­маль­ное рас­сто­я­ние в дан­ном слу­чае равно 4 (между чис­ла­ми 7 и 5). Числа 6, 7 и 8 взять нель­зя, так как мак­си­маль­ное рас­сто­я­ние в этом слу­чае равно 2, а по усло­вию оно долж­но быть не мень­ше 4. В от­ве­те для этого при­ме­ра надо на­пи­сать число 20.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

Дана по­сле­до­ва­тель­ность целых чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

Не­об­хо­ди­мо вы­брать из по­сле­до­ва­тель­но­сти три числа так, чтобы рас­сто­я­ние между ка­ки­ми-⁠то двумя из них было равно 3K, а сумма всех трёх чисел была мак­си­маль­но воз­мож­ной.

За­пи­ши­те в от­ве­те най­ден­ную сумму.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1 < 2K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

При­мер вход­но­го файла.

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1  < 3K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

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

В от­ве­те за­пи­ши­те най­ден­ную сумму.

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число N  — общее ко­ли­че­ство чисел в на­бо­ре. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10⁸.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

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

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

Пер­вая стро­ка вход­но­го файла со­дер­жит число N  — общее ко­ли­че­ство чисел в по­сле­до­ва­тель­но­сти. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее 10⁸.

При­мер.

Дан вход­ной файл:

4

3

5

2

6

Из этого файла надо вы­брать числа 3, 5 и 6, сумма ко­то­рых равна 14.

Вы­брать числа 3, 5 и 2 нель­зя, так как они не об­ра­зу­ют воз­рас­та­ю­щую по­сле­до­ва­тель­ность.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

Для участ­ни­ков ве­ло­гон­ки на каж­дом ки­ло­мет­ре коль­це­вой трас­сы с дву­сто­рон­ним дви­же­ни­ем уста­нов­ле­ны пунк­ты пи­та­ния. Длина коль­це­вой трас­сы равна N ки­ло­мет­ров. Ну­ле­вой и N-⁠й ки­ло­мет­ры трас­сы на­хо­дят­ся в одной точке. Из­вест­но ко­ли­че­ство ком­плек­тов пи­та­ния в каж­дом из пунк­тов на трас­се. В каж­дый пункт ком­плек­ты пи­та­ния до­став­ля­ет от­дель­ный элек­тро­кар. Сто­и­мость до­став­ки пи­та­ния вы­чис­ля­ет­ся как про­из­ве­де­ние ко­ли­че­ства ком­плек­тов пи­та­ния на рас­сто­я­ние от мо­биль­но­го цеха их под­го­тов­ки до пунк­та пи­та­ния спортс­ме­нов на трас­се. Мо­биль­ный цех под­го­тов­ки ком­плек­тов рас­по­ло­жен в одном из пунк­тов пи­та­ния на трас­се таким об­ра­зом, что общая сто­и­мость до­став­ки из цеха во все пунк­ты ми­ни­маль­на.

Опре­де­ли­те ми­ни­маль­ную сум­мар­ную сто­и­мость до­став­ки пи­та­ния для спортс­ме­нов из цеха его под­го­тов­ки в пунк­ты пи­та­ния на трас­се.

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

Дано два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (1 ≤ N ≤ 10 000 000)  — ко­ли­че­ство

пунк­тов пи­та­ния на коль­це­вой трас­се. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся число  — ко­ли­че­ство ком­плек­тов пи­та­ния на пунк­те (все числа на­ту­раль­ные, ко­ли­че­ство ком­плек­тов пи­та­ния на каж­дом пунк­те не пре­вы­ша­ет 1000). Числа ука­за­ны в по­ряд­ке рас­по­ло­же­ния пунк­тов пи­та­ния спортс­ме­нов на трас­се, на­чи­ная с пер­во­го ки­ло­мет­ра.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле:

6

8

20

5

13

7

19

При таких ис­ход­ных дан­ных, если кон­тей­не­ры уста­нов­ле­ны на каж­дом ки­ло­мет­ре ав­то­до­ро­ги, не­об­хо­ди­мо от­крыть центр пе­ре­ра­бот­ки в пунк­те 6. В этом слу­чае сумма транс­порт­ных за­трат со­ста­вит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.

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

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

Ответ:

Пусть S  — по­сле­до­ва­тель­ность из N чисел про­ну­ме­ро­ван­ных под­ряд на­чи­ная с 1. Обо­зна­чим S_i, S_j, S_k три эле­мен­та по­сле­до­ва­тель­но­сти S, где i < j < k. Опре­де­ли­те в по­сле­до­ва­тель­но­сти S три таких числа S_i, S_j, S_k, что S_i > S_j, S_k > S_j и зна­че­ние вы­ра­же­ния (S_i − S_j) + (S_k − S_j) мак­си­маль­но. В от­ве­те ука­жи­те най­ден­ное мак­си­маль­ное зна­че­ние вы­ра­же­ния (S_i − S_j) + (S_k − S_j). Га­ран­ти­ру­ет­ся, что в по­сле­до­ва­тель­но­сти есть три числа S_i, S_j, S_k, удо­вле­тво­ря­ю­щие усло­вию за­да­чи.

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

Дано два вход­ных файла (файл А и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (5 < N <10 000 000)  — ко­ли­че­ство целых чисел. Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно целое число, зна­че­ние ко­то­ро­го по мо­ду­лю не пре­вы­ша­ет 1000. В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла B.

Ответ:

Фраг­мент звёзд­но­го неба спро­еци­ро­ван на плос­кость с де­кар­то­вой си­сте­мой ко­ор­ди­нат. Учёный решил про­ве­сти кла­сте­ри­за­цию по­лу­чен­ных точек, яв­ля­ю­щих­ся изоб­ра­же­ни­я­ми звёзд, то есть раз­бить их мно­же­ство на N не­пе­ре­се­ка­ю­щих­ся не­пу­стых под­мно­жеств (кла­сте­ров), таких что точки каж­до­го под­мно­же­ства лежат внут­ри пря­мо­уголь­ни­ка со сто­ро­на­ми дли­ной H и W, причём эти пря­мо­уголь­ни­ки между собой не пе­ре­се­ка­ют­ся. Сто­ро­ны пря­мо­уголь­ни­ков не обя­за­тель­но па­рал­лель­ны ко­ор­ди­нат­ным осям.

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

Га­ран­ти­ру­ет­ся, что во всех кла­сте­рах ко­ли­че­ство точек раз­лич­но.

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

Спек­траль­ный класс звез­ды опре­де­ля­ет­ся в со­от­вет­ствии с таб­ли­цей:

Класс све­ти­мо­сти звез­ды опре­де­ля­ет­ся в со­от­вет­ствии с таб­ли­цей:

Будем на­зы­вать цен­тром кла­сте­ра точку этого кла­сте­ра, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных точек кла­сте­ра ми­ни­маль­на. Для каж­до­го кла­сте­ра га­ран­ти­ру­ет­ся един­ствен­ность его цен­тра. Рас­сто­я­ние между двумя точ­ка­ми на плос­ко­сти А(х₁, y₁) и B(х₂, y₂) вы­чис­ля­ет­ся по фор­му­ле:

В файле А хра­нят­ся дан­ные о звёздах двух кла­сте­ров, где Н  =  5 и W  =  4 для каж­до­го кла­сте­ра. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция одной звез­ды: ко­ор­ди­на­та х, ко­ор­ди­на­та у и её ха­рак­те­ри­сти­ка. Зна­че­ния даны в услов­ных еди­ни­цах. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 1000.

В файле Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров, где Н  =  3 и W  =  5 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 10 000.

Струк­ту­ра хра­не­ния ин­фор­ма­ции о звёздах в файле Б ана­ло­гич­на струк­ту­ре в файле А.

Для файла А опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: A₁  — абс­цис­су бли­жай­ше­го бе­ло­го ги­ган­та к цен­тру кла­сте­ра с наи­мень­шим ко­ли­че­ством точек, и A₂  — ор­ди­на­ту бли­жай­ше­го бе­ло­го ги­ган­та к цен­тру кла­сте­ра с наи­мень­шим ко­ли­че­ством точек.

Для файла Б опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: B₁  — рас­сто­я­ние между цен­тра­ми кла­сте­ров с наи­боль­шим и наи­мень­шим ко­ли­че­ством крас­ных сверх­ги­ган­тов, и B₂  — мак­си­маль­ное рас­сто­я­ние между двумя жёлтыми кар­ли­ка­ми, на­хо­дя­щи­ми­ся в одном кла­сте­ре.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния A₁ × 10 000, затем целую часть про­из­ве­де­ния A₂ × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния B₁ × 10 000, затем целую часть про­из­ве­де­ния B₂ × 10 000.

Ответ:

Фраг­мент звёзд­но­го неба спро­еци­ро­ван на плос­кость с де­кар­то­вой си­сте­мой ко­ор­ди­нат. Учёный решил про­ве­сти кла­сте­ри­за­цию по­лу­чен­ных точек, яв­ля­ю­щих­ся изоб­ра­же­ни­я­ми звёзд, то есть раз­бить их мно­же­ство на N не­пе­ре­се­ка­ю­щих­ся не­пу­стых под­мно­жеств (кла­сте­ров), таких что точки каж­до­го под­мно­же­ства лежат внут­ри пря­мо­уголь­ни­ка со сто­ро­на­ми дли­ной H и W, причём эти пря­мо­уголь­ни­ки между собой не пе­ре­се­ка­ют­ся. Сто­ро­ны пря­мо­уголь­ни­ков не обя­за­тель­но па­рал­лель­ны ко­ор­ди­нат­ным осям.

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

Га­ран­ти­ру­ет­ся, что во всех кла­сте­рах ко­ли­че­ство точек раз­лич­но.

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

Спек­траль­ный класс звез­ды опре­де­ля­ет­ся в со­от­вет­ствии с таб­ли­цей:

Класс све­ти­мо­сти звез­ды опре­де­ля­ет­ся в со­от­вет­ствии с таб­ли­цей:

Будем на­зы­вать цен­тром кла­сте­ра точку этого кла­сте­ра, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных точек кла­сте­ра ми­ни­маль­на. Для каж­до­го кла­сте­ра га­ран­ти­ру­ет­ся един­ствен­ность его цен­тра. Рас­сто­я­ние между двумя точ­ка­ми на плос­ко­сти А(х₁, y₁) и B(х₂, y₂) вы­чис­ля­ет­ся по фор­му­ле:

В файле А хра­нят­ся дан­ные о звёздах двух кла­сте­ров, где Н  =  5 и W  =  4 для каж­до­го кла­сте­ра. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция одной звез­ды: ко­ор­ди­на­та х, ко­ор­ди­на­та у и её ха­рак­те­ри­сти­ка. Зна­че­ния даны в услов­ных еди­ни­цах. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 1000.

В файле Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров, где Н  =  3 и W  =  5 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 10 000.

Струк­ту­ра хра­не­ния ин­фор­ма­ции о звёздах в файле Б ана­ло­гич­на струк­ту­ре в файле А.

Для файла А опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: A₁  — абс­цис­су бли­жай­ше­го жёлтого ги­ган­та к цен­тру кла­сте­ра с наи­боль­шим ко­ли­че­ством точек, и A₂  — ор­ди­на­ту бли­жай­ше­го жёлтого ги­ган­та к цен­тру кла­сте­ра с наи­боль­шим ко­ли­че­ством точек.

Для файла Б опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: B₁  — рас­сто­я­ние между цен­тра­ми кла­сте­ров с наи­боль­шим и наи­мень­шим ко­ли­че­ством белых сверх­ги­ган­тов, и B₂  — мак­си­маль­ное рас­сто­я­ние между двумя го­лу­бы­ми кар­ли­ка­ми, на­хо­дя­щи­ми­ся в одном кла­сте­ре.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния A₁ × 10 000, затем целую часть про­из­ве­де­ния A₂ × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния B₁ × 10 000, затем целую часть про­из­ве­де­ния B₂ × 10 000.

Ответ:

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

В файле А хра­нят­ся дан­ные о звёздах 2-⁠х кла­сте­ров, в файле Б хра­нят­ся дан­ные о звёздах 3-⁠х кла­сте­ров. Для каж­дой звез­ды дана ха­рак­те­ри­сти­ка: тип цвета, тип све­ти­мо­сти и её раз­мер в со­от­вет­ствии с таб­ли­цей.

По­лу­чен­ные зна­че­ния за­пи­са­ны в ха­рак­те­ри­сти­ке слит­но: обо­зна­че­ние цвета, све­ти­мость (обо­зна­ча­ет­ся циф­рой 1–⁠9) и обо­зна­че­ние раз­ме­ра (рим­ские цифры).

Рас­сто­я­ние между двумя точ­ка­ми A(x₁; y₁) и B(x₂; y₂) вы­чис­ля­ет­ся по фор­му­ле:

Даны два вход­ных файла (файл А и файл Б). Для файла А опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: A₁  — ми­ни­маль­ное рас­сто­я­ние от цен­тра кла­сте­ра с наи­мень­шим ко­ли­че­ством точек до крас­но­го ги­ган­та, и A₂  — мак­си­маль­ное рас­сто­я­ние от цен­тра кла­сте­ра с наи­мень­шим ко­ли­че­ством точек до крас­но­го ги­ган­та.

Для файла Б опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: B₁  — ми­ни­маль­ное рас­сто­я­ние между двумя раз­лич­ны­ми жёлтыми кар­ли­ка­ми, рас­по­ло­жен­ны­ми в одном и том же кла­сте­ре, и B₂  — рас­сто­я­ние между цен­тра­ми кла­сте­ров с ми­ни­маль­ным и мак­си­маль­ным ко­ли­че­ством жёлтых кар­ли­ков.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — целую часть про­из­ве­де­ния A₁ × 10 000, затем целую часть про­из­ве­де­ния A₂ × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния B₁ × 10 000, затем целую часть про­из­ве­де­ния B₂ × 10 000.

Ответ:

Фраг­мент звёзд­но­го неба спро­еци­ро­ван на плос­кость с де­кар­то­вой си­сте­мой ко­ор­ди­нат. Учёный решил про­ве­сти кла­сте­ри­за­цию по­лу­чен­ных точек, яв­ля­ю­щих­ся изоб­ра­же­ни­я­ми звёзд, то есть раз­бить их мно­же­ство на не­пе­ре­се­ка­ю­щих­ся не­пу­стых под­мно­жеств (кла­сте­ров), таких что точки каж­до­го под­мно­же­ства лежат внут­ри пря­мо­уголь­ни­ка со сто­ро­на­ми дли­ной H и W ,причём эти пря­мо­уголь­ни­ки между собой не пе­ре­се­ка­ют­ся. Сто­ро­ны пря­мо­уголь­ни­ков не обя­за­тель­но па­рал­лель­ны ко­ор­ди­нат­ным осям. Га­ран­ти­ру­ет­ся, что такое раз­би­е­ние су­ще­ству­ет и един­ствен­но.

Для каж­дой звез­ды дана ха­рак­те­ри­сти­ка: тип цвета, тип све­ти­мо­сти и её раз­мер в со­от­вет­ствии с таб­ли­цей.

По­лу­чен­ные зна­че­ния за­пи­са­ны в ха­рак­те­ри­сти­ке слит­но: обо­зна­че­ние цвета, све­ти­мость (араб­ская цифра) и обо­зна­че­ние раз­ме­ра.

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

В файле А хра­нят­ся дан­ные о звёздах двух кла­сте­ров, где H  =  6,5, W  =  4,5 для каж­до­го кла­сте­ра. В каж­дой стро­ке за­пи­са­на ко­ор­ди­на­та x, затем ко­ор­ди­на­та y, а затем её ха­рак­те­ри­сти­ка.

Опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра для файла А, затем най­ди­те два числа: A_x  — абс­цис­са бли­жай­ше­го к цен­т­ро­и­ду жел­то­го кар­ли­ка, кла­сте­ра с наи­боль­шим ко­ли­че­ством звёзд, и A_y  — ор­ди­на­та бли­жай­ше­го к цен­т­ро­и­ду жел­то­го кар­ли­ка, кла­сте­ра с наи­боль­шим ко­ли­че­ством звёзд.

В от­ве­те ука­жи­те целые части про­из­ве­де­ний A₁ × 10 000 и A₂ × 10 000.

Ответ: