На ри­сун­ке спра­ва схема дорог Н-⁠ского рай­о­на изоб­ра­же­на в виде графа, в таб­ли­це со­дер­жат­ся све­де­ния о дли­нах этих дорог (в ки­ло­мет­рах).

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те длину до­ро­ги из пунк­та Г в пункт Е. В от­ве­те за­пи­ши­те целое число.

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем (z ∧ y) ∨ ((x → z ) ≡ (y → w)).

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

Опре­де­ли­те, ка­ко­му столб­цу таб­ли­цы ис­тин­но­сти со­от­вет­ству­ет каж­дая из пе­ре­мен­ных x, y, z, w.

В от­ве­те на­пи­ши­те буквы x, y, z, w в том по­ряд­ке, в ко­то­ром идут со­от­вет­ству­ю­щие им столб­цы (сна­ча­ла  — буква, со­от­вет­ству­ю­щая пер­во­му столб­цу; затем  — буква, со­от­вет­ству­ю­щая вто­ро­му столб­цу, и т. д.). Буквы в от­ве­те пи­ши­те под­ряд, ни­ка­ких раз­де­ли­те­лей между бук­ва­ми ста­вить не нужно.

При­мер. Пусть за­да­но вы­ра­же­ние x → y, за­ви­ся­щее от двух пе­ре­мен­ных x и y, и фраг­мент таб­ли­цы ис­тин­но­сти:

Тогда пер­во­му столб­цу со­от­вет­ству­ет пе­ре­мен­ная y, а вто­ро­му столб­цу со­от­вет­ству­ет пе­ре­мен­ная x. В от­ве­те нужно на­пи­сать: yx.

В файле при­ведён фраг­мент базы дан­ных «Про­дук­ты», со­дер­жа­щей ин­фор­ма­цию о по­став­ках то­ва­ров и их про­да­же. База дан­ных со­сто­ит из трёх таб­лиц.

Таб­ли­ца «Дви­же­ние то­ва­ров» со­дер­жит за­пи­си о по­став­ках то­ва­ров в ма­га­зи­ны го­ро­да в пер­вой де­ка­де июня 2021 г. и о про­да­же то­ва­ров в этот же пе­ри­од. Таб­ли­ца «Товар» со­дер­жит дан­ные о то­ва­рах. Таб­ли­ца «Ма­га­зин» со­дер­жит ад­ре­са ма­га­зи­нов.

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

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

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв И, К, Л, М, Н, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы Н ис­поль­зо­ва­ли ко­до­вое слово 0, для буквы К  — ко­до­вое слово 10. Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех пяти ко­до­вых слов?

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

Ав­то­мат по­лу­ча­ет на вход четырёхзнач­ное число (число не может на­чи­нать­ся с нуля). По этому числу стро­ит­ся новое число по сле­ду­ю­щим пра­ви­лам.

1.  Скла­ды­ва­ют­ся от­дель­но пер­вая и вто­рая, вто­рая и тре­тья, тре­тья и четвёртая цифры за­дан­но­го числа.

2.  Наи­мень­шая из по­лу­чен­ных трёх сумм уда­ля­ет­ся.

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

При­мер. Ис­ход­ное число: 1984. Суммы: 1 + 9  =  10, 9 + 8  =  17, 8 + 4  =  12. Уда­ля­ет­ся 10. Ре­зуль­тат: 1217.

Ука­жи­те наи­боль­шее число, при об­ра­бот­ке ко­то­ро­го ав­то­мат выдаёт ре­зуль­тат 613.

При­ме­ча­ние. Если мень­шие из трех сумм равны, то от­бра­сы­ва­ют одну из них.

Ис­пол­ни­тель Че­ре­па­ха дей­ству­ет на плос­ко­сти с де­кар­то­вой си­сте­мой ко­ор­ди­нат. В на­чаль­ный мо­мент Че­ре­па­ха на­хо­дит­ся в на­ча­ле ко­ор­ди­нат, её го­ло­ва на­прав­ле­на вдоль по­ло­жи­тель­но­го на­прав­ле­ния оси ор­ди­нат, хвост опу­щен. При опу­щен­ном хво­сте Че­ре­па­ха остав­ля­ет на поле след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его дви­же­ния. У ис­пол­ни­те­ля су­ще­ству­ет две ко­ман­ды: Вперёд n (где n  — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Че­ре­па­хи на n еди­ниц в том на­прав­ле­нии, куда ука­зы­ва­ет её го­ло­ва, и На­пра­во m (где m  — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрел­ке. За­пись По­вто­ри k [Ко­ман­да1 Ко­ман­да2 … Ко­ман­даS] озна­ча­ет, что по­сле­до­ва­тель­ность из S ко­манд по­вто­рит­ся k раз. Че­ре­па­хе был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм:

По­вто­ри 4 [Вперёд 12 На­пра­во 90]

На­пра­во 30

По­вто­ри 3 [Вперёд 8 На­пра­во 60 Вперёд 8 На­пра­во 120].

Опре­де­ли­те, сколь­ко точек с це­ло­чис­лен­ны­ми ко­ор­ди­на­та­ми будут на­хо­дить­ся внут­ри об­ла­сти, огра­ни­чен­ной ли­ни­ей, за­дан­ной дан­ным ал­го­рит­мом: По­вто­ри 4 [Вперёд 12 На­пра­во 90].

и на­хо­дить­ся вне об­ла­сти, огра­ни­чен­ной ли­ни­ей, за­дан­ной дан­ным ал­го­рит­мом: По­вто­ри 3 [Вперёд 8 На­пра­во 60 Вперёд 8 На­пра­во 120]. Точки на линии учи­ты­вать не сле­ду­ет.

Какой ми­ни­маль­ный объём па­мя­ти (в Кбайт) нужно за­ре­зер­ви­ро­вать, чтобы можно было со­хра­нить любое раст­ро­вое изоб­ра­же­ние раз­ме­ром 128 × 128 пик­се­лей при усло­вии, что в изоб­ра­же­нии могут ис­поль­зо­вать­ся 256 раз­лич­ных цве­тов? В от­ве­те за­пи­ши­те толь­ко целое число, еди­ни­цу из­ме­ре­ния пи­сать не нужно.

Все 5-⁠бук­вен­ные слова, со­став­лен­ные из букв А, О, У, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке. Вот на­ча­ло спис­ка:

1.  ААААА

2.  ААААО

3.  ААААУ

4.  АААОА

……

За­пи­ши­те слово, ко­то­рое стоит на 210-⁠м месте от на­ча­ла спис­ка.

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

Опре­де­ли­те, сколь­ко раз в тек­сте про­из­ве­де­ния А. С. Пуш­ки­на «Ка­пи­тан­ская дочка» встре­ча­ет­ся слово «ка­пи­тан­ская» или «Ка­пи­тан­ская». Дру­гие формы этого слова («ка­пи­тан­скую», «ка­пи­тан­ские» и т. д.) учи­ты­вать не надо.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 23 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы A, F, G, Y, S, L (таким об­ра­зом, ис­поль­зу­ет­ся 6 раз­лич­ных сим­во­лов). Каж­дый такой па­роль в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит). Опре­де­ли­те объём па­мя­ти в бай­тах, от­во­ди­мый этой про­грам­мой для за­пи­си 50 па­ро­лей. В от­ве­те ука­жи­те толь­ко число, слово «байт» пи­сать не нужно.

Ис­пол­ни­тель Ре­дак­тор по­лу­ча­ет на вход стро­ку цифр и пре­об­ра­зу­ет её. Ре­дак­тор может вы­пол­нять две ко­ман­ды, в обеих ко­ман­дах v и w обо­зна­ча­ют це­поч­ки цифр.

А)  за­ме­нить (v, w).

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды за­ме­нить (111, 27) пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150.

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

Б)  на­шлось (v).

Эта ко­ман­да про­ве­ря­ет, встре­ча­ет­ся ли це­поч­ка v в стро­ке ис­пол­ни­те­ля Ре­дак­тор. Если она встре­ча­ет­ся, то ко­ман­да воз­вра­ща­ет ло­ги­че­ское зна­че­ние «ис­ти­на», в про­тив­ном слу­чае воз­вра­ща­ет зна­че­ние «ложь». Стро­ка ис­пол­ни­те­ля при этом не из­ме­ня­ет­ся.

Цикл

ПОКА усло­вие

    по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

Какая стро­ка по­лу­чит­ся в ре­зуль­та­те при­ме­не­ния при­ведённой ниже про­грам­мы к стро­ке, со­сто­я­щей из 77 еди­ниц?

НА­ЧА­ЛО

    ПОКА на­шлось (11111)

        за­ме­нить (222, 1)

        за­ме­нить (111, 2)

    КОНЕЦ ПОКА

КОНЕЦ

В тер­ми­но­ло­гии сетей TCP/⁠IP мас­кой сети на­зы­ва­ет­ся дво­ич­ное число, опре­де­ля­ю­щее, какая часть IP-⁠ад­ре­са узла сети от­но­сит­ся к ад­ре­су сети, а какая  — к ад­ре­су са­мо­го узла в этой сети. При этом в маске сна­ча­ла (в стар­ших раз­ря­дах) стоят еди­ни­цы, а затем с не­ко­то­ро­го места  — нули. Обыч­но маска за­пи­сы­ва­ет­ся по тем же пра­ви­лам, что и IP-⁠адрес,  — в виде четырёх бай­тов, причём каж­дый байт за­пи­сы­ва­ет­ся в виде де­ся­тич­но­го числа. Адрес сети по­лу­ча­ет­ся в ре­зуль­та­те при­ме­не­ния по­раз­ряд­ной конъ­юнк­ции к за­дан­но­му IP-⁠ад­ре­су узла и маске.

