Дан массив целых чисел x[1]..x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]..x[m] длины m и конца x[m+1]..x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец. (Число действий порядка m+n.)

[Решение]

Задача 2.

Некоторое число содержится в каждом из трех целочисленных неубывающих массивов x[1] <= ... <= x[p], y[1] <= ... <= y[q], z[1] <= ... <= z[r]. Найти одно из таких чисел. Число действий должно быть порядка p + q + r.

[Решение]

На шашечной доске размера n x n её верхний правый угол имеет номер (1,1). В позиции (i,j) стоит фишка, которая может двигаться по правилу, показанному на рисунке (допустимые ходы обозначены х, шашка - О). Фишка не может дважды ставиться на одно и то же поле.

Играют двое, по очереди двигая фишку. Выигрывает поставивший фишку в позицию (1,1).

Для введённых i,j определить, может ли выиграть первый игрок при наилучших ходах второго.

Написать программу, где первый игрок - компьютер.

[Решение]

Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a₁, либо a₂, либо ... a_S бананов (а₁ <a₂ <...<a_S), а 2-ая при каждом очередном

ходе --либо b₁, либо b₂, либо ... b_K бананов (b₁ <b₂ <...<b_K ). Нумерация индексов при a и b не имеет никакого отношения к номерам ходов обезьян Выигрывает та обезьяна, которая на своем ходе не может взять банан(ы) (либо потому, что их не осталось, либо потому что бананов осталось меньше чем a₁ (при ходе первой обезьяны) либо b₁ (при ходе второй обезьяны)).

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

[Решение]

Вводится целое число K>=1. Бумажная полоса разбита на N клеток (K <= N <= 40).Играют двое, по очереди выбирая и зачеркивая K пустых смежных клетки. Выигрывает сделавший последний ход.

Сверху печатается номер позиции. Зачеркнутые клетки помечаются символом '*'. В конце игры выдать сообщение 'Победа игрока 1(2)'. При вводе N и K выдать подсказывающие сообщения 'N>'и 'K>', при вводе хода - 'Ход игрока 1>'.Предусмотреть контроль корректности входных данных.

[Решение]

Пусть слово - это последовательность от 1 до 8 символов, не включающая пробелов.

Вводится n слов A₁,...,A_n. Можно ли их переупорядочить так, чтобы получилась "цепочка", т.е. для каждого слова A_j его первая буква должна совпадать с последней буквой предыдущего слова, а последняя буква в A_j - с первой буквой последующего слова; соответственно последняя буква последнего слова должна совпадать с первой буквой первого слова. В цепочку входят все n слов без повторений.

Дать ответ в виде "Можно"\"Нельзя".

Если такое упорядочение возможно, то вывести какую-нибудь цепочку слов. Слова при выводе разделяются пробелами.

[Решение]

На линейке из m клеток в разных концах стоят две фишки, которые ходят по очереди. Каждая из фишек может ходить влево или вправо не более чем на К клеток (m<=80;К<=m-2). При этом нельзя перешагивать через фишку и нельзя оставаться на месте. Фишка проигрывает, если она не может сделать ход. Написать программу, реализующую выигрышную стратегию для одной из фишек. При этом разрешается передача хода в самом начале игры. Предусмотреть контроль входных данных.

[Решение]

Составить программу, которая по введенному N выдает последовательность длины N, состоящую из цифр 0 и 1 такую, что ни один фрагмент этой подпоследовательности не повторяется подряд трижды.

[Решение]

Ввести три числа а,b,с.

1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c].

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

,

где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует.

[Решение]

Даны три слова X,Y,Z. Определить, существует ли слово V такое, что X,Y,Z являются повторениями слова V. Если V существует, то напечатать его. Слова имеют длину не более 1000 символов. Символ "пробел" является разделителем слов.

[Решение]

Даны два положительных целых числа А,В. Напечатать слово "ДА" или "НЕТ" в соответствии с тем, можно ли получить десятичную запись числа А путем вычеркивания одной или более цифр числа В.

[Решение]

Пусть А - последовательность букв. После вычеркивания одной буквы из А (в одной позиции)получили последовательность В. После вычеркивания другой буквы из А (в одной позиции) получили последовательность С.

Можно ли по последовательностям B и С

1) Определить вычеркнутые буквы.

2) Определить последовательность A.

Примечание: В и C могут быть получены вычеркиванием одной и той же буквы.

[Решение]

Имеется N книг и два читателя, А и В, желающих прочитать эти книги. Заданы неотрицательные целые числа A[I] и B[I] такие, что читателю А (или В) потребуется A[I] (соответственно, B[I]) часов для прочтения книги I, 1 <=I <=N. Процесс чтения начинается в момент времени 0. В любой момент времени каждый читатель не может читать более одной книги и каждую книгу не могут читать оба читателя.

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

Задано целое число К, 2<=K <=N, и книги пронумерованы таким образом, что ни один читатель не имеет права начать читать книгу J, 2<= J <= K, прежде чем книга J-1 не будет прочитана обоими читателями.

Требуется:

