Результаты олимпиады по программированию в ШГПИ
(25 апреля 2007 года)

В олимпиаде по программированию, проходившей 25 апреля 2007 года в ШГПИ, приняли участие студенты из Челябинска, Екатеринбурга, Тобольска и Шадринска. Было зарегистрировано 22 участника, из них 16 человек сдали работы, 10 человек набрали не менее 5 баллов из 40 возможных. Ниже приведена сводная таблица распределения баллов и мест:

ФИО

Повороты
(6)

Видеопамять (6)

Арифметика (8)

Менеджер пакетов (10)

Резидентура
(10)

Результат

1 место - ШГПИ, Кобелев Д.Г.

Решено

Решено

Решено

Решено, но сбой при наличии лишних пробелов в конце строк

-

6+6+8+9.5=29.5
(+3 балла за приз.место в заочной олимпиаде) =32.5

2 место - УрГПУ, Чурманов Е.В.

Решено

Решено

-

-

Решено

6+6+10=22

3 место - ЧГПУ, Запорожец А.В

-

Недорешано

-

Решено

Решено

0+10+10=20

3 место - ШГПИ, Щеколдин В.В.

Решено

Решено

Решено

Неверно

-

6+6+8=20

4 место - УрГПУ, Алексеевский П. И.

-

Иногда неверно

-

Решено

-

3+10=13

5 место - УрГПУ, Коновалов М.А.

Решено

Решено

-

-

-

6+6=12

6 место - ШГПИ, Кащенко П.А.

Решено

Иногда неверно

-

-

-

6+3=9

7 место - ШГПИ, Хохлов А.А.

Решено

-

-

-

-

6

8 место - УрГПУ, Ганиев Р.

Решено, но нестандарт в вводе-выводе

-

-

-

-

5.5

9 место - ЧГПУ, Зонтов А.С

-

-

-

Иногда неверно

-

5

Остальные участники получили менее 5 баллов


