На ри­сун­ке схема дорог Н-⁠ского рай­о­на изоб­ра­же­на в виде графа. Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те, какие но­ме­ра в таб­ли­це со­от­вет­ству­ют населённым пунк­там D и F. В от­ве­те за­пи­ши­те 2 числа в по­ряд­ке воз­рас­та­ния.

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем:

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

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: А, Б, В, Г, Д, Е, Ж и З. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: А  — 011, Б  — 10, В  — 110, Г  — 111.

Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния остав­ших­ся букв?

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: А, Б, В, Г, Д, Е, Ж и З. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: В  — 000, Г  —011, Д  — 1000, Е  — 1001, Ж  — 110 и З  — 1111.

Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния остав­ших­ся букв?

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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко во­семь букв: А, Б, В, Г, Д, Е, Ж и З. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: А  — 011, Б  — 10, В  — 110, Г  — 111.

Какое наи­мень­шее ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния остав­ших­ся букв?

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

На вход ал­го­рит­ма подаётся на­ту­раль­ное число N. Ал­го­ритм стро­ит по нему новое число R сле­ду­ю­щим об­ра­зом.

1.  Стро­ит­ся дво­ич­ная за­пись числа N.

2.  Далее эта за­пись об­ра­ба­ты­ва­ет­ся по сле­ду­ю­ще­му пра­ви­лу:

а)  если число N де­лит­ся на 3, то в этой за­пи­си до­пи­сы­ва­ют­ся спра­ва три по­след­ние дво­ич­ные цифры;

6)  если число N на 3 не де­лит­ся, то оста­ток от де­ле­ния умно­жа­ет­ся на 3, пе­ре­во­дит­ся в дво­ич­ную за­пись и до­пи­сы­ва­ет­ся в конец числа.

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

3.  Ре­зуль­тат пе­ре­во­дит­ся в де­ся­тич­ную си­сте­му и вы­во­дит­ся на экран.

На­при­мер, для ис­ход­но­го числа 12  =  1100₂ ре­зуль­та­том яв­ля­ет­ся число 1100100₂  =  100, а для ис­ход­но­го числа 4  =  100₂ ре­зуль­та­том яв­ля­ет­ся число 10011₂  =  19.

Ука­жи­те мак­си­маль­ное число R, не пре­вы­ша­ю­щее 137, ко­то­рое может быть по­лу­че­но с по­мо­щью опи­сан­но­го ал­го­рит­ма. В от­ве­те за­пи­ши­те это число в де­ся­тич­ной си­сте­ме счис­ле­ния.

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

Че­ре­па­хе был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм:

По­вто­ри 2 [Вперёд 3 На­ле­во 90 Назад 10 На­ле­во 90]

Под­нять хвост

Назад 10 На­пра­во 90 Впе­ред 8 На­ле­во 90

Опу­стить хвост

По­вто­ри 2 [Вперёд 16 На­пра­во 90 Вперёд 8 На­пра­во 90].

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

Сколь­ко се­кунд по­тре­бу­ет­ся мо­де­му, пе­ре­да­ю­ще­му со­об­ще­ния со ско­ро­стью 15 872 бит/⁠с, чтобы пе­ре­дать цвет­ное раст­ро­вое изоб­ра­же­ние раз­ме­ром 1023 × 768 пик­се­лей, при усло­вии, что цвет каж­до­го пик­се­ля ко­ди­ру­ет­ся 3 бай­та­ми.

Сколь­ко су­ще­ству­ет чисел, вось­ме­рич­ная за­пись ко­то­рых со­дер­жит 5 цифр, при­чем в за­пи­си нет цифры 1. Также все цифры за­пи­си раз­лич­ны и ни­ка­кие две чётные и две нечётные цифры не стоят рядом.

Опре­де­ли­те ко­ли­че­ство че­ты­рех­знач­ных чисел, за­пи­сан­ных в де­ся­тич­ной си­сте­ме счис­ле­ния, в за­пи­си ко­то­рых все цифры раз­лич­ны и ни­ка­кие две чётные и две нечётные цифры не стоят рядом.

Алиса со­став­ля­ет 6-⁠бук­вен­ные слова из букв М, А, Н, Г, У, С, Т. Каж­дая из букв может встре­чать­ся сколь­ко угод­но раз, причём пер­вой бук­вой не может быть А, буква У долж­на встре­чать­ся не менее 1 раза. Также в за­пи­си долж­ны быть ровно две буквы М.

Сколь­ко раз­лич­ных слов может со­ста­вить Алиса?

Ев­ге­ний со­став­ля­ет 6-⁠бук­вен­ные слова из букв М, У, Ж, Ч, И, Н, А. Каж­дая из букв может встре­чать­ся в слове ровно один раз, причём пер­вой бук­вой не может быть Ч, буква Ж долж­на встре­чать­ся не менее 1 раза и номер слова дол­жен быть нечётный.

Сколь­ко раз­лич­ных слов может со­ста­вить Ев­ге­ний?

Все 5-бук­вен­ные слова, в со­ста­ве ко­то­рых могут быть буквы А, Л, Г, О, Р, И, Т, М, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны на­чи­ная с 1.

Ниже при­ве­де­но на­ча­ло спис­ка.

ААААА

ААААГ

ААААИ

ААААЛ

ААААМ

ААААО

ААААР

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

Сколь­ко су­ще­ству­ет де­ся­тич­ных чисел, ко­то­рые де­лят­ся на 5, при усло­вии что все цифры числа раз­лич­ные?

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

—  среди семи чисел сов­па­да­ют ровно че­ты­ре числа;

—  сред­нее зна­че­ние не­по­вто­ря­ю­щих­ся чисел боль­ше суммы по­вто­ря­ю­щих­ся чисел.

В от­ве­те за­пи­ши­те толь­ко число.

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

—  среди семи чисел сов­па­да­ют ровно че­ты­ре числа;

—  сред­нее зна­че­ние по­вто­ря­ю­щих­ся чисел боль­ше, чем сред­нее ариф­ме­ти­че­ское не­по­вто­ря­ю­щих­ся чисел стро­ки.

В от­ве­те за­пи­ши­те толь­ко число.

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

—  среди семи чисел сов­па­да­ют ровно че­ты­ре числа;

—  сред­нее зна­че­ние по­вто­ря­ю­щих­ся чисел стро­го мень­ше, чем сред­нее ариф­ме­ти­че­ское ВСЕХ чисел стро­ки.

В от­ве­те за­пи­ши­те толь­ко число.

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз в тек­сте книги А. И. Куп­ри­на «Гра­на­то­вый брас­лет», встре­ча­ет­ся слово «шаг» или «Шаг». Учи­ты­ва­ют­ся толь­ко те слова, ко­то­рые вхо­дят в со­став дру­го­го слова, но не как са­мо­сто­я­тель­ное слово.

Слова в снос­ках учи­ты­вать не сле­ду­ет. В от­ве­те ука­жи­те толь­ко число.

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз в тек­сте книги А. И. Куп­ри­на «Гра­на­то­вый брас­лет», встре­ча­ет­ся слово «мой» или «Мой». Учи­ты­ва­ют­ся толь­ко те слова, ко­то­рые вхо­дят в со­став дру­го­го слова, но не как са­мо­сто­я­тель­ное слово.

В от­ве­те ука­жи­те толь­ко число.

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз в тек­сте книги А. И. Куп­ри­на «Гра­на­то­вый брас­лет», встре­ча­ет­ся слово «пост» или «Пост». Учи­ты­ва­ют­ся толь­ко те слова, ко­то­рые вхо­дят в со­став дру­го­го слова, но не как са­мо­сто­я­тель­ное слово.

Слова в снос­ках учи­ты­вать не сле­ду­ет. В от­ве­те ука­жи­те толь­ко число.

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

