Сортировка атомов(2012г)

СОРТИРОВКА АТОМОВ

Внимание, начинаем очередной конкурс программистов. Как обычно проводятся конкурсы программистов? все приходят, даются задания, все их решают.
Как правило задания сложные и если (не дай бог конечно) кто-то узнает о заданиях заранее, то он получает ощутимое преимущество. Мы долго искали такую форму проведения конкурса, которая исключила бы саму возможность несправедливости. И мы ее нашли!
Наш конкурс проводится в течении уже нескольких лет и всегда по одному сценарию.
Задание известно заранее и для всех! Вот только оно... НЕРЕШАЕМО! Точнее, оно не имеет однозначного решения. Ну а какой тогда смысл в таком задании? А смысл в том, что вокруг нас такие задачи встречаются постоянно. Вот взять хотя бы обыкновенный лифт. Если бы знать, сколько народу ждет на этаже, да сколько из них и куда поедет, то тогда можно найти однозначное решение. Ну так что теперь, лифты нельзя программировать? А ведь кто-то логику для лифтов программирует! И у кого-то лифты работают лучше а у кого-то нет.

Для того, чтобы выиграть в нашем конкурсе, нужно не просто знать язык программирования и уметь реализовывать какие-то алгоритмы. Нужно придумать, как можно решить задачу с наилучшим результатом. Ну а потом реализовать свою идею на языке программирования. Тоесть нужно уметь использовать программирование как инструмент решения задачи. Тут все важно. И идея и реализация.

Мало того, мы не просто заранее даем задание, но и предлагаем готовую реализацию! Как правило, наша программа уже работает и даже очки получает! Просто чтобы победить, желательно заработать очков как можно больше. Ну а конкуренты не дремлют! Но зато можно посмотреть как все реализовано.

Конкурс проводится в 2-а этапа. Сначала заочный этап. Все желающие регистрируются на сайте и заполняют заявку согласно положению о конкурсе (Приложение 1) . (Заполненная заявка должна быть отправлена на адрес knf09@rambler.ru)

Затем участники скачивают подходящий им проект и пробуют его доработать. Целый месяц, все пробуют улучшить результаты, задают вопросы, знакомятся с проблемой . Вопросы по конкурсу лучше задавать через систему Вопрос-ответ. Это и есть заочный этап.

В этом году спонсором конкурса выступает "РОСАТОМ". Ожидаются участники из других городов края. Традиционно,в нашем конкурсе будут 2-е номинации. Отдельно 8-9 классы и 10-11.

ИТАК, СЛУШАЙТЕ УСЛОВИЯ КОНКУРСА

Одной из больших проблем является проблема переработки ядерных отходов. Недавние события на АЭС "ФУКУСИМА" показали, что эта проблема является очень и очень серьезной. Нами предлагается новейшая система очистки, состоящая из множества микророботов, которые будут работать под управлением вашей программы.

В емкости, где находятся роботы растворены атомы 3-х типов Тип =1 - радиоактивные изотопы, Тип =2 - окислитель и Тип =3 - нейтральные атомы. Робот может анализировать тип атома, который ему доступен в текущий момент. для этого существует функция "M_GET". Управляется робот при помощи подпрограммы "M_RAB" (применение описано ниже). Каждый робот может взять до 9-ти атомов (после чего команда "взять" перестает выполняться).

За каждый взятый атом первого типа дается одно очко.

Кроме роботов на игровом поле находятся утилизаторы (синие квадратики), которые служат для переработки атомов. Если координаты робота совпадают с координатами утилизатора, то робот разгружается. Если в утилизаторе скапливаются атомы 1-го и 2-го типа, То они вступают в реакцию и за каждую пару дается еще два очка.

Всего на миссию дается 3000 ходов. Один ход - это когда будут выданы команды не всех роботов. ВНИМАНИЕ! если вы выдадите команду на робота, которым уже ходили в этом цикле, то программа автоматически считает ход сделанным!

Ваша задача - набрать макимальное количество очков. Смотрите исходники проектов, задавайте вопросы. Для успеха необходимо построить коллективную систему управления роботами. Кстати, на очном этапе условия будут изменены и за 4-ре часа необходимо будет переделать свою программу для получения большей эффективности (А то вдруг программу вы не сами писали?).