На­при­мер, если IP-⁠адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-⁠ад­ре­сом 93.138.164.49 адрес сети равен 93.138.160.0. Для сколь­ких раз­лич­ных зна­че­ний маски это воз­мож­но?

Зна­че­ние вы­ра­же­ния 343⁵ + 343⁴ + 49⁶ − 7¹³ − 21 за­пи­са­ли в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 7. Сколь­ко раз­лич­ных цифр со­дер­жит эта за­пись?

При­мер. За­пись 122233₇ со­дер­жит три раз­лич­ные цифры: 1, 2 и 3.

Для ка­ко­го наи­мень­ше­го це­ло­го не­от­ри­ца­тель­но­го числа А вы­ра­же­ние

тож­де­ствен­но ис­тин­но, то есть при­ни­ма­ет зна­че­ние 1 при любых целых не­от­ри­ца­тель­ных x и y?

Обо­зна­чим через mod(a, b) оста­ток от де­ле­ния на­ту­раль­но­го числа a на на­ту­раль­ное число b. Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n  — целое не­от­ри­ца­тель­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:

F(0)  =  0;

F(n)  =  F(n / 3), если n > 0 и при этом mod(n, 3)  =  0;

F(n)  =  mod(n, 3) + F(n − mod(n, 3)), если mod(n, 3) > 0.

На­зо­ви­те ми­ни­маль­ное зна­че­ние n, для ко­то­ро­го F(n)  =  9.

В файле со­дер­жит­ся по­сле­до­ва­тель­ность из 10 000 целых по­ло­жи­тель­ных чисел. Каж­дое число не пре­вы­ша­ет 10 000. Опре­де­ли­те и за­пи­ши­те в от­ве­те сна­ча­ла ко­ли­че­ство пар эле­мен­тов по­сле­до­ва­тель­но­сти, у ко­то­рых сумма нечётна, а про­из­ве­де­ние де­лит­ся на 5, затем мак­си­маль­ную из сумм эле­мен­тов таких пар. В дан­ной за­да­че под парой под­ра­зу­ме­ва­ет­ся два раз­лич­ных эле­мен­та по­сле­до­ва­тель­но­сти. По­ря­док эле­мен­тов в паре не важен.

Ответ:

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

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це.

При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

Для ука­зан­ных вход­ных дан­ных оп­ти­маль­ным марш­ру­том будет путь по клет­кам 44, 42, 89, 50, 26, 70, 85. Ито­го­вая сумма равна 44 + 89 + 70 + 85  =  288. Числа 42, 50 и 26 не вклю­ча­ют­ся в сумму, так как 42 < 44, 50 < 89 и 26 < 50.

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в че­ты­ре раза. На­при­мер, пусть в одной куче 6 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (6, 9). За один ход из по­зи­ции (6, 9) можно по­лу­чить любую из четырёх по­зи­ций: (7, 9), (24, 9), (6, 10), (6, 36). Чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было 3 камня, во вто­рой куче  — S кам­ней, 1 ≤ S ≤ 57.

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

Из­вест­но, что Ваня вы­иг­рал своим пер­вым ходом после не­удач­но­го пер­во­го хода Пети. Ука­жи­те ми­ни­маль­ное зна­че­ние S, когда такая си­ту­а­ция воз­мож­на.

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в че­ты­ре раза. На­при­мер, пусть в одной куче 6 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (6, 9). За один ход из по­зи­ции (6, 9) можно по­лу­чить любую из четырёх по­зи­ций: (7, 9), (24, 9), (6, 10), (6, 36). Чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было 3 камня, во вто­рой куче  — S кам­ней, 1 ≤ S ≤ 57.

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

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

—  Петя не может вы­иг­рать за один ход;

—  Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в че­ты­ре раза. На­при­мер, пусть в одной куче 6 кам­ней, а в дру­гой  — 9 кам­ней; такую по­зи­цию мы будем обо­зна­чать (6, 9). За один ход из по­зи­ции (6, 9) можно по­лу­чить любую из четырёх по­зи­ций: (7, 9), (24, 9), (6, 10), (6, 36). Чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было 3 камня, во вто­рой куче  — S кам­ней, 1 ≤ S ≤ 57.

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

Най­ди­те ми­ни­маль­ное зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