При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. В ком­пью­тер­ной си­сте­ме за­ре­ги­стри­ро­ва­но 16 930 поль­зо­ва­те­лей. Ука­жи­те ко­ли­че­ство Кбайт, вы­де­лен­ное на хра­не­ние всех па­ро­лей. В от­ве­те за­пи­ши­те толь­ко целое число.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 107 сим­во­лов. В ка­че­стве сим­во­лов ис­поль­зу­ют 1100-⁠бук­вен­ный ал­фа­вит. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт.

При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. В ком­пью­тер­ной си­сте­ме за­ре­ги­стри­ро­ва­но 32 768 поль­зо­ва­те­лей. Ука­жи­те ко­ли­че­ство Кбайт, вы­де­лен­ное на хра­не­ние всех па­ро­лей. В от­ве­те за­пи­ши­те толь­ко целое число.

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

При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. В ком­пью­тер­ной си­сте­ме за­ре­ги­стри­ро­ва­но 65 536 поль­зо­ва­те­лей. Ука­жи­те ко­ли­че­ство Кбайт, вы­де­лен­ное на хра­не­ние всех па­ро­лей. В от­ве­те за­пи­ши­те толь­ко целое число.

На ри­сун­ке пред­став­ле­на схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Ка­ко­ва длина са­мо­го про­тя­жен­но­го пути из го­ро­да А в город М? Дли­ной пути счи­тать ко­ли­че­ство дорог, со­став­ля­ю­щих этот путь.

Опе­ран­ды ариф­ме­ти­че­ско­го вы­ра­же­ния за­пи­са­ны в си­сте­ме счис­ле­ния с ос­но­ва­ни­ем 19:

В за­пи­си чисел пе­ре­мен­ной x обо­зна­че­на не­из­вест­ная цифра ал­фа­ви­та 19-⁠ричс­ной си­сте­мы счис­ле­ния. Опре­де­ли­те наи­мень­шее зна­че­ние x, при ко­то­ром зна­че­ние дан­но­го ариф­ме­ти­че­ско­го вы­ра­же­ния крат­но 18. Для най­ден­но­го зна­че­ния x вы­чис­ли­те част­ное от де­ле­ния зна­че­ния ариф­ме­ти­че­ско­го вы­ра­же­ния на 18 и ука­жи­те его в от­ве­те в де­ся­тич­ной си­сте­ме счис­ле­ния.

Ос­но­ва­ние си­сте­мы счис­ле­ния ука­зы­вать не нужно.

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

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

тож­де­ствен­но ис­тин­но?

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

тож­де­ствен­но ис­тин­но?

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

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

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

тож­де­ствен­но ис­тин­но?

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

F(n)  =  10, при n < 11;

F(n)  =  n + F(n − 1) , если n ≥ 11.

Чему равно зна­че­ние вы­ра­же­ния F(2024) − F(2022)?

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

F(n)  =  10, при n < 11;

F(n)  =  n + F(n − 1), если n ≥ 11.

Чему равно зна­че­ние вы­ра­же­ния F(2204) − F(2202)?

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

F(n)  =  10, при n < 11;

F(n)  =  n + F(n − 1), если n ≥ 11.

Чему равно зна­че­ние вы­ра­же­ния F(2022) − F(2019)?

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

F(n)  =  10, при n < 11;

F(n)  =  n + F(n − 1), если n ≥ 11.

Чему равно зна­че­ние вы­ра­же­ния F(2021) − F(2019)?

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

F(n)  =  10 при n < 11;

F(n)  =  n + F(n − 1), если n ≥ 11.

Чему равно зна­че­ние вы­ра­же­ния F(2124) − F(2122)?

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Эле­мен­ты по­сле­до­ва­тель­но­сти могут при­ни­мать целые зна­че­ния от −1 000 000 до 1 000 000 вклю­чи­тель­но.

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

Ответ:

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел. Эле­мен­ты по­сле­до­ва­тель­но­сти могут при­ни­мать целые зна­че­ния от −1 000 000 до 1 000 000 вклю­чи­тель­но.

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

