![[at]](/Images/at.png)
inse.ru.
Решения, присланные позднее 24 февраля,
не рассматриваются ни при каких обстоятельствах. Дата поступления решений
определяется днём получения нами вашего электронного письма. В присланных
решениях должно содержаться следующее:
Курчатовская олимпиада по информатике состоит из двух туров: заочного и очного. Очный тур будет происходить в Москве, в конце февраля/начале марта 2011 года. Отбор участников очного тура происходит по результатам заочного тура. В олимпиаде может принимать участие любой школьник, обучающийся в 1-11 классе любой школы России.
Правила проведения заочного тура таковы: желающим предлагаются две задачи,
которые решаются дома, и не позднее 24 февраля 2011 года решения отсылаются по
электронному адресу olymp11inse.ru.
Решения, присланные позднее 24 февраля,
не рассматриваются ни при каких обстоятельствах. Дата поступления решений
определяется днём получения нами вашего электронного письма. В присланных
решениях должно содержаться следующее:
Требования к программам: программы могут быть написаны на любом из существующих процедурных компилируемых языков программирования под любую свободно-распространяемую операционную систему для PC или под Miscrosoft Windows. Исходный текст программы должен быть хорошо отформатирован и откомментирован. Запрещается использовать внешние библиотеки, не входящие в состав поставки компилятора, а также библиотеки компилятора, предназначенные специально для решения поставленной перед вами задачи. Очень приветствуется переносимость написанной программы на другие компиляторы/платформы.
Важное замечание: не обязательно делать обе программы. Если вы сделали только одну, или даже половину программы — присылайте получившееся нам, мы разберемся.
Очный тур будет проходить на территории РНЦ «Курчатовский Институт» в конце февраля/начале марта 2011 года. Участники, допущенные до очного тура, будут извещены об этом по электронному адресу, с которого было отослано решение. Также, список участников будет опубликован на этой странице после окончания заочного тура.
Победители и лауреаты будут награждены ценными призами и красивыми грамотами.
Рассмотрим типичный случай исследования некоторого физического объекта. Предположим что у нас есть некоторый датчик, снимающий показания некоторой физической величины. Данные снимаются с некоторой малой площади поверхности исследуемого объекта. Использование отдельных датчиков малоэффективно, поэтому, датчики объединяют в сборку или пучок. Если датчики объединить в пучок таким образом, что у нас для каждого внутреннего датчика будет шесть соседей, мы получим структуру, похожую на пчелиные соты. (рис.1) Данные с датчиков, расположенных таким образом, немного сложнее обрабатывать, чем с датчиков, расположенных в узлах прямоугольной решётки, но структура с шестью ближайшими соседями позволяет разместить больше сенсоров на единицу площади.
Саму исследуемую поверхность при такой схеме разположения датчиков также удобнее описывать структурой, похожей на соты. (рис.2) Кроме того, примем, что верхний левый угол её всегда имеет такую же форму, как и на рисунке, т.е. первый ряд смещён относительно нулевого влево.
Положим, что такой пучок двигается по некоторой поверхности и «сканирует» её, располагаясь над ней в некоторых заданных экспериментатором точках. Однако, к сожалению, экспериментатор не смог хорошо настроить механизм, располагающий пучок над поверхностью, и в итоге пучок располагается над поверхностью с некоторой погрешностью.
Синим цветом показано ожидаемое расположение пучка. Чёрным цветом заштрихованы шестиугольники, в центрах которых может оказаться центр пучка из-за погрешности механизма. Жёлтой стрелкой показан пример смещения из-за погрешности. Красным цветом обведена область, которая в действительности будет просканирована пучком в случае, если центр пучка перейдёт в шестиугольник, отмеченный стрелкой (для простоты считаем, что он ВСЕГДА окажется в центре одного из заштрихованных шестиугольников, и никогда, скажем между ними). В итоге получается, что для того, чтобы получить полную картину поверхности, надо просканировать её кусочки так, чтобы они заходили друг на друга, и потом при помощи программы «сшить» их в единую картину. Это вам и предстоит сделать на основании данных каждого сканирования и точек, в которых оно должно было происходить.
Во входных данных задаётся область из шестиугольников, в которых планируется сделать сканирование. В выходных данных выводятся точные координаты, в которых действительно было выполнено сканирование, и числа, содержащиеся в прямоугольной области.
Пример входных данных (всё, что содержится между двумя знаками ';' и переводом строки является комментарием и будет отсутствовать в реальных входных данных).
;; ширина и высота сканируемой области.
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, которую необходимо вывести в качестве ответа. Жёлтым цветом показаны шестиугольники, в которых планировалось поместить центр пучка (из входных данных). Синим цветом помечены шестиугольники, в которых центр оказался на самом деле из-за погрешности (эти точки должна выдавать ваша программа в выходных результатах), зелёным контуром - просканированные области вокруг этих шестиугольников. Заметьте, что в одном из случаев погрешность не сдвинула точку, в которой происходило сканирование, из запланированной, такое тоже возможно. Также видно, что в некоторых случаях просканированные области могут накладываться вне прямоугольной области, и в этом случае перекрывающиеся области тоже должны совпадать. Кроме того, есть два участка, числа в которых выяснить не удалось (отмечены знаками '?').
Так же как и для входных данных, символы между двумя знаками ';' и переводом строки являются комментариями.
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Т.е. выходной поток будет отображать как планировщик производил бы запуск задач исходя из описания их поступления к нему и реализованному алгоритму планирования.
Обратите внимание, что хотя данные на входе содержат все задачи сразу, алгоритма планирования должен работать так, как будто задачи поступают согласно указанному времени во входных данных.