По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, каж­дое из ко­то­рых со­дер­жит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (дру­гих букв в со­об­ще­ни­ях нет). Каж­дую букву ко­ди­ру­ют дво­ич­ной по­сле­до­ва­тель­но­стью. При вы­бо­ре кода учи­ты­ва­лись два тре­бо­ва­ния:

а)  ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го (это нужно, чтобы код до­пус­кал од­но­знач­ное де­ко­ди­ро­ва­ние);

б)  общая длина за­ко­ди­ро­ван­но­го со­об­ще­ния долж­на быть как можно мень­ше.

Какой код из при­ведённых ниже сле­ду­ет вы­брать для ко­ди­ро­ва­ния букв А, Б, В и Г?

1)  А:0, Б:10, В:110, Г:111

2)  А:0, Б:10, В:01, Г:11

3)  А:1, Б:01, В:011, Г:001

4)  А:00, Б:01, В:10, Г:11

Миша за­пол­нял таб­ли­цу ис­тин­но­сти для вы­ра­же­ния F. Он успел за­пол­нить лишь не­боль­шой фраг­мент таб­ли­цы:

Каким вы­ра­же­ни­ем может быть F?

1)  x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8

2)  ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ x6 ∧ x7 ∧ x8

3)  x1 ∨ x2 ∨ ¬ x3 ∨ x4 ∨ x5 ∨ ¬x6 ∨ x7 ∨ x8

4)  x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 ∨ ¬x8

Ниже пред­став­ле­ны две таб­ли­цы из базы дан­ных. Каж­дая стро­ка таб­ли­цы 2 со­дер­жит ин­фор­ма­цию о ребёнке и об одном из его ро­ди­те­лей. Ин­фор­ма­ция пред­став­ле­на зна­че­ни­ем поля ID в со­от­вет­ству­ю­щей стро­ке таб­ли­цы 1. Опре­де­ли­те на ос­но­ва­нии при­ведённых дан­ных ID дяди Ва­щен­ко К. Г.

По­яс­не­ние: дядей счи­та­ет­ся род­ной брат отца или ма­те­ри.

Сколь­ко еди­ниц в дво­ич­ной за­пи­си вось­ме­рич­но­го числа 1731₈?

Между населёнными пунк­та­ми A, B, C, D, E, F по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых при­ве­де­на в таб­ли­це. От­сут­ствие числа в таб­ли­це озна­ча­ет, что пря­мой до­ро­ги между пунк­та­ми нет.

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

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

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

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

а)  скла­ды­ва­ют­ся все цифры дво­ич­ной за­пи­си, и оста­ток от де­ле­ния суммы на 2 до­пи­сы­ва­ет­ся в конец числа (спра­ва). На­при­мер, за­пись 11100 пре­об­ра­зу­ет­ся в за­пись 111001;

б)  над этой за­пи­сью про­из­во­дят­ся те же дей­ствия  — спра­ва до­пи­сы­ва­ет­ся оста­ток от де­ле­ния суммы цифр на 2.

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

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

Дан фраг­мент элек­трон­ной таб­ли­цы. Из ячей­ки D2 в ячей­ку E1 была ско­пи­ро­ва­на фор­му­ла. При ко­пи­ро­ва­нии ад­ре­са ячеек в фор­му­ле ав­то­ма­ти­че­ски из­ме­ни­лись. Каким стало чис­ло­вое зна­че­ние фор­му­лы в ячей­ке E1?

При­ме­ча­ние. Знак $ обо­зна­ча­ет аб­со­лют­ную ад­ре­са­цию.

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