Игрушку с ручным управлением для вникания в проблему можно скачать здесь
Внимание! игрушка управляется следующим образом:
Левая кнопка мышки задает точку сбора, к которой стремятся все роботы.
Правая кнопка, наоборот, задает точку от которой все роботы начинают разбегаться.
Средняя кнопка включает режим случайных перемещений (роботы начинают топтаться на месте)
Кнопки "В круг" "вертикаль" и "Горизонталь" пытаются соответственно построить роботов.
Роботов 100, утилизаторов 50. Кнопки "Разгрузка 1" и "Разгрузка 2", Отправляют половину роботов к утилизаторам.
Роботы обозначены квадратиками. Зеленый цвет, говорит о том, что робот пустой. Желтый - что он захватил несколько атомов. Ну а красный, говорит о том, что робот полон, и больше не может брать атомы. Синие квадратики - утилизаторы. Ну а атомы представлены точками.
белые - радиоактивные атомы (1-й тип). Красные - окислитель (2-й тип) Ну а синие (их слабо видно - нейтральные) Конечно, программа написана бестолково, роботы постоянно натыкаются друг на друга. Это мешает им занять нужные позиции, но ведь вы конечно напишете более вразумительную программу? не так ли? :-).

Итак, приступаем собственно к заданию.

Для разных облочек программирования (C++BUIlDER, DELPHI2007, LAZARUS) мы подготовили проекты, в которых роботы двигаются по случайному закону и ловят атомы первого(радиоактивного) типа. Это "затравка" для вашей программы. В проекте специально выделена подпрограмма пользователя которую вам и необходимо модифицировать. Остальные части проекта трогать нежелательно, во избежание потери работоспособности.

Размер сосуда 640 на 640 пикселов. В задаче заочного этапа имеется 100 роботов и 50 утилизаторов.

Для управления применяется подпрограмма M_RAB(N,KOM);

N   - Номер робота (от 1 до MAX_ROB)
KOM - Команда  =1 - Влево 
               =2 - Вверх
               =3 - Вправо
               =4 - Вниз
               =5 - Взять ближайший атом (выполнится если такой атом есть, и робот не заполнен)

Узнать, какой тип атома сейчас может быть взят роботом можно через функцию M_GET(N) (Где N - номер робота). Кроме того, В ходе работы программы вам доступны основные параметры, которые вам выдаются в виде готовой структуры:

                 Для LAZARUSA и DELPHI
****************************************************************
// описание робота
 T_ROB=PACKED RECORD
    X,Y:INTEGER;// координаты
    KOL:BYTE;   // количество пойманных атомов
   END;
// описание утилизатора
 T_UTIL=PACKED RECORD
    X,Y:INTEGER;// координаты
   END;
//  ОСНОВНАЯ СТРУКТУРА
 T_STRUK=PACKED RECORD
     MAX_ROB:INTEGER; // Количество роботов
     MAX_UTIL:INTEGER;// Количество утилизаторов
     KOL_HOD:INTEGER; // количество оставшихся ходов
     SCORE: INTEGER;  // Очки
     MR:PACKED ARRAY[1..MAX_ROB]OF T_ROB;  // Массив роботов
     MU:PACKED ARRAY[1..MAX_UTIL]OF T_UTIL;// Массив утилизаторов
    END;


                    для С++BUILDERA
****************************************************************

// описание робота
struct T_ROB{
public:
	int X;   // координаты
	int Y;   // координаты
	Byte KOL;// количество пойманных атомов
} ;
// описание утилизатора
struct T_UTIL{
public:
	int X;// координаты
	int Y;// координаты
} ;
//  ОСНОВНАЯ ТРУКТУРА
struct T_STRUK{
public:
	int MAX_ROB;  // Количество роботов
	int MAX_UTIL; // Количество утилизаторов
	int KOL_HOD;  // Оставшееся количество ходов
	int SCORE;    // Очки
	T_ROB MR[100];// Массив роботов
	T_UTIL MU[50];// Массив утилизаторов
} ;


} ;
//   ВНИМАНИЕ !!! ввиду известных особенностй
// реализации массивов на языке "С", нумерация в массивах "сдвинута"
// Например номера роботов идут от 1 до 100 а нумерация в массиве от 0 до 99.

Например:
Текущие координаты 5-го робота будут (на паскале) P^.MR[5].X и P^.MR[5].Y
А на С P->MR[4].X и P->MR[4].Y

А здесь выложены готовые проекты, которые вам нужно будет подправить для достижения наибольшего результата. Учтите, что работать Можно на си или паскале
P.S. Результатом считается количество набранных вами очков. Чем очков больше, тем лучше!

Проект для Lazarus (Предпочитается)
Проект для C++BUILDER(CodeGear)
Проект для Delphi7(CodeGear)(не рекомендуется)

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

Очный этап состоится 31 марта.

По результатам очного этапа будут вручены грамоты и призы.

На сегодня зарегистрировались: (модерируется 1-н раз в сутки)

По всем вопросам обращайтесь к администрации "звездного мира" через систему

Вопрос-ответ.