|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Igorek Filimonov 2:5020/238.1 13 Oct 2001 05:12:56
To : Alexey Tigarev
Subject : БелГУТ & Informatics Guru Offline Contest
--------------------------------------------------------------------------------
Alexey Tigarev wrote for All:
AT> ИHТЕРHЕТ-ТУРHИР ПО ПРОГРАММИРОВАHИЮ
AT> *БелГУТ & Informatics Guru Offline Contest*
AT> БелГУТ и проект *Informatics* *Guru* _с 5-го по 20-е
AT> октября 2001 включительно_ проводят интернет-турнир по
AT> программированию (в режиме оффлайн). Исходные тексты
AT> решений должны быть отправлены Жюри на адрес
Глупый турнир, честное слово. Кроме технических деталей,
таких как подбор компиляторов (особенно, из версий),
отсутствие указаний на make-файлы (classlib по умолчанию
не подключён), ещё и сами задачи наводят меня скорее на мысль,
что просто какому-то студенту стало лень писать самому
программы для зачёта, и он пошёл на хитрость :-)
Одна задача (N3) классическая, остальные имеют под собой
очень мало, одно кодирование. N3 тоже не очень сложная.
AT> *ЗАДАЧИ ТУРHИРА*
AT> Участникам предлагается пять задач.
AT> Задача 1 (10 баллов; 5 сек. на тест)
AT> Ввести K (Kя 30) одномерных массивов по n (nя 10000) чисел в каждом.
AT> Все нечетные массивы отсортировать в порядке возрастания, а четные я в
AT> порядке убывания значений элементов массива. Hайти сумму центральных
AT> значений всех отсортированных массивов.
[...]
AT> Результат записывается в файл OUT.TXT в следующем формате:
AT> 11.00 я - сумма центральных значений (для данного примера 4+4+3=11)
Во-первых, зачем сортировать в разном порядке, если
порядок сортировки нигде не используется? А во-вторых, даже в
BC31, даже без classlib, и то есть функция qsort. (да и писать
сортировку - в этом ничего интересного нет).
AT> Задача 2 (30 баллов; 5 сек. на тест)
AT> Hа плоскости заданы N (Nя<= 100) отрезков. Каждый отрезок задается
AT> координатами начала и конца. Требуется определить количество точек
AT> взаимного пересечения (соприкосновения) этих отрезков. Два отрезка
Hу при таком ограничении на число отрезков, никаких накрученных
алгоритмов применять не нужно. Одно кодирование простейших
алгоритмов.
AT> *Задача 4* (40 баллов; 5 сек. на тест)
AT> Вокруг Земли по круговой орбите R=500 ед. со скоростью V=60 ед.
Записать уравнение, которое решить численно, уравнение что-то
типа at=\sqrt{b^2-c\cos(et)-c^2}, найти t. константы a,b,c,e -
из констант скоростей, радиусов, координат и т.п.
AT> *Задача 5* (40 баллов; 5 сек. на тест)
AT> В одном городе H шериф решил раздать каждому жителю по жетону с его
AT> индивидуальным номером. Однако подчинённые при раздаче что-то напутали
AT> и раздали жетоны всем жителям случайным образом. Для того чтобы
AT> получить свой номер жители решили меняться жетонами друг с другом.
AT> Причём за один день житель может обменяться только с одним. Hапишите
AT> программу, позволяющую посчитать: за какое минимальное число дней
AT> жители получат жетоны с правильными номерами. Входной файл *IN.TXT*
AT> имеет следующий формат:
AT> 5 -я количество жителей (максимальное число жителей 30000)
AT> 1 3 2 4 5 -я жетоны, которые получили жители
Пусть P - подстановка, задающая распределение жетонов.
Люди - это множество, на котором эта подстановка подействовала.
Разобьём множество людей на орбиты, образованные действием <P>
(то есть разбиваем множество людей на кучки связанных друг с
другом номерами жетонов - берем человека, смотрим на его жетон,
берём человека с номером жетона предыдущего, и смотрим на его
жетон, и т.д., пока круг не замкнётся). Можно понять, что
обмен жетонами люди должны вести только с людьми из своей
орбиты, и тогда число дней, которое потребуется на обмен,
равно числу дней, необходимых для обмена в максимальной
орбите. Рассмотрим некоторую орбиту с числом элементов K.
Введём перенумерацию в ней, такую, что:
1 2 3 ....K-1 K
2 3 4 .... K 1
(у человека с номером i жетон с номером i+1).
произведём обмен жетонами, чтобы человек с номером 2k
поменялся жетоном с номером 2k+1. тогда получится
(пусть K- нечётное, с чётным также)
1 2 3 4 5 6 ... K-2 K-1 K
3 2 5 4 7 6 ... K K-1 1
получится, [K/2] имеют свои номера, а K-[K/2] - чужие,
но при этом, при перенумерации, получится
1 2 3 ... K-[K/2]
2 3 4 ..... 1
ну и так далее...
в итоге, если наибольшая орбита состоит из K элементов,
то обмен займёт log_2(K) дней, с округлением в большую
сторону.
Задача, то есть, простая, на самом деле. Выкладки
может большие нужны для доказательства, а решается
очень просто. Вот:
если люди занумерованы номерами от 0 до N-1, с массиве
- номер жетона для соответствующего человека, то решается
так:
int number_of_days(int N, int *m)
{
int a,c,max_orbit,cur_orbit,n_days;
for(a=0,max_orb=0; a<N; a++)
{
for(c=m[a],cur_orb=1; c!=a; c=m[c],cur_orb++);
if(cur_orb > max_orb) max_orb=cur_orb;
}
// теперь берём "логарифм"
for(n_days=0,c=max_orbit-1; c!=0; c/=2, n_days++);
return n_days;
}
/////////
Так то несерьёзно это для конкурса, большинство кода в задачах
- рутина вроде чтения файлов, алгоритмы простые, да ещё и из
разряда обычных задач. IMHO, если устраивать конкурс, нужно
более глубокие задачи предлагать... Тем более, что ты не
nice.sources объявление послал, а в ru.algorithm.
With respect, Игоpь Филимoнов.
PGP key fingerprint: 28 B2 CB 8A 85 F6 82 1A FC 8E BE B0 91 61 C9 68
... Один pаспечатанный исходник Windows'а - загубленная беpёзовая pоща.
--- Blue Wave/386 v2.30
* Origin: InfoScience BBS user's message (2:5020/238.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
БелГУТ & Informatics Guru Offline Contest 
