Задачи олимпиады "Муниципальный этап ВОШ Красноярского края по информатике, 9-11 классы"

Задача A. Окружность

В центре системы координат находится окружность длины L.

Требуется определить количество пересечений окружности с координатной сеткой.

Входные данные

Входной файл INPUT.TXT содержит натуральное число L (L ≤ 10¹⁸) – длину окружности.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Система оценки

Решения, работающие верно для L ≤ 25, будут оцениваться в 30 баллов.

Задача B. Максимальное число

Заданы два целых неотрицательных числа A и B.

Требуется найти такое максимально возможное целое число C, которое можно составить как из цифр числа A, так и из цифр числа B.

Входные данные

Входной файл INPUT.TXT содержит два целых неотрицательных числа A и B по одному в каждой строке. Каждое из чисел состоит не более чем из 10⁵ цифр.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число C – ответ на задачу. Если такого числа не существует, выведите «No solution» (без кавычек).

Примеры

Система оценки

Решения, правильно работающие только для чисел, состоящих не более чем из 6 цифр, будут оцениваться в 20 баллов.

Решения, правильно работающие только для чисел, состоящих не более чем из 9 цифр, будут оцениваться в 40 баллов.

Решения, правильно работающие только для чисел, состоящих не более чем из 1000 цифр, будут оцениваться в 60 баллов.

Задача C. Киберспорт

В киберспорте используется множество систем проведения соревнований. Не так давно для игры StarCraft II была введена новая система отбора трех человек из шести на групповой стадии.

Система напоминает круговую: каждый играет с каждым две игры. При этом в такой дуэли один из матчей проходит для каждого игрока на своей выбранной карте (домашняя игра), а другой – на карте, выбранной соперником (гостевая игра). Всего получается 30 игр в турнире. В результате более высокую позицию занимает тот, кто одержит больше побед, если число побед совпадает, то преимущество получает тот, у кого больше побед на гостевых картах, если же и эти параметры равны, то учитывается показатель личных встреч. Если согласно этим правилам в результате невозможно определить первую тройку победителей, то проводятся переигровки.

Требуется написать программу, которая по результатам 30 игр определяет тройку победителей, либо определяет, что нужны дополнительные игры.

Входные данные

Входной файл INPUT.TXT содержит турнирную таблицу 6 x 6. В i-й строке сначала идут 6 цифр «0» или «1» (без пробелов) – информация об играх i-го игрока на домашних картах, далее через пробел – имя (ник) игрока. На главной диагонали таблицы стоят нули. Если в i-й строке и j-м столбце стоит «1», то это означает, что i-й игрок одержал победу над j-м на домашней карте, «0» обозначает проигрыш. Все имена – строки, состоящие не более чем из 10 английских символов.

Выходные данные

В выходной файл OUTPUT.TXT выведите тройку победителей в алфавитном порядке или слово «Undefined» (без кавычек), если победителей определить невозможно.

Примеры

Система оценки

Решения, учитывающие только число выигранных игр, будут оцениваться в 40 баллов.

Решения, определяющие победителей только по числу выигранных игр и по числу выигранных игр на гостевых картах, будут оцениваться в 60 баллов.

Задача D. Нортландский шифр

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

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

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

Входные данные

Входной файл INPUT.TXT содержит строку, состоящую из слов, разделенных пробелом. Слова состоят из строчных и прописных букв английского алфавита. Максимальная длина строки – 10⁵ символов.

Выходные данные

В выходной файл OUTPUT.TXT выведите зашифрованный текст в формате, схожем с форматом входных данных.

Примеры

Система оценки

Решения, работающие для текста, в котором каждое слово состоит из различных букв, будут оцениваться в 30 баллов.

Решения, предполагающие, что во входных данных все слова состоят менее чем из 10 букв, будут оцениваться в 50 баллов.

Задача E. Красивая матрица

Квадратная матрица – двумерный массив (таблица), составленный из N строк и N столбцов. Строки и столбцы матрицы нумеруются от 1 до N. Число N называют порядком матрицы.

Симметричная матрица – квадратная матрица A порядка N, которая симметрична своему горизонтальному и вертикальному отражению. Более формально: для любой пары (i,j) (1 ≤ i,j ≤ N) верно, что A_i,j = A_N-i+1,j и A_i,j = A_i,N-j+1.

Красивая матрица – симметричная матрица, составленная из нулей и единиц таким образом, что никакие две клетки, содержащие единицы, не имеют общей стороны.

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

Входные данные

Входной файл INPUT.TXT содержит единственное число K (1 ≤ K ≤ 10¹⁹) – количество единиц в матрице.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите число N – порядок матрицы. Если K ≤ 10⁶, то в последующих N строках выведите N цифр в каждой строке без пробелов – искомую матрицу. Если существует несколько решений, выведите любое.

Примеры

Система оценки

Решения, работающие только для K ≤ 20, будут оцениваться в 20 баллов.

Решения, работающие только для K ≤ 10⁶, будут оцениваться в 70 баллов.