Му­зы­каль­ный фраг­мент был оциф­ро­ван и за­пи­сан в виде файла без ис­поль­зо­ва­ния сжа­тия дан­ных. По­лу­чив­ший­ся файл был пе­ре­дан в город А по ка­на­лу связи за 30 се­кунд. Затем тот же му­зы­каль­ный фраг­мент был оциф­ро­ван по­втор­но с раз­ре­ше­ни­ем в 2 раза выше и ча­сто­той дис­кре­ти­за­ции в 1,5 раза мень­ше, чем в пер­вый раз. Сжа­тие дан­ных не про­из­во­ди­лось. По­лу­чен­ный файл был пе­ре­дан в город Б; про­пуск­ная спо­соб­ность ка­на­ла связи с го­ро­дом Б в 4 раза выше, чем ка­на­ла связи с го­ро­дом А. Сколь­ко се­кунд дли­лась пе­ре­да­ча файла в город Б? В от­ве­те за­пи­ши­те толь­ко целое число, еди­ни­цу из­ме­ре­ния пи­сать не нужно.

Вася со­став­ля­ет 5-⁠бук­вен­ные слова, в ко­то­рых есть толь­ко буквы С, Л, О, Н, причём буква С ис­поль­зу­ет­ся в каж­дом слове ровно 1 раз. Каж­дая из дру­гих до­пу­сти­мых букв может встре­чать­ся в слове любое ко­ли­че­ство раз или не встре­чать­ся со­всем. Сло­вом счи­та­ет­ся любая до­пу­сти­мая по­сле­до­ва­тель­ность букв, не обя­за­тель­но осмыс­лен­ная. Сколь­ко су­ще­ству­ет таких слов, ко­то­рые может на­пи­сать Вася?

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­ны две ре­кур­сив­ные функ­ции (про­це­ду­ры): F и G.

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(11)?

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

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

Для узла с IP-⁠ад­ре­сом 117.191.88.37 адрес сети равен 117.191.80.0. Чему равен тре­тий слева байт маски? Ответ за­пи­ши­те в виде де­ся­тич­но­го числа.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 15 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы из 12-⁠сим­воль­но­го на­бо­ра: А, В, C, D, Е, F, G, H, К, L, M, N. В базе дан­ных для хра­не­ния све­де­ний о каж­дом поль­зо­ва­те­ле от­ве­де­но оди­на­ко­вое и ми­ни­маль­но воз­мож­ное целое число байт. При этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние па­ро­лей, все сим­во­лы ко­ди­ру­ют оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Кроме соб­ствен­но па­ро­ля, для каж­до­го поль­зо­ва­те­ля в си­сте­ме хра­нят­ся до­пол­ни­тель­ные све­де­ния, для чего от­ве­де­но 12 байт на од­но­го поль­зо­ва­те­ля.

Опре­де­ли­те объём па­мя­ти (в бай­тах), не­об­хо­ди­мый для хра­не­ния све­де­ний о 50 поль­зо­ва­те­лях. В от­ве­те за­пи­ши­те толь­ко целое число  — ко­ли­че­ство байт.

Ис­пол­ни­тель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плос­ко­сти, остав­ляя след в виде линии. Чертёжник может вы­пол­нять ко­ман­ду сме­стить­ся на (a, b), где a, b – целые числа. Эта ко­ман­да пе­ре­ме­ща­ет Чертёжника из точки с ко­ор­ди­на­та­ми (x, y) в точку с ко­ор­ди­на­та­ми (x + a; y + b). На­при­мер, если Чертёжник на­хо­дит­ся в точке с ко­ор­ди­на­та­ми (4, 2), то ко­ман­да сме­стить­ся на (2, −3) пе­ре­ме­стит Чертёжника в точку (6, −1).

Цикл

ПО­ВТО­РИ число РАЗ

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

КОНЕЦ ПО­ВТО­РИ

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

Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм (ко­ли­че­ство по­вто­ре­ний и ве­ли­чи­ны сме­ще­ния в пер­вой из по­вто­ря­е­мых ко­манд не­из­вест­ны):

НА­ЧА­ЛО

сме­стить­ся на (1, 2)

ПО­ВТО­РИ … РАЗ

сме­стить­ся на (…, …)

сме­стить­ся на (-1, -2)

КОНЕЦ ПО­ВТО­РИ

