Задачи олимпиады "Муниципальный этап ВОШ Красноярского края по информатике, 7-8 классы"
Задача A. Площадь прямоугольного треугольника
(Время: 1 сек. Память: 16 Мб Баллы: 100)
По длинам катетов прямоугольного треугольника требуется вычислить его площадь.
Напомним, что треугольник называется прямоугольным, если один из его углов – прямой (равен 90 градусов). Катетами прямоугольного треугольника называют стороны, смежные с прямым углом.
Входные данные
Входной файл INPUT.TXT содержит два целых положительных числа – длины катетов прямоугольного треугольника, не превосходящие 109.
Выходные данные
В выходной файл OUTPUT.TXT выведите точное значение площади треугольника с одной цифрой после запятой. Следуйте согласно формату, приведенному в примерах.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 4
6.0
2
5 7
17.5
Система оценки
Решения, округленные до целого значения, будут оцениваться в 40 баллов.
Решения, работающие для катетов с длинами до 104, будут оцениваться в 60 баллов.
Задача B. Координатная четверть
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Известно, что OX и OY – оси абсцисс и ординат делят плоскость на 4 четверти и каждая точка с координатами (x,y) либо принадлежит одной из четвертей, либо находится между таковыми (в случае ее принадлежности одной из осей координат).
Принадлежность точки с координатами (x,y) к одной из четвертей определяется следующим образом:
для первой четверти x ≥ 0 и y ≥ 0;
для второй четверти x ≤ 0 и y ≥ 0;
для третьей четверти x ≤ 0 и y ≤ 0;
для четвертой четверти x ≥ 0 и y ≤ 0.
По заданным координатам точки на плоскости требуется определить четверть, в которой она лежит.
Входные данные
Входной файл INPUT.TXT содержит два целых числа X и Y – координаты точки на плоскости. Координаты не превосходят 1000 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – номер четверти, в которой лежит данная точка. В том случае, когда точка лежит на одной из осей, следует вывести в порядке возрастания все четверти, между которыми она находится.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 5
1
2
-7 -3
3
3
0 4
1 2
Система оценки
Решения, верно работающие только для точек, не принадлежащих осям координат, будут оцениваться в 50 баллов.
Задача C. Игра в города
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Шрек и Румпельштильцхен играют в популярную игру «Города», в которой каждый участник в свою очередь называет город, название которого начинается на ту букву, которой оканчивается название предыдущего участника. Игроки делают свои ходы поочередно. Первым начинает Шрек и он называет любой город, начинающийся с любой буквы. Проигрывает тот, кто не сможет в свою очередь назвать очередной город согласно правилам игры.
Все называемые игроками сказочные города существуют, и игроки называют их без повторов. Известно, что в процессе игры как Шрек, так и Румпельштильцхен могут ошибаться, называя город не по правилам, используя неверную первую букву. В этом случае, очевидно, проигрывает тот, кто совершает подобную ошибку.
По заданному списку городов, которые называли в процессе игры Шрек и его напарник, необходимо определить победителя.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество названных городов (N ≤ 100). Далее следует N строк, в каждой из которых записано название очередного города длинной от 1 до 20 символов английского алфавита: первая буква – большая, остальные – строчные.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите количество корректно названных игроками городов. Во второй строке выведите «Shrek», если победил Шрек и «Rumpelstiltskin» в противном случае.
Решения, не анализирующие возможные ошибки игроков, будут оцениваться в 30 баллов.
Задача D. Казино
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Василий Петрович – очень азартный человек. В свое время, когда игра в казино была разрешена и общедоступна, Василий Петрович на протяжении значительного периода времени играл в рулетку ежедневно. При этом он вел статистику своих побед и поражений, результаты которых отмечал в записной книжке.
Спустя несколько лет, Василий Петрович нашел свои записи и его заинтересовал вопрос: какой промежуток времени в том периоде игры для него был наиболее благоприятным? Иными словами, его интересовала максимальная прибыль, которую он получил в некотором временном диапазоне за один или более дней.
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество дней, на протяжении которых Василий Петрович играл в казино (N ≤ 105). Вторая строка содержит N целых чисел, соответствующих прибыли в рублях с игры за каждый день (отрицательные значения означают проигрыш в данный день). Известно, что за один день Василий Петрович никогда не выигрывал и никогда не проигрывал более 1000 рублей.
Выходные данные
В выходной файл OUTPUT.TXT выведите максимальную прибыль, которую получил Василий Петрович в свой наиболее благоприятный период времени.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
15
4 -5 2 5 -6 8 4 -9 13 0 8 -13 -5 20 -2
27
Пояснение к примеру
В общем периоде игры в 15 дней наиболее благоприятным для Василия Петровича был промежуток с 3-го по 14-й день, в который он заработал 27 рублей.
Система оценки
Решения, работающие для N ≤ 100 будут оцениваться в 40 баллов.
Решения, работающие для N ≤ 3000 будут оцениваться в 80 баллов.
Задача E. Раскраска карты
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Задана контурная карта, на которой расположено несколько стран. Требуется ее раскрасить, используя минимально возможное количество цветов таким образом, чтобы любые страны с общей границей были окрашены в разный цвет.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество стран на карте (N ≤ 20). В следующих N строках располагается матрица смежности: каждая (i+1)-я строка содержит разделенные пробелом N цифр – информацию о смежных государствах i-й страны. В (i+1)-й строке в j-й позиции записана цифра 1, если страны с номерами i и j имеют общую границу и 0 – в противном случае. Страны нумеруются от 1 до N. Гарантируется, что такое расположение стран возможно отобразить на плоскости.
Выходные данные
В выходной файл OUTPUT.TXT выведите N целых чисел от 1 до M – цвета стран после раскраски. Здесь M – минимально возможное количество цветов, необходимых для раскраски. Если возможных вариантов раскраски несколько, выведите любой из вариантов.