1. Вычислить наименьший момент времени Т, раньше которого все книги не могут быть прочитаны всеми читателями. Вывести вычисленное значение Т.

2. Построить расписание чтения книг каждым читателем, при котором не нарушается ни одно из перечисленных выше условий и процесс чтения всех книг завершается в момент времени Т. Расписание для каждого читателя вывести в виде

< РАСПИСАНИЕ ДЛЯ ЧИТАТЕЛЯ А (или В) >

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

3. Постарайтесь сократить число прерываний для каждого читателя.

Дана последовательность двузначных чисел

24,81,63,26,41,...

Продолжить ее. Найти правило формирования последующих членов.

[Решение]

Продолжить следующую последовательность

110 , 20 , 12 , 11 , 10 , ...

[Решение]

Янис и Петрис играют в следующую игру. Петрис загадывает декартовы координаты двух различных точек A(A_x,A_y) и B(B_x,B_y). Известно, что среди чисел A_x, A_y, B_x, B_y нет двух одинаковых. Янис может задавать вопросы только следующего вида: "Какое расстояние от точки P(P_x,P_y) до точки A (до точки B)?", где P_x и P_y - числа. В ответ Петрис называет число, которое является длиной отрезка PA (или, соответственно, PB). Определить, какое наименьшее количество вопросов должен задать Янис, чтобы он смог назвать координаты какой-либо точки, находящейся на серединном перпендикуляре отрезка AB, независимо от того, какие точки загадал Петрис. Описать, как найти эту точку. Ответ обосновать.

Известно, что среди 13 монет есть одна отличающаяся по весу (тяжелее одна или легче - неизвестно). За 3 взвешивания на чашечных весах найти эту монету.

[Решение]

"Быки и коровы"

Пользователь загадывает число из 4 цифр, каждая из которых от 1 до 6, причем все цифры различны. Разработать алгоритм, который угадывает число по следующим правилам: выводится число и пользователь сообщает, сколько в нем "быков" и "коров", т.е. сколько цифр стоят на своих местах и сколько цифр содержатся в обоих числах, но совпадают лишь по значению. Например, пусть загадано число 1264, спрошено 1256. В этом случае 2 быка (1,2) и одна корова (6).

Модификация: Правила игры те же, но загадывается 6-значное число с цифрами от 1 до 9, причем среди цифр допускаются одинаковые.

Примечание: Спрошенное число должно удовлетворять правилам для загадываемого; компьютеру на ход дается 1 минута.

[Решение]

Составить тесты для проверки правильности работы программы определения площади треугольника по его сторонам a, b, c.

[Решение]

Задача 19 (Прохоров В.В.).

Учитель попросил Диму написать программу вида

Ввод (x,y)

Пока < условия выполнения итерации >

НЦ

< тело цикла >

КЦ

Вывод (x,y)

т.е. такие < условия выполнения итерации > (не содержащие никаких переменных кроме x и y) и < тело цикла >, чтобы этот фрагмент для произвольных введенных в операторе ввода чисел x=x₀ и y=y₀ выдавал бы оператором вывода числа x=x₀+y₀ и y=x₀-y₀.

Помогите Диме.

Игровой автомат состоит из нескольких изогнутых трубок, по форме похожих на перевернутую вверх ногами букву "Y" . Сверху у трубы находится входное отверстие, а два выходных отверстия - снизу. Труба может находиться в одном из двух возможных состояний:

Шарики кладутся вовнутрь один за другим через входное отверстие. В состоянии 1 (Рис. 3), шарик покидает трубу через незаблокированный правый выход, при этом Состояние 1 автоматически изменяется на Состояние 0 ( Рис.4, правый вход заблокирован, левый -- нет ). В состоянии 0 все происходит наоборот.

Пусть игральный автомат состоит из 8 "Y"-образных трубок, их взаимное расположение показано на Рис.5. Вы можете забрасывать шарики через Вход A, Вход B, или Вход C. Пусть, например, первый шарик опускается через Вход A. Он покидает трубу G₁ через левый выход, изменяя ее состояние с 0 на 1, поступает в G₆ и покидает автомат через левый выход G₆ ( изменяя состояние G₆ c 0 на 1). Эту процедуру мы запишем следующим образом:

A

Затем мы забросим шарик через Вход A (он находится в Состоянии 1). Шаpик покидает G₁ чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G₄, покидает G₄ чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G₇, покидает автомат чеpез левый выход (изменяя G₇ из состояния 0 в состояние 1 ).Все вышеизложенные действия мы запишем в виде:

AA

Если мы опустим третий шарик через Вход B, четвертый - через Вход C, то все действия запишутся следующим образом:

AABC

Необходимо:

1. Ввести с клавиатуры последовательность из 8 двоичных цифр (бит), показывающих соответственно начальное состояние G₁-G₈:

Например, последовательность 11001010 означает, что G₈, G₇, G₄ и G₂ находятся в Состоянии 1 ( левый вход заблокирован ), тогда как G₆, G₅, G₃ и G₁ находятся в Состоянии 0 (правый вход заблокирован).

2. Ввести с клавиатуры вторую последовательность из 8 бит, показывающих конечные состояния G'₁-G'₈.

3. Напечатать последовательность ходов A, B, или C, указывающую, каким образом можно получить конечную позицию, забрасывая шарики через Входы A, B и C.

[Решение]

Определить, является ли периодической последовательностью строка символов A₁ A₂ ... A_N, т.е. имеет ли она вид d d ... d, где d - некоторая подпоследовательность символов.

[Решение]

Если мы из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то полученный результат назовем правильным скобочным выражением [скобочное выражение "(()(()))" - правильное, а "()(" и "())(" - нет].

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

[Решение]

Пусть слово - это последовательность от 1 до 8 заглавных букв латинского алфавита.

Задается множество слов A={a[1], a[2],..., a[n]}, n<10. Из слов множества A составляется текст - последовательность слов, записанных друг за другом без разделителей пробелов. Слова могут встречаться в тексте произвольное число раз.

Дешифровка текста - это разбивка текста на слова множества A. В дешифрованном тексте слова разделяются пробелами.

Необходимо:

1.Определить, существует ли для заданного множества A такой текст, который дешифруется не единственным образом (сам текст приводить не надо).

Примеры:

1) A = { B , C }

Любой текст дешифруется однозначно.

2) A = { B , BC , C }

Существует текст, который дешифруется двумя способами

Текст ---> Дешифровка

BBC ---> B B C

BBC ---> B BC

2. Если такой текст существует, то исключить из множества A минимальное число слов так, чтобы после этого любой текст, составленный из слов полученного множества A, дешифровался однозначно. Напечатать эти исключенные слова. Если такой набор не единственный, то напечатать все наборы.

3.Для введенного текста произвести его дешифровку и, если дешифровка не единственная, вывести все варианты.

Примечания: Порядок выполнения пунктов строго фиксирован.

[Решение]

На рисунке изображен фрагмент компьютерной сети. Система состоит из двух интерфейсов Международного Союза ORT и двух компьютеров. Каждый интерфейс подключен к отдельному компьютеру, один из которых является компьютером-передатчиком, другой - компьютером-приемником. Интерфейсы соединены друг с другом следующим образом: все восемь выходов интерфейса-передатчика соединены с восемью входами интерфейса-приемника, восьмой выход интерфейса-приемника соединен с восьмым входом интерфейса-передатчика. Реле входов (выходов) интерфейсов нумеруются с 0 по 7. Для включения реле-выхода с номером A запишите в порт с адресом 642 байт, в котором бит с номером A равен 1. Для выключения реле-выхода с номером A запишите в порт с адресом 642 байт, в котором бит с номером A равен 0. Для получения информации о состоянии реле-входа с номером A прочитайте байт из порта компьютера с адресом 642 и проанализируйте бит с номером A. Биты нумеруются, начиная с младшего.

Задание:

Написать программу, которая осуществляет:

1. Ввод с клавиатуры строки символов на компьютере-передатчике. Передачу строки через связанные интерфейсы на компьютер-приемник. Отображение данной строки на компьютере-приемнике.

2. Проверку типа компьютера (приемник или передатчик), на котором загружается программа с выдачей сообщения об этом.

3. Проверку правильности соединения интерфейсов согласно рисунку.

Примечание:

Выдача байта информации D в порт с адресом 642 и считывание байта D из порта с адресом 642 производится следующим образом:

[Решение]

Пометить ребра куба числами от 1 до 12 так, чтобы для всех вершин сумма пометок входящих ребер была одинакова.

[Решение]

КОМПОСТЕР

В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал на него несколько раз. Контролеру требуется определить, могло ли быть получено заданное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые отверстия не выходят за пределы билета. В билете было пробито N (N<10) отверстий.

ТРЕБУЕТСЯ:

А. Для компостера с двумя штырями (S=2) составить программу, которая:

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

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

3. При K=0 (см. п.2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий.

4. Находит минимальное число нажатий, требуемое для пробивки заданной конфигурации отверстий, для каждого компостера из пункта 2.

Б. Решить задачу А для компостеров с числом штырей S (S>2).

ПРИМЕЧАНИЯ.

* Все исходные данные - натуральные числа.

* Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются одинаковыми.

* Относительное расположение отверстий в билете и штырей в компостере вводится либо с клавиатуры, либо из файла с именем COMP.DAT .

Сруктура вводимой информации: {N,x[1],y[1],...,x[N],y[N],S,u[1],v[1],...,u[S],v[S]},

где x[i], y[i] – координаты отверстий в билете, u[i], v[i] - координаты штырей в компостере.

* Нажатие компостера (см. п.1) моделировать клавишей "Пробел".

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

[Решение]

Дан массив a[1..n] и число b. Переставить числа в массиве таким образом, чтобы слева от некоторой границы стояли числа, меньшие или равные b, а справа от границы - большие или равные b.

[Решение]

Та же задача, но требуется, чтобы сначала шли элементы, меньшие b, затем равные b, а лишь затем большие b.

[Решение]