сме­стить­ся на (-26, -12)

КОНЕЦ

В ре­зуль­та­те вы­пол­не­ния этого ал­го­рит­ма Чертёжник воз­вра­ща­ет­ся в ис­ход­ную точку. Какое наи­боль­шее число по­вто­ре­ний могло быть ука­за­но в кон­струк­ции «ПО­ВТО­РИ … РАЗ»?

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

Сколь­ко еди­ниц со­дер­жит­ся в дво­ич­ной за­пи­си зна­че­ния вы­ра­же­ния: 4¹⁶ + 2³⁶ – 16?

В языке за­про­сов по­ис­ко­во­го сер­ве­ра для обо­зна­че­ния ло­ги­че­ской опе­ра­ции «ИЛИ» ис­поль­зу­ет­ся сим­вол «|», а для ло­ги­че­ской опе­ра­ции «И» – сим­вол «&».

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

Какое ко­ли­че­ство стра­ниц (в ты­ся­чах) будет най­де­но по за­про­су

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

Обо­зна­чим через ДЕЛ(n, m) утвер­жде­ние «на­ту­раль­ное число n де­лит­ся без остат­ка на на­ту­раль­ное число m».

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

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

В про­грам­ме ис­поль­зу­ет­ся од­но­мер­ный це­ло­чис­лен­ный мас­сив A с ин­дек­са­ми от 0 до 9. Зна­че­ния эле­мен­тов равны 8, 4, 3, 0, 7, 2, 1, 5, 9, 6 со­от­вет­ствен­но, т. е. A[0] = 8, A[1] = 4 и т. д. Опре­де­ли­те зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния сле­ду­ю­ще­го фраг­мен­та этой про­грам­мы (за­пи­сан­но­го ниже на раз­ных язы­ках про­грам­ми­ро­ва­ния).

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан ал­го­ритм. По­лу­чив на вход число x, этот ал­го­ритм пе­ча­та­ет два числа: L и M. Ука­жи­те наи­мень­шее число x, при вводе ко­то­ро­го ал­го­ритм пе­ча­та­ет сна­ча­ла 3, а потом 6.

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

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

У ис­пол­ни­те­ля есть две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

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

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

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая умно­жа­ет его на 2. Про­грам­ма для ис­пол­ни­те­ля Ап­рель15 – это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1

ре­зуль­та­том яв­ля­ет­ся число 21 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 10?

Тра­ек­то­рия вы­чис­ле­ний про­грам­мы – это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 16, 17.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, ... x6, y1, y2, ... y6, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)

(x2 ∧ y2) ≡ (¬x3 ∨ ¬y3)

…

(x5 ∧ y5) ≡ (¬x6 ∨ ¬y6)

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ... x6, y1, y2, ... y6, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

На об­ра­бот­ку по­сту­па­ет на­ту­раль­ное число, не пре­вы­ша­ю­щее 10⁹. Нужно на­пи­сать про­грам­му, ко­то­рая вы­во­дит на экран мак­си­маль­ную цифру числа, крат­ную 3. Если в числе нет цифр, крат­ных 3, тре­бу­ет­ся на экран вы­ве­сти «NO». Про­грам­мист на­пи­сал про­грам­му не­пра­виль­но. Ниже эта про­грам­ма для Ва­ше­го удоб­ства при­ве­де­на на пяти язы­ках про­грам­ми­ро­ва­ния.

На­по­ми­на­ние: 0 де­лит­ся на любое на­ту­раль­ное число.

По­сле­до­ва­тель­но вы­пол­ни­те сле­ду­ю­щее.

1.  На­пи­ши­те, что вы­ве­дет эта про­грам­ма при вводе числа 134.

2.  При­ве­ди­те при­мер та­ко­го трёхзнач­но­го числа, при вводе ко­то­ро­го про­грам­ма выдаёт вер­ный ответ.

