Для ко­ди­ро­ва­ния по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв К, О, Л, Р, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Букве К со­от­вет­ству­ет дво­ич­ный код 00, букве Р  — код 011.

Ка­ко­ва наи­мень­шая сум­мар­ная длина ко­до­вых слов для всех букв в слове КО­ЛО­КОЛ?

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

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

2.  К этой за­пи­си до­пи­сы­ва­ют­ся спра­ва ещё не­сколь­ко раз­ря­дов по сле­ду­ю­щим пра­ви­лам:

—  если число N чет­ное, то спра­ва к этой за­пи­си до­пи­сы­ва­ет­ся 1 и слева также до­пи­сы­ва­ет­ся 1;

—  если число N не­чет­ное, то спра­ва к этой за­пи­си до­пи­сы­ва­ет­ся 10, а слева  — 1.

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

В от­ве­те за­пи­ши­те число в де­ся­тич­ной си­сте­ме счис­ле­ния.

Лена за­пи­сы­ва­ет го­ло­со­вое со­об­ще­ние для своей по­дру­ги. Перед от­прав­кой со­об­ще­ние оциф­ро­вы­ва­ет­ся в фор­ма­те сте­рео с ча­сто­той дис­кре­ти­за­ции 32 000 Гц и глу­би­ной ко­ди­ро­ва­ния 16 бит. Опре­де­ли­те наи­мень­шее целое ко­ли­че­ство Кбайт, не­об­хо­ди­мое для со­хра­не­ния со­об­ще­ния в па­мя­ти (без учёта за­го­лов­ка), если его дли­тель­ность  — 2 ми­ну­ты 27 се­кунд.

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

Лена за­пи­сы­ва­ет го­ло­со­вое со­об­ще­ние для своей по­дру­ги. Перед от­прав­кой со­об­ще­ние оциф­ро­вы­ва­ет­ся в фор­ма­те сте­рео с ча­сто­той дис­кре­ти­за­ции 20 000 Гц и глу­би­ной ко­ди­ро­ва­ния 24 бит. Опре­де­ли­те наи­мень­шее целое ко­ли­че­ство Кбайт, не­об­хо­ди­мое для со­хра­не­ния со­об­ще­ния в па­мя­ти (без учёта за­го­лов­ка), если его дли­тель­ность  — 2 ми­ну­ты 18 се­кунд.

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

Все пя­ти­бук­вен­ные слова, со­став­лен­ные из букв А, К, Ц, Е, Н, Т, за­пи­са­ны в ал­фа­вит­ном по­ряд­ке и про­ну­ме­ро­ва­ны.

Вот на­ча­ло спис­ка:

1.  ААААА

2.  ААААЕ

3.  ААААК

4.  ААААН

5.  ААААТ

6.  ААААЦ

...

Опре­де­ли­те, под каким но­ме­ром в этом спис­ке стоит пер­вое слово, ко­то­рое не на­чи­на­ет­ся с букв А, Е и К и при этом со­дер­жит в своей за­пи­си не менее одной буквы Т.

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

С по­мо­щью тек­сто­во­го ре­дак­то­ра опре­де­ли­те, сколь­ко раз встре­ча­ет­ся от­дель­ное слово «и» или «И» в тек­сте глав XI и XIV вто­рой части тома 2 ро­ма­на Л. Н. Тол­сто­го «Война и мир». В от­ве­те за­пи­ши­те толь­ко число.

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

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му объ­ек­ту при­сва­и­ва­ет­ся иден­ти­фи­ка­тор, со­сто­я­щий из 257 сим­во­лов и со­дер­жа­щий толь­ко цифры сем­на­дца­ти­рич­ной си­сте­мы счис­ле­ния и сим­во­лы из 4080-⁠сим­воль­но­го спе­ци­аль­но­го ал­фа­ви­та. В базе дан­ных для хра­не­ния каж­до­го иден­ти­фи­ка­то­ра от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние иден­ти­фи­ка­то­ров, все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Опре­де­ли­те объём па­мя­ти (в Мбайт), не­об­хо­ди­мый для хра­не­ния 8 388 608 иден­ти­фи­ка­то­ров. В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство Мбайт.

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

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

Узел имеет IP-⁠адрес 210.185.140.126. Маска сети равна 255.255.255.252. Опре­де­ли­те наи­мень­ший воз­мож­ный IP-⁠адрес в этой сети (адрес сети) и в от­ве­те за­пи­ши­те сумму зна­че­ний его ок­те­тов.

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния

за­пи­са­ли в дво­ич­ной си­сте­ме счис­ле­ния. Сколь­ко цифр 0 со­дер­жит­ся в этой за­пи­си?

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния

за­пи­са­ли в 36-⁠рич­ной си­сте­ме счис­ле­ния. Опре­де­ли­те ко­ли­че­ство цифр, не пре­вы­ша­ю­щих 9, в этой за­пи­си.

Зна­че­ние ариф­ме­ти­че­ско­го вы­ра­же­ния 5¹⁵⁰ + 5¹⁰⁰ –⁠ x, где x  — целое по­ло­жи­тель­ное число, мень­шее 2030, за­пи­са­ли в пя­те­рич­ной си­сте­ме счис­ле­ния. Опре­де­ли­те наи­мень­шее зна­че­ние x, при ко­то­ром ко­ли­че­ство нулей в пя­те­рич­ной за­пи­си числа, яв­ля­ю­ще­го­ся зна­че­ни­ем дан­но­го ариф­ме­ти­че­ско­го вы­ра­же­ния, мак­си­маль­но.

В от­ве­те за­пи­ши­те число в де­ся­тич­ной си­сте­ме счис­ле­ния.

Обо­зна­чим через ДЕЛ(x, y) утвер­жде­ние «на­ту­раль­ное число x де­лит­ся без остат­ка на на­ту­раль­ное число y». Для ка­ко­го наи­боль­ше­го на­ту­раль­но­го числа A ло­ги­че­ское вы­ра­же­ние

ис­тин­но при любом на­ту­раль­ном зна­че­нии пе­ре­мен­ной x?

Для ка­ко­го наи­мень­ше­го на­ту­раль­но­го числа A фор­му­ла

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

Обо­зна­чим через ДЕЛ(n, m) утвер­жде­ние «на­ту­раль­ное число n де­лит­ся без остат­ка на на­ту­раль­ное число m». Задан от­ре­зок B  =  [65; 85]. Для ка­ко­го наи­боль­ше­го на­ту­раль­но­го числа A фор­му­ла

тож­де­ствен­но ис­тин­на (т. е. при­ни­ма­ет зна­че­ние 1) при любом целом по­ло­жи­тель­ным зна­че­нии пе­ре­мен­ной x?

Обо­зна­чим через ДЕЛ(n, m) утвер­жде­ние «на­ту­раль­ное число n де­лит­ся без остат­ка на на­ту­раль­ное число m». Задан от­ре­зок B  =  [30; 40]. Опре­де­ли­те ми­ни­маль­ное ко­ли­че­ство эле­мен­тов мно­же­ства A при ко­то­ром фор­му­ла

тож­де­ствен­но ис­тин­на (т. е. при­ни­ма­ет зна­че­ние 1) при любом целом по­ло­жи­тель­ном зна­че­нии пе­ре­мен­ной x?

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

если

если

Опре­де­ли­те зна­че­ние

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

если

если и не­чет­но;

если и четно.

Опре­де­ли­те зна­че­ние

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел.

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

Ответ:

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел от –⁠100 000 до 100 000.

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

Ответ:

В файле со­дер­жит­ся по­сле­до­ва­тель­ность целых чисел.

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

Ответ:

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может:

—  до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) 3 камня;

—  уве­ли­чить ко­ли­че­ство кам­ней в одной из куч (по сво­е­му вы­бо­ру) в 3 раза.

На­при­мер, пусть в одной куче 20 кам­ней, а в дру­гой 30 кам­ней; такую по­зи­цию в игре обо­зна­чим (20, 30). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (23, 30), (20, 33), (60, 30), (20, 90).

Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда сум­мар­ное ко­ли­че­ство кам­ней в двух кучах ста­но­вит­ся не менее 176. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший такую иг­ро­вую по­зи­цию, при ко­то­рой в двух кучах сум­мар­но 176 кам­ней или боль­ше. В на­чаль­ный мо­мент в пер­вой куче 14 кам­ней, во вто­рой куче  — S кам­ней;

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

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

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

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

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

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

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

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

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

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

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

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

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

Опре­де­ли­те ми­ни­маль­ное время, в ко­то­рое за­кон­чат свою ра­бо­ту 18 про­цес­сов.

Для при­ведённой таб­ли­цы про­цесс 3 на­чи­на­ет­ся на 8-⁠й мс, за­кан­чи­ва­ет­ся на 9-⁠й мс.

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

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

1.  Вычти 1

2.  Найди целую часть от де­ле­ния на 2

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

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

1.  При­бавь 1

2.  По­ме­няй ме­ста­ми

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

Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 110 ре­зуль­та­том яв­ля­ет­ся число 154?

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

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

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

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

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

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

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

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

Ответ: