Курчатовская Олимпиада по информатике 2011 года

Правила проведения

Курчатовская олимпиада по информатике состоит из двух туров: заочного и очного. Очный тур будет происходить в Москве, в конце февраля/начале марта 2011 года. Отбор участников очного тура происходит по результатам заочного тура. В олимпиаде может принимать участие любой школьник, обучающийся в 1-11 классе любой школы России.

Правила проведения заочного тура таковы: желающим предлагаются две задачи, которые решаются дома, и не позднее 24 февраля 2011 года решения отсылаются по электронному адресу olymp11[at]inse.ru. Решения, присланные позднее 24 февраля, не рассматриваются ни при каких обстоятельствах. Дата поступления решений определяется днём получения нами вашего электронного письма. В присланных решениях должно содержаться следующее:

Требования к программам: программы могут быть написаны на любом из существующих процедурных компилируемых языков программирования под любую свободно-распространяемую операционную систему для PC или под Miscrosoft Windows. Исходный текст программы должен быть хорошо отформатирован и откомментирован. Запрещается использовать внешние библиотеки, не входящие в состав поставки компилятора, а также библиотеки компилятора, предназначенные специально для решения поставленной перед вами задачи. Очень приветствуется переносимость написанной программы на другие компиляторы/платформы.

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

Очный тур будет проходить на территории РНЦ «Курчатовский Институт» в конце февраля/начале марта 2011 года. Участники, допущенные до очного тура, будут извещены об этом по электронному адресу, с которого было отослано решение. Также, список участников будет опубликован на этой странице после окончания заочного тура.

Победители и лауреаты будут награждены ценными призами и красивыми грамотами.

Заочный тур

Задача: Совмещение шестигранников.

Рассмотрим типичный случай исследования некоторого физического объекта. Предположим что у нас есть некоторый датчик, снимающий показания некоторой физической величины. Данные снимаются с некоторой малой площади поверхности исследуемого объекта. Использование отдельных датчиков малоэффективно, поэтому, датчики объединяют в сборку или пучок. Если датчики объединить в пучок таким образом, что у нас для каждого внутреннего датчика будет шесть соседей, мы получим структуру, похожую на пчелиные соты. (рис.1) Данные с датчиков, расположенных таким образом, немного сложнее обрабатывать, чем с датчиков, расположенных в узлах прямоугольной решётки, но структура с шестью ближайшими соседями позволяет разместить больше сенсоров на единицу площади.

Image path3025

Рис. 1 Пример пучка из 19 датчиков с «диаметром» в 5 датчиков.

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

Image hc3

Рис. 2 Форма исследуемой области.

Положим, что такой пучок двигается по некоторой поверхности и «сканирует» её, располагаясь над ней в некоторых заданных экспериментатором точках. Однако, к сожалению, экспериментатор не смог хорошо настроить механизм, располагающий пучок над поверхностью, и в итоге пучок располагается над поверхностью с некоторой погрешностью.

Image hc

Рис. 3 Пример смещения пучка датчиков из-за погрешности.

Синим цветом показано ожидаемое расположение пучка. Чёрным цветом заштрихованы шестиугольники, в центрах которых может оказаться центр пучка из-за погрешности механизма. Жёлтой стрелкой показан пример смещения из-за погрешности. Красным цветом обведена область, которая в действительности будет просканирована пучком в случае, если центр пучка перейдёт в шестиугольник, отмеченный стрелкой (для простоты считаем, что он ВСЕГДА окажется в центре одного из заштрихованных шестиугольников, и никогда, скажем между ними). В итоге получается, что для того, чтобы получить полную картину поверхности, надо просканировать её кусочки так, чтобы они заходили друг на друга, и потом при помощи программы «сшить» их в единую картину. Это вам и предстоит сделать на основании данных каждого сканирования и точек, в которых оно должно было происходить.

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

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

Пример входных данных (всё, что содержится между двумя знаками ';' и переводом строки является комментарием и будет отсутствовать в реальных входных данных).

10 10

;; ширина и высота сканируемой области.

7

;; «диаметр» пучка, возможные значения: 5, 7, 9.

;; Форма области как на рис. 1.

3

;; «диаметр» области, в которую попадает центр пучка из-за погрешностей.

;; Нечётное число, строго меньше диаметра пучка. Форма области как на рис. 1.

5

;; число отсканированных участков.

1 2

;; координаты первого участка. Первое число - номер строки сверху вниз,

;; начиная с нуля, второе - номер внутри этой строки слева направо,

;; начиная с нуля.

5 3 7 5 3 6 2 1 5 4 7 3 0 3 2 7 1 8 0 4 4 4 0 2 9 3 0 5 8 1 0 7 5 3 2 5 7

;; Показания датчиков в пучке, числа от 0 до 9 включительно.

;; Показания всех датчиков данного пучка записываются построчно,

;; сначала нулевая строка слева направо, потом следующая, и так далее.

7 8

4 7 2 4 3 2 1 3 9 5 7 8 7 3 7 1 0 6 8 0 2 1 7 6 0 5 0 3 2 6 2 3 5 5 0 7 2

2 6

1 8 7 7 5 1 1 2 3 3 2 1 7 9 6 4 4 4 4 6 3 7 0 5 7 8 2 8 5 8 9 6 6 2 0 5 4

0 9

1 5 9 6 5 2 9 5 3 9 8 4 2 0 8 7 5 7 2 2 4 5 3 8 1 3 7 6 6 0 9 8 2 7 6 7 3

6 3

3 0 5 7 0 7 5 8 9 2 5 7 2 0 5 8 4 5 7 4 3 3 1 7 4 2 0 5 2 5 6 9 1 3 8 4 5

На рис. 4 представлено графическоре решение поставленной задачи. Голубым светом закрашена область 10x10, которую необходимо вывести в качестве ответа. Жёлтым цветом показаны шестиугольники, в которых планировалось поместить центр пучка (из входных данных). Синим цветом помечены шестиугольники, в которых центр оказался на самом деле из-за погрешности (эти точки должна выдавать ваша программа в выходных результатах), зелёным контуром - просканированные области вокруг этих шестиугольников. Заметьте, что в одном из случаев погрешность не сдвинула точку, в которой происходило сканирование, из запланированной, такое тоже возможно. Также видно, что в некоторых случаях просканированные области могут накладываться вне прямоугольной области, и в этом случае перекрывающиеся области тоже должны совпадать. Кроме того, есть два участка, числа в которых выяснить не удалось (отмечены знаками '?').

Image hc4

Рис. 4 Графическое представление решения задачи.

Пример выходных результатов.

Так же как и для входных данных, символы между двумя знаками ';' и переводом строки являются комментариями.

10 10 ;; Размер поля.

5 ;; число отсканированных участков.

;; Далее идут настоящие координаты центров пучков.

;; Они должны идти в том же порядке, что и во входном файле.

2 1

8 8

2 5

-1 9

6 3

;; Распечатка «карты» прямоугольной области. Отступы сделаны так,

;; чтобы повторять структуру области, в вашем выводе их делать не обязательно.

;; Значения, которые невозможно точно определить,

;; обозначаются знаками вопроса.

 6 2 1 5 1 1 2 3 8 1

7 3 0 3 2 1 7 9 6 0

 8 0 4 4 4 4 6 3 7 6

2 9 3 0 5 7 8 2 8 ?

 1 0 7 5 8 9 6 6 ? ?

3 2 5 7 2 0 5 4 7 2

 8 4 5 7 4 3 3 2 1 3

? 1 7 4 2 0 5 7 8 7

 ? 2 5 6 9 1 0 6 8 0

? ? 3 8 4 5 7 6 0 5

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

Примечание. В примере работы рассмотрен не самый сложный вариант входных данных. Работу с более сложными входными данными вы должны протестировать самостоятельно.

Графический интерфейс. Не обязателен, но если сделаете графическое отображение выходных данных, это плюс.

Задача: планировщик заданий.

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

Как правило, на таких супермашинах работают разные исследователи, у которых разные приоритеты на обслуживание. Эти приоритеты определяют возможности пользователей по использованию ресурсов суперкомьютера. Например. Пользователь A запустил задание раньше пользователя B, и в данный момент нет свободных ресурсов. Если пользователь B имеет приоритеты выше, скорее всего, его задание начнет вычисляться раньше.

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

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

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

# Количество компьютеров в систем
100
# Маркер начала списка пользователей
[userlist]
# Пользователь (буквы+цифры) вес(целое)
alex 100
pluto 201
juli 53
# Маркер начала описания заданий
[tasklist]
# Время (ГГГГ-ММ-ДД ЧЧ:ММ:CC) пользователь (из описанных выше) количество комьютеров (целое) время счета (целое в секундах)
2010-05-30 23:59:45 alex 7 56743
2010-05-31 01:01:00 pluto 78 75632
2010-05-31 08:00:59 alex 55 78233

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

# Номер задачи пользователь время поступления в очередь время начала счета время окончания счета
1 alex	2010-05-30 23:59:45 2010-05-30 23:59:45 2010-05-31 23:59:45 
2 alex	2010-05-31 03:59:45 2010-05-31 05:19:20 2010-05-31 23:01:45 
3 pluto	2010-05-31 04:48:23 2010-05-31 04:55:17 2010-05-31 05:12:33 
Т.е. выходной поток будет отображать как планировщик производил бы запуск задач исходя из описания их поступления к нему и реализованному алгоритму планирования.

Обратите внимание, что хотя данные на входе содержат все задачи сразу, алгоритма планирования должен работать так, как будто задачи поступают согласно указанному времени во входных данных.

Удачи!