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

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

HotLog


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

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

Задача A. Площадь прямоугольного треугольника

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

По длинам катетов прямоугольного треугольника требуется вычислить его площадь.

Напомним, что треугольник называется прямоугольным, если один из его углов – прямой (равен 90 градусов). Катетами прямоугольного треугольника называют стороны, смежные с прямым углом.

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

Входной файл INPUT.TXT содержит два целых положительных числа – длины катетов прямоугольного треугольника, не превосходящие 109.

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

В выходной файл OUTPUT.TXT выведите точное значение площади треугольника с одной цифрой после запятой. Следуйте согласно формату, приведенному в примерах.

Примеры

INPUT.TXTOUTPUT.TXT
13 46.0
25 717.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.TXTOUTPUT.TXT
12 51
2-7 -33
30 41 2

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

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


Задача C. Игра в города

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

Шрек и Румпельштильцхен играют в популярную игру «Города», в которой каждый участник в свою очередь называет город, название которого начинается на ту букву, которой оканчивается название предыдущего участника. Игроки делают свои ходы поочередно. Первым начинает Шрек и он называет любой город, начинающийся с любой буквы. Проигрывает тот, кто не сможет в свою очередь назвать очередной город согласно правилам игры.

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

По заданному списку городов, которые называли в процессе игры Шрек и его напарник, необходимо определить победителя.

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество названных городов (N ≤ 100). Далее следует N строк, в каждой из которых записано название очередного города длинной от 1 до 20 символов английского алфавита: первая буква – большая, остальные – строчные.

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

В первой строке выходного файла OUTPUT.TXT выведите количество корректно названных игроками городов. Во второй строке выведите «Shrek», если победил Шрек и «Rumpelstiltskin» в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
17
Achinsk
Krasnoyarsk
Kozulka
Abakan
Norilsk
Kansk
Kedroviy
7
Shrek
25
Borodino
Orlovka
Uzhur
Rodniki
Ilanskiy
2
Rumpelstiltskin

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

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


Задача D. Казино

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

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

Спустя несколько лет, Василий Петрович нашел свои записи и его заинтересовал вопрос: какой промежуток времени в том периоде игры для него был наиболее благоприятным? Иными словами, его интересовала максимальная прибыль, которую он получил в некотором временном диапазоне за один или более дней.

Помогите Василию Петровичу решить поставленную задачу.

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество дней, на протяжении которых Василий Петрович играл в казино (N ≤ 105). Вторая строка содержит N целых чисел, соответствующих прибыли в рублях с игры за каждый день (отрицательные значения означают проигрыш в данный день). Известно, что за один день Василий Петрович никогда не выигрывал и никогда не проигрывал более 1000 рублей.

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

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

Пример

INPUT.TXTOUTPUT.TXT
115
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 до Cmax – цвета стран после раскраски. Здесь Cmax – минимально возможное количество цветов, необходимых для раскраски. Если возможных вариантов раскраски несколько, выведите любой из вариантов.

Примеры

INPUT.TXTOUTPUT.TXT
13
0 1 0
1 0 0
0 0 0
1 2 1
217
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0
1 2 1 1 1 2 3 1 2 3 1 2 1 2 1 2 3

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

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



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