—  у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

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

В ком­пью­тер­ной си­сте­ме не­об­хо­ди­мо вы­пол­нить не­ко­то­рое ко­ли­че­ство вы­чис­ли­тель­ных про­цес­сов, ко­то­рые могут вы­пол­нять­ся па­рал­лель­но или по­сле­до­ва­тель­но. Для за­пус­ка не­ко­то­рых про­цес­сов не­об­хо­ди­мы дан­ные, ко­то­рые по­лу­ча­ют­ся как ре­зуль­та­ты вы­пол­не­ния од­но­го или двух дру­гих про­цес­сов  — по­став­щи­ков дан­ных. Не­за­ви­си­мые про­цес­сы (не име­ю­щие по­став­щи­ков дан­ных) можно за­пус­кать в любой мо­мент вре­ме­ни. Если про­цесс B (за­ви­си­мый про­цесс) по­лу­ча­ет дан­ные от про­цес­са A (по­став­щи­ка дан­ных), то про­цесс B может на­чать вы­пол­не­ние не рань­ше чем через 5 мс после за­вер­ше­ния про­цес­са A. Любые про­цес­сы, го­то­вые к вы­пол­не­нию, можно за­пус­кать па­рал­лель­но, при этом ко­ли­че­ство од­но­вре­мен­но вы­пол­ня­е­мых про­цес­сов может быть любым, дли­тель­ность про­цес­са не за­ви­сит от дру­гих па­рал­лель­но вы­пол­ня­е­мых про­цес­сов.

В таб­ли­це пред­став­ле­ны иден­ти­фи­ка­тор (ID) каж­до­го про­цес­са, его дли­тель­ность и ID по­став­щи­ков дан­ных для за­ви­си­мых про­цес­сов.

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

Ис­пол­ни­тель А22 пре­об­ра­зу­ет целое число, за­пи­сан­ное на экра­не.

У ис­пол­ни­те­ля три ко­ман­ды, каж­дой ко­ман­де при­сво­ен номер.

1.  При­бавь 1.

2.  При­бавь 3.

3.  При­бавь преды­ду­щее.

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет это число на 3, тре­тья при­бав­ля­ет к числу на экра­не число, мень­шее на 1 (к числу 3 при­бав­ля­ет­ся 2, к числу 11 при­бав­ля­ет­ся 10 и так далее). Про­грам­ма для ис­пол­ни­те­ля А22  — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 10?

Тек­сто­вый файл со­сто­ит не более, чем из 10⁷ строч­ных букв ан­глий­ско­го ал­фа­ви­та. Най­ди­те мак­си­маль­ную длину под­стро­ки, в ко­то­рой сим­во­лы a и d не стоят рядом.

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

На­пи­ши­те про­грам­му, ко­то­рая ищет среди целых чисел, при­над­ле­жа­щих чис­ло­во­му от­рез­ку [185 311; 185 330], числа, име­ю­щие ровно че­ты­ре раз­лич­ных на­ту­раль­ных де­ли­те­ля. Для каж­до­го най­ден­но­го числа за­пи­ши­те эти че­ты­ре де­ли­те­ля в че­ты­ре со­сед­них столб­ца на экра­не с новой стро­ки. Де­ли­те­ли в стро­ке долж­ны сле­до­вать в по­ряд­ке воз­рас­та­ния.

На­при­мер, в диа­па­зо­не [12; 14] ровно че­ты­ре раз­лич­ных на­ту­раль­ных де­ли­те­ля имеет число 14, по­это­му для этого диа­па­зо­на вывод на экра­не долж­на со­дер­жать сле­ду­ю­щие зна­че­ния:

1 2 7 14

Ответ:

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

1.  Нужно ку­пить как можно боль­ше из­де­лий, не­за­ви­си­мо от их типа и мо­ди­фи­ка­ции.

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

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

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

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

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

В от­ве­те за­пи­ши­те два целых числа: сна­ча­ла ко­ли­че­ство за­куп­лен­ных из­де­лий типа B, затем остав­шу­ю­ся не­ис­поль­зо­ван­ной сумму денег.

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

6 130

30 A

50 A

60 B

20 B

70 B

10 A

В дан­ном слу­чае можно ку­пить не более 4 из­де­лий, из них не более 2 из­де­лий B. Ми­ни­маль­ная цена такой по­куп­ки 120 руб­лей (по­ку­па­ем из­де­лия 30A, 60B, 20B, 10A). Оста­нет­ся 10 руб­лей. В от­ве­те надо за­пи­сать числа 2 и 10.

Ответ:

Дана по­сле­до­ва­тель­ность 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 встре­ча­ет­ся в ис­ход­ной по­сле­до­ва­тель­но­сти два­жды.