древнейших шифров разработал Полибий (III ст. к н.е.) - греческий историк, полководец, государственный деятель. В шифре, который назвали “квадрат Полибия”, каждая буква алфавита (или пара букв, соответствующих близким по произношению звукам) содержится в таблице. Во время кодирования сообщения каждая буква заменяется парой чисел номерами столбца и строки таблицы, на пересечении которых она размещена. Для кодирования сообщений на английском языке может быть использована таблица.
Слово CODE в закодированном виде 31 43 41 51
Входные данные:
В первой строке файла polybius.dat записано целое число N (0<N<100). В следующих N строках через пробел записано целое число L - длина слова (0<L<256) и шифры букв с данной таблицы Полибия.
Выходные данные:
файл polybius.sol нужно вывести декодируемые слова заглавными латинскими буквами, каждое в отдельной строке в той же последовательности, как они записаны в файле polybius.dat.
Примеры
Входные данные Выходные данные
2
4 22 43 43 41
4 13 54 31 52 GOOD
LUCK
Задача B. "День рождения"
Пес Шарик любит рыбные котлеты. На свой День рождения он решил всех угостить друзей рыбными котлетами. Пес посчитал, что ему нужно N рыбин. (0<N<1000). Пес - рыбак со стажем, поэтому каждый день он совершенствуется и ловит на S (0<S<N) рыбин больше, чем в предыдущий день. В первый день пес традиционно ловит K (0<K<N) рыбин. Но кот Матроскин любит живую рыбу и всегда съедает половину улова за день. Если количество рыб в улове за день нечетное, тогда кот съедает меньше на одну рыбину чем оставляет. Зная привычку кота, пес Шарик пытается определить за сколько дней до дня рождения ему нужно отправиться на рыбалку, чтобы наловить нужное количество рыбин и не поссориться с котом - главным гостем на его дне рождения.
Входные данные:
В стандартном входном потоке через пробел записано три целых числа N, S, K.
Выходные данные:
В стандартный выходной поток вывести наименьшее число дней, которые нужны псу, чтобы наловить необходимое количество рыбин и не поссориться с котом.
Примеры
Входные данные Выходные данные
20 2 3 5
Задача С. "Сервер"
На сервере хранится информация о работе клиентов в сети. Информация записывается в следующем виде: первые четыре числа указывают адрес с которой обращается программа-клиент, а следующие четыре - по какому адресу обращается. Нужно установить адрес самого активного клиента и адреса всех ресурсов к которым он обращался. Гарантированно, активный только один.
Входные данные:
В стандартном входном потоке в первой строке записано целое число N (0<N<1000) в следующих N строках по восемь целых чисел, значение которых от 0 до 255.
Выходные данные:
В стандартный выходной поток в первой строке нужно вывести четыре числа через точку (адрес самого активного клиента) и в следующей строке подряд 15 символов "-", в следующих строках - количество обращений, пробел, символ "-", пробел и адрес. Адреса посещение выводить по убыванию количества посещений, а если одинаковое количество посещений нужно выводить в порядке возрастания адреса.
Примеры
Входные данные Выходные
2 - 46.63.83.191
1 - 46.63.83.192
1 - 46.63.83.193
и их количество возрастает на 1 с уменьшением от единственного крупнейшего корабля и заканчивая одноклеточными кораблями. Например, если P=4, тогда количество кораблей 10. 1 корабль – 4 клетки, 2 корабля по 3 клетки, 3 корабля по 2 клетки 4 корабля по 1 клетке.
Зная координаты расположения кораблей и шаг N-1 нужно рассчитать наименьшее количество ходов, которая позволит поразить все корабли хотя бы один раз. Шаг выстрелов начинается от левого верхнего угла игрового поля – ячейки с координатами 1 1, то есть ячейки 1 N-1 . При достижении края игрового поля шаги отсчитываются пробел записаны два целых числа N, P.
В следующих строках через пробел записано по четыре целых числа – координаты расположения кораблей, координаты его начала и конца (x1<=x2, y1<=y2).
Выходные данные:
файл battleship.sol нужно вывести единственное число – количество выстрелов.
Примеры
Входные данные Выходные данн
Дано прямоугольную таблицу размером N на M (0<N, M<50). В некоторых ячейках таблицы записано число 0, а в некоторых -1. 0 – ячейка свободна и в нее можно переместиться, -1 – ячейка с препятствием и телепортироваться в эту ячейку нельзя. Ваша задача-найти наименьшее число шагов между указанными ячейками. За один шаг можно двигаться только в соседние горизонтальные или вертикальные ячейки, не допускается диагональный движение. Нумерация строк и столбцов таблицы начинается с 1.
Входные данные:
В стандартном входном потоке в первой строке через пробел вводятся два числа N M. Во второй строке через пробел записаны координаты начальной и конечной ячеек. В следующих N строках через пробел записано по M чисел 0 или -1.
Выходные данные:
В стандартный выходной поток вывести наименьшее количество шагов для перемещения из одной ячейки в другую. Если пути не существует, необходимо вывести слово No
Если речь о результатах, то в компьютерной арифметике числа представляются в двоичном коде, а точность их представления обычно ограничена разрядностью процессора. Для проведения расчетов с неограниченной точностью используются специальные алгоритмы с представлением чисел в виде символьных строк. При использовании двоичной арифметики приходится сталкиваться с тем, что большинство нецелых чисел невозможно точно представить в двоичной системе, как нельзя, например, в десятичной системе точно представить в виде десятичной дроби число 1/3 = 0.333 Рассмотрим пример. Если в простых дробях (1/3) х 3 = 1, то в десятичных 0.3333 х 3 = 0.9999. В двоичной машинной арифметике происходит аналогичная ситуация. Но если человек сознает, что результат 0.9999... - та же единица, то компьютер этого не понимает. В результате в компьютерной арифметике (1 / 3) х 3 не равняется единице. Еще пример. Пусть нам надо вычислить значение функции в точках от -2π до 2π с шагом π/6. Человек будет использовать значения -2π, -11π/6, -10π/6 и т.д. пока не придет к точке 2π. Компьютер (в арифметике с обычной точностью) вычислит значение -2π как -6.283185, а шаг представит значением 0.5235988. Это приведет к тому, что когда мы придем к нулю, то получим значение аргумента -9.536743х10⁻⁷, а в конечной точке получим аргумент 6.283184, который по абсолютной величине отличается от начального на единицу в младшей цифре, т.е. для компьютера при таком последовательном счете |-2π| ≠ 2π. Третий пример. отрицательные целые числа представляются в компьютере в дополнительном коде, когда старший разряд является знаковым: 0 - это плюс, 1 - это минус. Пусть мы прибавляем к 127 единицу в арифметике целых чисел, которым в двоичном представлении отведен один байт: 1111111₂ + 1₂ = 10000000₂ - тут все понятно, единичка перешла в старший, восьмой разряд. Но ведь он ЗНАКОВЫЙ! И вместо двоичного эквивалента 128 в компьютерной арифметике мы получаем отрицательное число! Причем, что самое интересное, из соображений эффективности эта ситуация обычно аппаратно не контролируется и в результате программы могут вести себя очень странно.
древнейших шифров разработал Полибий (III ст. к н.е.) - греческий историк, полководец, государственный деятель. В шифре, который назвали “квадрат Полибия”, каждая буква алфавита (или пара букв, соответствующих близким по произношению звукам) содержится в таблице. Во время кодирования сообщения каждая буква заменяется парой чисел номерами столбца и строки таблицы, на пересечении которых она размещена. Для кодирования сообщений на английском языке может быть использована таблица.
Слово CODE в закодированном виде 31 43 41 51
Входные данные:
В первой строке файла polybius.dat записано целое число N (0<N<100). В следующих N строках через пробел записано целое число L - длина слова (0<L<256) и шифры букв с данной таблицы Полибия.
Выходные данные:
файл polybius.sol нужно вывести декодируемые слова заглавными латинскими буквами, каждое в отдельной строке в той же последовательности, как они записаны в файле polybius.dat.
Примеры
Входные данные Выходные данные
2
4 22 43 43 41
4 13 54 31 52 GOOD
LUCK
Задача B. "День рождения"
Пес Шарик любит рыбные котлеты. На свой День рождения он решил всех угостить друзей рыбными котлетами. Пес посчитал, что ему нужно N рыбин. (0<N<1000). Пес - рыбак со стажем, поэтому каждый день он совершенствуется и ловит на S (0<S<N) рыбин больше, чем в предыдущий день. В первый день пес традиционно ловит K (0<K<N) рыбин. Но кот Матроскин любит живую рыбу и всегда съедает половину улова за день. Если количество рыб в улове за день нечетное, тогда кот съедает меньше на одну рыбину чем оставляет. Зная привычку кота, пес Шарик пытается определить за сколько дней до дня рождения ему нужно отправиться на рыбалку, чтобы наловить нужное количество рыбин и не поссориться с котом - главным гостем на его дне рождения.
Входные данные:
В стандартном входном потоке через пробел записано три целых числа N, S, K.
Выходные данные:
В стандартный выходной поток вывести наименьшее число дней, которые нужны псу, чтобы наловить необходимое количество рыбин и не поссориться с котом.
Примеры
Входные данные Выходные данные
20 2 3 5
Задача С. "Сервер"
На сервере хранится информация о работе клиентов в сети. Информация записывается в следующем виде: первые четыре числа указывают адрес с которой обращается программа-клиент, а следующие четыре - по какому адресу обращается. Нужно установить адрес самого активного клиента и адреса всех ресурсов к которым он обращался. Гарантированно, активный только один.
Входные данные:
В стандартном входном потоке в первой строке записано целое число N (0<N<1000) в следующих N строках по восемь целых чисел, значение которых от 0 до 255.
Выходные данные:
В стандартный выходной поток в первой строке нужно вывести четыре числа через точку (адрес самого активного клиента) и в следующей строке подряд 15 символов "-", в следующих строках - количество обращений, пробел, символ "-", пробел и адрес. Адреса посещение выводить по убыванию количества посещений, а если одинаковое количество посещений нужно выводить в порядке возрастания адреса.
Примеры
Входные данные Выходные
2 - 46.63.83.191
1 - 46.63.83.192
1 - 46.63.83.193
и их количество возрастает на 1 с уменьшением от единственного крупнейшего корабля и заканчивая одноклеточными кораблями. Например, если P=4, тогда количество кораблей 10. 1 корабль – 4 клетки, 2 корабля по 3 клетки, 3 корабля по 2 клетки 4 корабля по 1 клетке.
Зная координаты расположения кораблей и шаг N-1 нужно рассчитать наименьшее количество ходов, которая позволит поразить все корабли хотя бы один раз. Шаг выстрелов начинается от левого верхнего угла игрового поля – ячейки с координатами 1 1, то есть ячейки 1 N-1 . При достижении края игрового поля шаги отсчитываются пробел записаны два целых числа N, P.
В следующих строках через пробел записано по четыре целых числа – координаты расположения кораблей, координаты его начала и конца (x1<=x2, y1<=y2).
Выходные данные:
файл battleship.sol нужно вывести единственное число – количество выстрелов.
Примеры
Входные данные Выходные данн
Дано прямоугольную таблицу размером N на M (0<N, M<50). В некоторых ячейках таблицы записано число 0, а в некоторых -1. 0 – ячейка свободна и в нее можно переместиться, -1 – ячейка с препятствием и телепортироваться в эту ячейку нельзя. Ваша задача-найти наименьшее число шагов между указанными ячейками. За один шаг можно двигаться только в соседние горизонтальные или вертикальные ячейки, не допускается диагональный движение. Нумерация строк и столбцов таблицы начинается с 1.
Входные данные:
В стандартном входном потоке в первой строке через пробел вводятся два числа N M. Во второй строке через пробел записаны координаты начальной и конечной ячеек. В следующих N строках через пробел записано по M чисел 0 или -1.
Выходные данные:
В стандартный выходной поток вывести наименьшее количество шагов для перемещения из одной ячейки в другую. Если пути не существует, необходимо вывести слово No
При использовании двоичной арифметики приходится сталкиваться с тем, что большинство нецелых чисел невозможно точно представить в двоичной системе, как нельзя, например, в десятичной системе точно представить в виде десятичной дроби число 1/3 = 0.333
Рассмотрим пример. Если в простых дробях (1/3) х 3 = 1, то в десятичных 0.3333 х 3 = 0.9999.
В двоичной машинной арифметике происходит аналогичная ситуация. Но если человек сознает, что результат 0.9999... - та же единица, то компьютер этого не понимает. В результате в компьютерной арифметике (1 / 3) х 3 не равняется единице.
Еще пример. Пусть нам надо вычислить значение функции в точках от -2π до 2π с шагом π/6. Человек будет использовать значения -2π, -11π/6, -10π/6 и т.д. пока не придет к точке 2π. Компьютер (в арифметике с обычной точностью) вычислит значение -2π как -6.283185, а шаг представит значением 0.5235988. Это приведет к тому, что когда мы придем к нулю, то получим значение аргумента -9.536743х10⁻⁷, а в конечной точке получим аргумент 6.283184, который по абсолютной величине отличается от начального на единицу в младшей цифре, т.е. для компьютера при таком последовательном счете |-2π| ≠ 2π.
Третий пример. отрицательные целые числа представляются в компьютере в дополнительном коде, когда старший разряд является знаковым: 0 - это плюс, 1 - это минус.
Пусть мы прибавляем к 127 единицу в арифметике целых чисел, которым в двоичном представлении отведен один байт:
1111111₂ + 1₂ = 10000000₂ - тут все понятно, единичка перешла в старший, восьмой разряд. Но ведь он ЗНАКОВЫЙ! И вместо двоичного эквивалента 128 в компьютерной арифметике мы получаем отрицательное число! Причем, что самое интересное, из соображений эффективности эта ситуация обычно аппаратно не контролируется и в результате программы могут вести себя очень странно.