3.  Най­ди­те все ошиб­ки в этой про­грам­ме (их может быть одна или не­сколь­ко). Из­вест­но, что каж­дая ошиб­ка за­тра­ги­ва­ет толь­ко одну стро­ку и может быть ис­прав­ле­на без из­ме­не­ния дру­гих строк. Для каж­дой ошиб­ки:

1)  вы­пи­ши­те стро­ку, в ко­то­рой сде­ла­на ошиб­ка;

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

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

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

Дан це­ло­чис­лен­ный мас­сив из 20 эле­мен­тов. Эле­мен­ты мас­си­ва могут при­ни­мать целые зна­че­ния от –10 000 до 10 000 вклю­чи­тель­но. Опи­ши­те на есте­ствен­ном языке или на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм,

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

На­при­мер, для мас­си­ва из пяти эле­мен­тов: 6; 2; 9; –3; 6 – ответ: 2.

Ис­ход­ные дан­ные объ­яв­ле­ны так, как по­ка­за­но ниже на при­ме­рах для не­ко­то­рых язы­ков про­грам­ми­ро­ва­ния и есте­ствен­но­го языка. За­пре­ща­ет­ся ис­поль­зо­вать пе­ре­мен­ные, не опи­сан­ные ниже, но раз­ре­ша­ет­ся не ис­поль­зо­вать не­ко­то­рые из опи­сан­ных пе­ре­мен­ных.

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

про­грам­ми­ро­ва­ния (ука­жи­те на­зва­ние и ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер Free Pascal 2.6) или в виде блок-схемы. В этом слу­чае Вы долж­ны ис­поль­зо­вать те же самые ис­ход­ные дан­ные и пе­ре­мен­ные, какие были пред­ло­же­ны в усло­вии (на­при­мер, в об­раз­це, за­пи­сан­ном на есте­ствен­ном языке).

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

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

В на­чаль­ный мо­мент в пер­вой куче было 5 кам­ней, во вто­рой куче – S кам­ней; 1 ≤ S ≤ 49.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

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

до­ста­точ­но ука­зать один вы­иг­ры­ва­ю­щий ход.

б)  Сколь­ко су­ще­ству­ет зна­че­ний S, при ко­то­рых Петя не может вы­иг­рать за один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом?

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

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

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

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

3.  Ука­жи­те зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

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

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

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На рёбрах де­ре­ва ука­зы­вай­те ходы,

в узлах ука­зы­вай­те по­зи­ции. В за­да­ни­ях 2 и 3 до­ста­точ­но ука­зать одно зна­че­ние S и объ­яс­нить, по­че­му это

зна­че­ние удо­вле­тво­ря­ет усло­вию со­от­вет­ству­ю­ще­го за­да­ния.

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

нечётное про­из­ве­де­ние двух по­ка­за­ний, между мо­мен­та­ми пе­ре­да­чи ко­то­рых про­шло не менее 6 минут. Если по­лу­чить такое про­из­ве­де­ние не удаётся, ответ счи­та­ет­ся рав­ным −1. Ко­ли­че­ство энер­гии, по­лу­ча­е­мое при­бо­ром за ми­ну­ту, не пре­вы­ша­ет 1000 услов­ных еди­ниц. Общее ко­ли­че­ство по­ка­за­ний при­бо­ра в серии не пре­вы­ша­ет 10 000.

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

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

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

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

Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния. ОБЯ­ЗА­ТЕЛЬ­НО ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем ЗА­ДА­НИЯ А. Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А  — 2 балла.

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

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

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

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

ОБЯ­ЗА­ТЕЛЬ­НО ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем ЗА­ДА­НИЯ Б. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти,  — 4 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти,  — 3 балла.

НА­ПО­МИ­НА­ЕМ! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

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

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

11

12

45

5

3

17

23

21

20

19

12

26

Про­грам­ма долж­на вы­ве­сти одно число  — опи­сан­ное в усло­вии про­из­ве­де­ние, либо  — 1, если по­лу­чить такое про­из­ве­де­ние не удаётся.

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

95