Ответ:

Квад­рат раз­ли­но­ван на N х N кле­ток (1 < N < 30). Ис­пол­ни­тель Робот может пе­ре­ме­щать­ся по клет­кам, вы­пол­няя за одно пе­ре­ме­ще­ние одну из двух ко­манд: впра­во или вниз. По ко­ман­де впра­во Робот пе­ре­ме­ща­ет­ся в со­сед­нюю пра­вую клет­ку, по ко­ман­де вниз  — в со­сед­нюю ниж­нюю. Квад­рат огра­ни­чен внеш­ни­ми сте­на­ми.

Между со­сед­ни­ми клет­ка­ми квад­ра­та также могут быть внут­рен­ние стены. Сквозь стену Робот прой­ти не может.

Перед каж­дым за­пус­ком Ро­бо­та в каж­дой клет­ке квад­ра­та лежит мо­не­та до­сто­ин­ством от 1 до 100. По­се­тив клет­ку, Робот за­би­ра­ет мо­не­ту с собой; это также от­но­сит­ся к на­чаль­ной и ко­неч­ной клет­кам марш­ру­та Ро­бо­та.

В «уг­ло­вых» клет­ках поля  — тех, ко­то­рые спра­ва и снизу огра­ни­че­ны сте­на­ми, Робот He может про­дол­жать дви­же­ние, по­это­му на­коп­лен­ная сумма счи­та­ет­ся ито­го­вой. Таких ко­неч­ных кле­ток на поле может быть не­сколь­ко, вклю­чая пра­вую ниж­нюю клет­ку поля.

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

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

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

Ответ:

Робот впра­во вниз, за ко­неч­ные клет­ки при­ни­ма­ют­ся все ту­пи­ки, то есть все клет­ки, огра­ни­чен­ные внизу и спра­ва, найти мин макс.

Квад­рат раз­ли­но­ван на N х N кле­ток (1 < N < 30). Ис­пол­ни­тель Робот может пе­ре­ме­щать­ся по клет­кам, вы­пол­няя за одно пе­ре­ме­ще­ние одну из двух ко­манд: впра­во или вниз. По ко­ман­де впра­во Робот пе­ре­ме­ща­ет­ся в со­сед­нюю пра­вую клет­ку, по ко­ман­де вниз  — в со­сед­нюю ниж­нюю. Квад­рат огра­ни­чен внеш­ни­ми сте­на­ми.

Между со­сед­ни­ми клет­ка­ми квад­ра­та также могут быть внут­рен­ние стены. Сквозь стену Робот прой­ти не может.

Перед каж­дым за­пус­ком Ро­бо­та в каж­дой клет­ке квад­ра­та лежит мо­не­та до­сто­ин­ством от 1 до 100. По­се­тив клет­ку, Робот за­би­ра­ет мо­не­ту с собой; это также от­но­сит­ся к на­чаль­ной и ко­неч­ной клет­кам марш­ру­та Ро­бо­та.

В «уг­ло­вых» клет­ках поля  — тех, ко­то­рые спра­ва и снизу огра­ни­че­ны сте­на­ми, Робот He может про­дол­жать дви­же­ние, по­это­му на­коп­лен­ная сумма счи­та­ет­ся ито­го­вой. Таких ко­неч­ных кле­ток на поле может быть не­сколь­ко, вклю­чая пра­вую ниж­нюю клет­ку поля.

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

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

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

Ответ:

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один или че­ты­ре камня, или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. На­при­мер, имея кучу из 13 кам­ней, за один ход можно по­лу­чить кучу из 14, 16 или 39 кам­ней.

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

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

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

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу два или три камня, или уве­ли­чить ко­ли­че­ство кам­ней в куче в три раза. Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. На­при­мер, имея кучу из 13 кам­ней, за один ход можно по­лу­чить кучу из 15, 16 или 39 кам­ней.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ин­фор­ма­ция о про­цес­сах пред­став­ле­на в файле в виде таб­ли­цы. В пер­вой стро­ке таб­ли­цы ука­зан иден­ти­фи­ка­тор про­цес­са (ID), во вто­рой стро­ке таб­ли­цы  — время его вы­пол­не­ния в мил­ли­се­кун­дах, в тре­тьей стро­ке пе­ре­чис­ле­ны с раз­де­ли­те­лем «;» ID про­цес­сов, от ко­то­рых за­ви­сит дан­ный про­цесс. Если про­цесс яв­ля­ет­ся не­за­ви­си­мым, то в таб­ли­це ука­за­но зна­че­ние 0.

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

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

Вы­пол­ни­те за­да­ния, ис­поль­зуя дан­ные из файла ниже:

Ис­пол­ни­тель пре­об­ра­зу­ет число на экра­не. У ис­пол­ни­те­ля есть три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра.

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

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

3.  Умно­жить на 3.

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 3 ре­зуль­та­том яв­ля­ет­ся число 25 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 10 и не со­дер­жит число 17?

Ис­пол­ни­тель пре­об­ра­зу­ет число на экра­не. У ис­пол­ни­те­ля есть три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

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

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

3.  Умно­жить на 2.

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 4 ре­зуль­та­том яв­ля­ет­ся число 19 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 15 и не со­дер­жит число 6?

Ис­пол­ни­тель пре­об­ра­зу­ет число на экра­не. У ис­пол­ни­те­ля есть три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра.

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

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

3.  Умно­жить на 2.

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 3 ре­зуль­та­том яв­ля­ет­ся число 18 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 14 и не со­дер­жит число 8?

Ис­пол­ни­тель пре­об­ра­зу­ет число на экра­не. У ис­пол­ни­те­ля есть три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

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

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

3.  Умно­жить на 3.

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 3 ре­зуль­та­том яв­ля­ет­ся число 25 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 15 и не со­дер­жит число 9?

Ис­пол­ни­тель пре­об­ра­зу­ет число на экра­не. У ис­пол­ни­те­ля есть три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра.

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

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

3.  Умно­жить на 3.

Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 3 ре­зуль­та­том яв­ля­ет­ся число 18 и при этом тра­ек­то­рия вы­чис­ле­ний не со­дер­жит число 9 и не со­дер­жит число 15?

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те длину самой длин­ной не­пре­рыв­ной под­по­сле­до­ва­тель­но­сти, где сим­вол Y встре­ча­ет­ся не более 100 раз. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те ми­ни­маль­ную под­стро­ку, со­дер­жа­щую 210 сим­во­лов T. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те длину ми­ни­маль­ной под­стро­ки, со­дер­жа­щую не менее 130 сим­во­лов W. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те ми­ни­маль­ную под­стро­ку, со­дер­жа­щую 100 сим­во­лов Т. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

В ответ за­пи­ши­те длину ми­ни­маль­ной под­стро­ки, со­дер­жа­щу 100 сим­во­лов Т.

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те ми­ни­маль­ную под­стро­ку, со­дер­жа­щую 120 сим­во­лов V. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

Тек­сто­вый файл со­сто­ит не более чем из 10⁶ сим­во­лов ла­тин­ско­го ал­фа­ви­та. Опре­де­ли­те ми­ни­маль­ную длину под­стро­ки, со­дер­жа­щую ровно 110 сим­во­лов U. Для вы­пол­не­ния этого за­да­ния сле­ду­ет на­пи­сать про­грам­му.

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

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся на­ту­раль­ное число N (N ≤ 1000), обо­зна­ча­ю­щее ко­ли­че­ство со­бра­ний. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа: ука­зан­ное в за­яв­ке время про­ве­де­ния (в ми­ну­тах от на­ча­ла суток, не пре­вы­ша­ет 1300) и дли­тель­ность (в ми­ну­тах, не пре­вы­ша­ет 1000) со­бра­ния.

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

5

10 140

100 10

120 10

131 19

131 49

Ответ к при­ме­ру: 3 1.

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

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

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

Ответ: