A0. “IntelliSense”

Во многих IDE (Integrated Development Environment) существует замечательная функция автодополнения ключевых слов и идентификаторов. Ее наличие было бы громадным плюсом для текстовых редакторов (особенно английского языка, где практически отсутствуют окончания).
Предлагается написать программу, которая для введенного слова подберет K слов из словаря с наибольшими частотами. Если вариантов меньше K , вывести все, какие есть.

Ввод:

В первой строке – начало слова, которое надо дополнить.
Во второй строке - целое неотрицательное число K <= 2000 – количество необходимых вариантов.
В третьей строке - целое неотрицательное число N <= 200000 – число слов в словаре.
Далее N строк с парами «слово-частота» (через пробел). Длина слова - не более 10 символов, частота – целое, неотрицательное число < 10^9.

Вывод:

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

Пример:

Ввод:                      Вывод:
rt                         rt.mipt 400
2                          rtlabs 34
5                          
fopf 325
rtlabs 34
frtk 100000
rt.mipt 400
rt 2

A1. “Измерения”

В некотором приборе угол определяется при помощи считывания с вала меток. При этом каждая метка представляет собой N-разрядное двоичное число, записанное вдоль вала: нуль изображается светлым участком, а единица – черным. Метки на поверхности вала нанесены подряд, без зазоров. Каждый разряд метки считывается своим датчиком (всего датчиков N и они расположены параллельно осевой линии вала). Когда в зону считывания датчиков попадает зона перехода от одной метки к другой, каждый из датчиков может прочитать значение бита, соответствующее либо одной метке, либо соседней. Например, для N = 2 возможен следующий порядок меток: 00, 01, 10, 11. Однако из-за того, что датчики имеют конечную длину при таком порядке следования меток возможны ошибки при чтении: при нахождении датчика между второй и третьей меткой, может быть прочитано неправильное значение (00 или 11).
Предложите порядок следования меток, лишенный этого недостатка, т.е. когда датчики находятся между двух строчек будет прочитано значение одной из этих строчек.

Ввод:

N < 18 (разрядность)

Вывод:

Последовательность меток, обеспечивающая максимальную точность. (Количество меток в последовательности – максимальна для данной длины меток)

Пример:

Ввод:            Вывод:
3                000
                 001
                 011
                 010
                 110
                 111
                 101
                 100 

A2 “Замок короля Артура”

На равнине стоит замок короля Артура. Стена замка представляет собой замкнутую ломаную без самопересечений, причем между каждыми двумя последовательными звеньями стены построены башни. Для простоты будем нумеровать эти башни от 1 до N (N < 100 и все они пронумерованы против часовой стрелки). Пусть звено стены определяется двумя принадлежащими ей башнями. Одинокий странник приближается к замку с произвольной стороны и заходит внутрь.
Необходимо определить в зависимости от положения странника, те звенья стены между любыми двумя башнями (номера которых отличаются на 1), которые он увидит полностью или частично в качестве невырожденного отрезка. Считается, что если путник видит звено стены как точку или как пару точек, то оно не видно. Странник не может находиться на стене.

Ввод:

N - Количество башен
Далее N cтрок с кординатами башен - целыми чисами меньшими по модулю 32000
В последней строке - координаты путника

Вывод:

Количество звеньев стены, которые увидит спутник.

Пример:

Ввод:             Вывод: 
4                 2
-1 -5
4 -5 
4 0
0 0
5 1

A3 “Задача про числа”

Пусть заданы числа a и b. Вычислить с – порядок степени - такой что остаток от деления a^с на b будет равен 1 (с > 0, a, b < 2^31).

Ввод: a b

Вывод: c либо NO , если такого с не существует

Пример:

Ввод:        Вывод:
6 7          2

A4 “Шахматы”

Однажды шахматисту пришла в голову следующая задачка: “Сколькими способами можно пройти из клетки a1 в правый верхний угол шахматной доски, двигаясь каждый раз только на одну клетку вправо или вверх и ни разу не оказавшись выше главной диагонали”? Помогите ему найти ответ.

Ввод: N < 100, где N – размер шахматной доски

Вывод: количество способов

Пример:

Ввод:         Вывод:

4             5

A5. “Паркур“

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

Ввод:

В первой строчке число K <= 4 (вещественное) и N (2 <= N <= 10).
Следующие N строчек из 5 чисел описывают дома. Первое – номер дома, дальше 2 пары декартовых координат (вершины в углах сетки с целыми числами в метрах), описывающие верхний левый и правый нижний углы прямоугольной крыши дома. Крыши домов находятся на одной высоте. Первый описанный дом – крыша, на которой начинает паркурщик.

Вывод:

Номера домов в порядке прыжков по ним

Пример:

Ввод:       Вывод: 3 2 1 4
2 4               
3 -2 0 0 -2 
2 1 2 2 1 
4 5 2 8 1 
1 3 4 6 3

A6.”Знаменитости”

Есть группа людей, cреди них может быть знаменитость. Знаменитость никого не знает, но знаменитость знают все. Требутся, задав минимальное число вопросов людям из группы, определить, есть ли среди них знаменитость, и, если есть, то кто.
Для того чтобы спросить человека m, знает ли он человека n, нужно вызвать функцию doesHeKnow(m, n). Если нужно узнать количество людей, то надо использовать функцию getPeopleNum(). После того как программа готова ответить на данный вопрос, она должна вызвать функцию noCelebrity(), если знаменитости в толпе нет, и celebrity(n) , чтобы показать, что человек n является знаменитостью.

Примечание:

В этой задаче необходимо прислать исходный текст модуля, на котором тестировалась программа. Имя включаемого файла в С\С++ Knowledge.h, в Java имя включаемого класса Knowledge (его методы статические), в Паскале Knowledge.inc. В Паскале вместо типа int (которого нет) использовать тип integer. В С/С++ в качестве булевых значений использовать числа: 1 (вместо true), 0 (вместо false). Ограничения: m < 2^15, n < 2^15.

Описание функций:

boolean doesHeKnow(int m, int n) - возвращает true , если m знает n , иначе false
int getPeopleNum() - возвращает число людей
void celebrity(int n) n - номер знаменитости
void noCelebrity()

Пример:

C: Knowledge.h
#include <Knowledge.h>
void main(){
int pNum = getPeopleNum();
if ( doesHeKnow(0,1) ) celebrity(1);
else noCelebrity();
}

A7.”IKT mobile”

Компания “IKT Mobile” решила создать собственную сеть в городе N. Она обратилась в компанию “IKT net design”, специализирующуюся на проектировании сотовых сетей. Компания “IKT net design” разработала проект. Вы являетесь инженером “IKT net design” и вам необходимо рассчитать максимальную ширину канала между узлами X и Y, который может быть предоставлен клиенту (для данного проекта). Сделайте этот расчет.

Ввод:

В первой строчке <количество узлов в сети> <номер узла X> <номер узла Y>
В каждой последующей строке параметры линии связи в виде
<номер узла> <номер узла> <пропускная способность прямой линии связи>.

Вывод:

число – ширина канала между узлами X и Y.

Примечание:

<пропускная способность канала> = <пропускная способность канала A -> B> = <пропускная способность канала B -> A>. Если пропускная способность между узлами не задана, то считаем, что они не соединены напрямую. Нумерация узлов в сети начинается с 1. Число узлов в сети не больше 100, пропускные способности – целые числа < 2^15.

Пример:

Ввод:        Вывод: 
3 1 3        17
1 3 10 
1 2 15       
2 3 7