Информатика

По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква	Кодовое слово		Буква	Кодовое слово
А	00		Л	1001
Б	1000		Р	1110
Е	010		С	1010
И	011		Т
К	1011		У	110

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

По каналу связи передаются сообщения, содержащие только четыре буквы: З, А, Р, Я; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Я, Р, З используются такие кодовые слова: Я –$–$ 0,
Р –$–$ 101; З –$–$ 110.
Укажите кратчайшее кодовое слово для буквы А, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код
с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
 

K участникам сборов для решения было предложено K задач. Участники решили разделить задачи между собой, решить каждому по одной задаче, а затем обменяться решениями (они не учли, что система ejudge способна отследить данный факт J). Известно ориентировочное время, за которое каждый из участников сборов может решить каждую из предложенных задач.

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

Входные данные
Во входном файле сначала записано число K (0 < K < 101) и далее K2 неотрицательных целых чисел, не превосходящие 20000, описывающих матрицу K x K, времен решения каждым из участников каждой из задач.

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

По каналу связи передаются сообщения, содержащие только четыре буквы: З, А, Р, Я; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Я, Р, З используются такие кодовые слова: Я –$–$ 0, Р –$–$ 101;
З –$–$ 110.
Укажите кратчайшее кодовое слово для буквы А, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
 

Остров народа Флатопии представляет собой часть плоскости. К сожалению, во Флатопии очень плохая система дорог. Правительство беспокоится об этой проблеме и уже построило несколько дорог, соединяющих наиболее важные города. Как всегда, остались города, до которых невозможно добраться по дорогам. Требуется построить новые дороги так, чтобы можно было проехать по дорогам от любого города до любого другого.

Города во Флатопии пронумерованы от 1 до N и город с номером i имеет декартовы координаты (x_i, y_i). Каждая дорога соединяет ровно два города. Все дороги (уже построенные и те, которые собираются построить) лежат на прямых линиях и их длина равна декартовому расстоянию между городами. Все дороги имеют двухстороннее движение. Дороги могут пересекаться, но водитель может переезжать с дороги на дорогу только в городах.

Правительство Флатопии хочет минимизировать стоимость постройки новых дорог. При этом, они хотят, чтобы все города были достижимы по дорогам. Так как Флатопия является плоской, то стоимость постройки дороги пропорциональна её длине. Поэтому, в целях экономии, требуется минимизировать суммарную длину построенных дорог.

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

Первая строка входного файла содержит единственное целое число N (1 <= N <= 750), обозначающее число городов. Следующие N строк содержат по два целых числа, x_i и y_i, разделённых пробелом. Эти числа являются координатами соответствующих городов (для i от 1 до N). Координаты по модулю не превосходят 10000. Никакие два города не совпадают.

Следующая строка содержит одно число M (0 <= M <= 1000), представляющее количество уже построенных дорог. Следующие M строк содержат по два целых числа, разделённых пробелом. Эти два числа обозначают пару городов, которые уже соединены дорогами. Каждая пара соединена не более чем одной дорогой.

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

По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 01, Р – 001. Для трёх оставшихся букв Б, Н и А кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова БАРАБАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, Д, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Р – 1, К – 0000. Для четырёх оставшихся букв А, В, Д и Н кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАРАВАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Л, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Ч – 1, Л – 011. Для трёх оставшихся букв А, З и К кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЧАЛКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, Д, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Р – 1, К – 0000. Для четырёх оставшихся букв А, В, Д и Н кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАРАВАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: Г, Д, К, С, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: С – 0, К – 1011. Для четырёх оставшихся букв Г, Д, О и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОСОГОР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

По каналу связи передаются сообщения, содержащие только буквы из набора: В, Д, К, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 0, К – 1001. Для четырёх оставшихся букв В, Д, О и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОНОВОД, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
 

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 1010; Б – 1100;
В – 0.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
 
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
 

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 1110;
В – 1010.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
 
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
 

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У.
Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
 

Буква	Кодовое слово		Буква	Кодовое слово
А	00		Л	1001
Б	1000		Р
Е	010		С	1010
И	011		Т	1101
К	1011		У	111

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

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

В	00
Г	10
Д	010
Е	110
Ж	0110
З	111

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

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

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

Входные данные
Содержит единственное число - степень кубооктаэдра 0 <= N <= 100000

Выходные данные
Вывести одно число - количество кубиков для кубооктаэдра степени N.

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

А	000
Б	001
В	0101
Г	0100
Д	011
Е	101

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

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

В	00
Г	1000
Д	111
Е	1001
Ж	01
З	110

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