Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

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

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

(Время: 1 сек. Память: 16 Мб Баллы: 100)
Окружность

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
154
21720

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

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


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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1240134
794041
4410
21234
5678
No solution

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

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

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

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


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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1010011 Maru
100010 Solar
000001 Curious
111001 Zest
001001 TY
011100 Sos
Maru
TY
Zest
2000010 Snute
001010 Happy
000101 ByuL
110000 Polt
010001 Classic
001100 Lilbow
Undefined

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

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

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


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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1After a storm comes a calmAtefr a srtom cmeos a clam
2Adversity is a great teacherAvtdirsey is a geart taehecr
3All asses wag their earsAll asess wag teihr eras

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

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

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


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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
143
010
101
010
295
01010
10001
00100
10001
01010
312345671573

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

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

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



Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483