В процессе работы каждый студент имел возможность использовать веб-ориентированную систему Solver, расположенную на локальном сервере кафедры Программирования и сетевых технологий (http://pst/teachers/slinkin/web/ot/) для проверки правильности своих собственных решений. Из сети Интернет с данной системой и применением ее в решении олимпиадных задач можно ознакомиться по адресу http://shgpi.edu.ru/scripts/olimp2007/



Условия задач

Повороты

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: 6

Команда ШГПИ возвращалась с олимпиады из города Челябинска. От нечего делать я считал повороты автобуса. Когда мы приехали домой, я вдруг понял, что не запомнил, сколько было поворотов налево, а сколько направо. Я задал себе вопрос, можно ли зная, где автобус поворачивал (зная координаты перекрестка), определить количество "левых" и "правых" поворотов.

Итак, входной файл input.txt имеет следующую структуру: в начале идет число, которое определяет количество поворотов, а затем координаты мест (через запятую), где автобус поворачивал.

input.txt:
5
1,2
5,1
4,7
1,9
2,10

Выходной файл output.txt должен содержать всего одно число - количество поворотов налево.

output.txt:
2

Вместо файлов input.txt и output.txt можно использовать стандартные потоки ввода и вывода.



Видеопамять

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 6

В видеоадаптерах EGA и VGA, распространенных для IBM PC-совместимых систем в конце 20 века, использование больших объемов видеопамяти сдерживалось ограниченностью адресного пространства. Архитектура IBM PC предполагала, что видеопамять отображается на определенную область обычной памяти объемом максимум 64 килобайта. Таким образом, с первого взгляда становится невозможно использовать, например, графический режим 640x350, 16 цветов (640*350/2=112000 байт). В результате разработчики видеоадаптеров пошли на "хитрость". Всю видеопамять разделили на так называемые "плоскости", каждая из которых содержала данные только об одном из битов, из которых строится цвет точки. Таким образом, каждый байт плоскости содержал частичную информацию о 8 точках видеопамяти. Для 16-цветного графического режима таких плоскостей было 4 (по одной на каждый бит). Естественно, что каждая плоскость по отдельности умещалась в объем памяти 64 килобайта. С помощью регистров контроллера программист мог переключаться между плоскостями, манипулировать специальной битовой маской, с помощью которой удавалось выполнять запись данных сразу в несколько плоскостей и т.д.

Рассмотрим хранение 16 точек 16-цветного режима в 4 плоскостях видеоадаптеров EGA и VGA
Каждая из плоскостей будет содержать по 2 байта (2*8=16 битов)
129 1
128 2
130 3
1 4
В битовом представлении получим
10000001 00000001
10000000 00000010
10000010 00000011
00000001 00000100
Формируем цвет каждой точки из соответствующих четырех битов плоскостей.
0111 0000 0000 0000 0000 0000 0100 1001 0000 0000 0000 0000 0000 1000 0110 0101  
В десятичном представлении получаем коды цветов 16 точек:
7  0  0  0  0  0  4  9  0  0  0  0  0  8  6  5

Задание: Определить цвета точек по содержимому 4 плоскостей видеопамяти

Исходные данные (файл input.txt или стандартный входной поток):
4 строки, содержащие набор байтов (через пробел) каждой из плоскостей. Количество байтов в каждой строке одинаково.

Результирующие данные (файл output.txt или стандартный выходной поток):
Строка, в которой через пробел перечислены коды цветов полученного набора точек

Пример исходных данных 1:

129 1
128 2
130 3
1 4

Пример результирующих данных 1:

7  0  0  0  0  0  4  9  0  0  0  0  0  8  6  5

Пример исходных данных 2:

1 2 3
4 5 6
6 5 4
3 2 1

Пример результирующих данных 2:

0  0  0  0  0  6 12  9  0  0  0  0  0  6  9  6  0  0  0  0  0  6  3  9

Арифметика

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 8

Даны натуральные числа A,B и N. Определить все возможные способы получения числа B с помощью не более чем N бинарных арифметических операций +, -, *, / (под операцией / понимается целочисленное деление) над числом A. Найти также количество таких способов.

Исходные данные (файл input.txt или стандартный входной поток):
Числа A, B и N по одному в каждой строке.

Результирующие данные (файл output.txt или стандартный выходной поток):
Каждая строка содержит формулу с не более чем N операциями над числом A, вычисляемую в число B. Последняя строка содержит количество таких формул.

Пример исходных данных:

2
3
4

Пример результирующих данных:

((((2*2)*2)-2)/2)
((((2*2)-2)/2)+2)
(((2*2)+2)/2)
((((2*2)/2)/2)+2)
((((2-2)+2)/2)+2)
((((2+2)*2)-2)/2)
((((2+2)-2)/2)+2)
(((2+2)+2)/2)
((((2+2)/2)/2)+2)
((((2/2)*2)/2)+2)
((((2/2)-2)+2)+2)
((2/2)+2)
((((2/2)+2)*2)/2)
((((2/2)+2)-2)+2)
((((2/2)+2)+2)-2)
((((2/2)+2)/2)+2)
16

Менеджер пакетов

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 10

Во многих дистрибутивах ОС Linux для управления набором программного обеспечения используются так называемые 'менеджеры пакетов'. Принцип работы такого менеджера заключается в отслеживании зависимостей программных пакетов друг от друга и выполнения операций над ними таким образом, что вся система остается в непротиворечивом состоянии. Например, если пакет A зависит от пакета B, а пакет B зависит от пакета C, то при попытке установить пакет A предварительно будут установлены пакет С, а затем B. Аналогично, при попытке удаления пакета C предварительно будут удалены сначала пакет A, а затем B. Дополнительной задачей пакетного менеджера является проверка зависимостей пакетов на корректность, а именно - отсутствия циклов. Например, ситуацию зависимости пакета A от пакета B, а пакета B от пакета А менеджер пакетов считает некорректной и запрещает установку в систему этих пакетов.

Частично смоделируете поведение пакетного менеджера.

Исходные данные (файл input.txt или стандартный входной поток):
Для простоты будем нумеровать пакеты программного обеспечения натуральными числами от 1 до 100. Тогда первая строка входных данных содержит номер пакета, который требуется установить. Остальные строки содержат информацию о пакетах с их зависимостями в следующем виде:
номер_пакета номер_требуемого_пакета1 номер_требуемого_пакета2 ...
Предполагаем, исходный набор данных обладает целостностью, то есть все упомянутые в зависимостях пакеты в нем присутствуют.

Результирующие данные (файл output.txt или стандартный выходной поток):
Строка, в которой через пробел перечислены пакеты в порядке их установки. Таких последовательностей может быть несколько. Достаточно вывести одну из них.
Если в наборе зависимых по отношению к искомому пакетах обнаруживается цикл, вывод должен содержать только одну строку со словом Cycle.

Пример исходных данных 1:

1
3
2 1 3 5
1 2
4
5 1

Пример результирующих данных 1:

Cycle

Пример исходных данных 2:

5
3
2 3 6
1 2
4 
5 3 2 1
6

Пример результирующих данных 2:

3 6 2 1 5

Резидентура

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: 10

Рассмотрим следующую гипотетическую ситуацию. В некотором государстве работают N российских нелегальных агентов. В задачу этих агентов входит сбор ценной для нашего государства информации. Агенты могут обмениваться информацией друг с другом. Рассмотрим Рис. 1.


A

B

C

D

A

0

1

1

0

B

0

0

1

0

C

0

0

0

1

D

0

0

0

0

Рис. 1.

Мы взяли всего четырех агентов. Цифра 1 на пересечении строки X и столбца Y означает, что агент X получает информацию от агента Y (имеет односторонний канал). Цифра 0, означает, что канал получения информации отсутствует. В нашем случае агент A получает информацию от агентов B и C, агент B получает информацию от агента C, агент C получает информацию от агента D, агент D не имеет каналов получения информации от других агентов. Разумеется, наша руководство разведки заинтересовано, чтобы информация, добытая агентами, в конце концов, дошла до них. С другой стороны, чем меньше контактов будет между агентами и руководством, тем лучше. Таким образом, необходимо в общем случае найти минимальный набор агентов, контакт с которыми позволит получить всю информацию, добытую агентами. Например, в ситуации представленной на Рис. 1 достаточно контактировать только с агентом A, а в ситуации на Рис. 2 с агентами A и D.


A

B

C

D

A

0

1

1

0

B

0

0

0

0

C

0

0

0

0

D

0

0

0

0

Рис. 2.

Требования задачи.

Входной файл содержит строки одинаковой длины, состоящие из нулей и единиц (см. Рис. 3). Агенты нашей разведки, таким образом, нумеруются цифрами от 0 до N-1 (для варианта, представленного на рис. 3 - от 0 до 4).

00000
10100
00000
00001
00000

Рис. 3.

Необходимо найти группу с минимальным количеством агентов, с помощью которых можно получить всю добываемую информацию (всеми агентами). В выходном файле должны быть перечислены номера этих агентов. Например, для ситуации, изображенной на Рис. 3 выходной файл будет содержать строку из двух цифр "1 3" (не забывайте, что нумерация агентов от 0).

Имя входного файла input.txt (или стандартный поток ввода), имя выходного файла output.txt (или стандартный поток вывода).

Важные замечания.

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

2. В поставленной выше задаче имеется один серьезный момент. Дело в том, что в общем случае информационные потоки между агентами могут замыкаться. Например, агент A получает информацию от агента B, а агент B получает информацию от агента A. Или более сложный вариант: агент A получает информацию от агента B, агент B получает информацию от агента C, агент C получает информацию от агента D, а агент D получает информацию от агента A (круг замкнулся). В случае наличия замыкания должно быть выведено сообщение об ошибке.



  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
Наверх