Городская олимпиада

В городе прошла олимпиада по информатике, вернее по программированию.  Одни  и те же  задачи предложены учащимся 9 - 11 классов. Информатика  - наука, содержащая большое количество разделов. Это логика, моделирование, кодирование информации, программирование, компьютер и программное обеспечение, информационные и коммуникационные технологии. Однако, нам ежегодно предлагают олимпиаду только по программированию. Кому это выгодно? Почему мы в таких "усеченных" условиях? Предлагаю познакомиться с олимпиадными заданиями и высказать свое мнение по поводу этого мероприятия. Обратите внимание,  олимпиада, все-таки, по информатике!

Задания муниципального этапа всероссийской олимпиады школьников 2009-2010 учебного года по информатике

9-11 классы

Задача A. Умные слоны

Имя входного файла:      a.in

Имя выходного файла:   a.out

Некоторые люди считают, что чем слон больше, тем он умнее. Чтобы опровергнуть это утверждение, вы хотите проанализировать набор слонов и найти наибольшую (по длине) подпоследовательность слонов  с увеличивающимся весом, но уменьшающимся IQ

Требования.

Выведите множество слонов, удовлетворяющее заданным условиям.

Формат входных данных (a.in).

Входные данные состоят из данных о наборе слонов, по одному слону на строку, и завершаются меткой конца файла. Данные о каждом конкретном слоне состоят из двух целых чисел: первое – это вес слона в килограммах, второе – его IQ. Оба числа лежат в пределах от 1 до 10 000. Во входных данных содержится информация не более чем о 1000 слонах. У двух слонов могут быть одинаковыми: вес, IQ или даже и вес, и IQ.

Формат выходных данных (a.out).

Первая строка выходных данных должна содержать целое число n – длину найденной последовательности слонов. Каждая из оставшихся n строк должна содержать единственное целое число, задающее слона. Обозначим числа на i-й строке выходных данных  как W[i] и S[i]. Если ваша последовательность состоит из n слонов a[1], a[2],…, a[n], то должны выполняться следующие условия:

W[a[1]] < W[a[2]]< … < W[a[n]] и S[a[1]] > S[a[2]] > … > S[a[n]]

Ваша программа может вывести любой верный ответ из возможных для заданных входных данных.

Примеры входного и выходного файлов:

a.in	a.out
6008 13006000 2100500 2000 1000 4000 1100 3000 6000 2000 8000 1200 2000 1900	445 8 7

Задача B. Железные дороги

Имя входного файла:      b.in

Имя выходного файла:   b.out

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

Требования.

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

Формат входных данных (a.in).

Входной файл состоит из трех частей. Первая часть содержит все города, соединенные между собой железными дорогами. Она начинается с числа 1 < C £ 100, за которым следуют С строк, содержащие названия городов. Все имена состоят из букв.

Вторая часть описывает маршруты поездов, отправляющиеся в течения дня. Она начинается с числа T £ 1000, за которым следуют T описаний поездов. Каждое состоит из строки, содержащей количество остановок Ti £ 100. За ней следуют еще Ti строк, каждая из которых состоит из времени и названия города, в котором останавливается поезд. Пассажиры могут сходить с поезда и садиться на него в  указанное время и в этом городе, т.е. время стоянки равно 0. Время задается в формате ЧЧММ.

Последняя часть состоит из трех строк: первая содержит самое раннее возможное время отправления Боба из города А, вторая –название города А, а третья – города Б. Начальный город никогда не совпадает с местом назначения.

Формат выходных данных (a.out).

Если подходящие пересадки существуют, то выведите, как показано в примере, две строки, содержащие временные метки и названия городов. Для отступов используйте пробелы. Если подходящих пересадок в этот день (то есть прибытие до полуночи) не нашлось, выведите строку, содержащую “No connection”.

Примеры входного и выходного файлов:

a.in	a.out
3HamburgFrankfurt Darmstadt 3 2 0949 Hamburg 1006 Frankfurt 2 1325 Hamburg 1550 Darmstadt 2 1205 Frankfurt 1411 Darmstadt 0800 Hamburg Darmstadt	Departure 0949 HamburgArrival 1411 Darmstadt
2ParisTokyo 1 2 0100 Paris 2300 Tokyo 0800 Paris Tokyo	No connection

 Задача C. Вырубка деревьев

 

Имя входного файла:      c.in

Имя выходного файла:   c.out

 

Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Требуется написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга (1 ≤ m ≤ n ≤ 1000).

Требования.

Найдите количество способов вырубки деревьев.

Формат входных данных (с.in).

В файле содержатся числа n и m (1 ≤ m ≤ n ≤ 1000).

Формат выходных данных (с.out).

В выходном файле должно быть только одно число – количество способов вырубки деревьев.

Примеры входных и выходных данных

c.in

c.out

Пояснение к первому примеру

Если обозначить условно исходное расположение деревьев перед дворцом как «TTTTT», то возможные результаты после вырубки следующие: «TTT..», «.TTT.», «..TTT», «T.T.T».

Задача D. Треугольники

Имя входного файла:      d.in

Имя выходного файла:   d.out

На плоскости расположено два равносторонних  треугольников, у которых одна из сторон параллельна оси OX.

Требования.

Найти пересечение этих треугольников, если оно существует.

Формат входных данных (d.in).

В первой строке три целых числа: x1, x2, y. Эти числа задают координаты вершин основания первого треугольника, т.е. точка (x1,y) и (x2,y) это координаты основания первого равностороннего треугольника. Во второй строке аналогично задан второй треугольник.

Формат выходных данных (d.out).

Вывести в файл число S равное площади пересечения этих двух треугольников.  Точность – 3 знака после запятой.

Примеры входного и выходного файлов:

d.in

d.out

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