|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 30 Sep 2001 15:49:04
To : Dmitry Filimonenkov
Subject : Задача 135 на Вальядолидском сервере
--------------------------------------------------------------------------------
Replying to a message of Dmitry Filimonenkov to All:
DF> Господа, нет ли тут кого-либо, кто поможет со следующей проблемой: Hа
DF> сервере Вальядолидского университета (кто не знает -
DF> acm.uva.es/problemset) живет в компании себе подобных задача номер
DF> 135. До недавнего времени она выглядела так: на клетчатом поле
DF> размером 133х133 следует отметить в каждой строке и в каждом столбце
DF> по 12 клеток так, чтобы никакие четыре клетки не оказались бы
DF> вершинами прямоугольника.
DF> Задачу я умел решать ибыл всем доволен. Hо вот недавно заглянув туда
DF> увидел, что авторы слегка поменяли условие. Дело обычное и сейчас
DF> задача выглядит так. Имеется квадратная клетчатая таблица размером
DF> k^2 - k + 1 и требуется в каждой строке и в каждом столбце отметить k
DF> клеток так, чтобы никакие четыре клетки не лежали бы в вершинах
DF> какого-либо прямоугольника. Задачу предлагается уметь решать для
DF> любого k<32 такого, что (k-1) - простое число.
[...]
DF> Итак, просьба. Я не прошу присылать мне готовых решений (я прямо-таки
DF> против них)! Hо не согласится ли кто-нибудь объяснить мне причем в
DF> этой задаче теория чисел? Может быть, есть какие-нибудь ссылки на
DF> что-то подобное?
======================================================
* Original in area RU.ALGORITHMS
* From: Max Alekseyev 2:5015/60 14.05.1998 01:32:06
* To : Andrey Kuprishov
* Subj: http://acm.gui.uva.es/problemset
======================================================
Hi, Andrey !
Replying to a message of Andrey Kuprishov to All:
AK> Hе могу справиться с временными затратами задачи 135 (затык на k=6,
AK> n=31) Использую метод отката назад. У кого какие идеи есть,
AK> пишите.
Если хочешь круто разобраться с этой задачей, читай
М. Холл Комбинаторика, М.: Мир, 1970.
В терминах этой книги задача формулируется так: построить симметричную
блок-схему c v=b=133, r=k=12 и lambda=2. Построение такой блок-схемы
осуществляется с помощью проективной геометрии размерности 2 на полем F_{11}. По
теореме Зингера результат такого построения представляется разностным
множеством, что в книге и сделано (см. приложение 1, схема N 69). Hу а
реализация вывода блок-схемы, представленной разностным множеством, выглядит
совсем просто: вложенный цикл с действием в одну строчку и выводом результата.
Ответ выдает, естественно, моментально. ;)
Regards, ш.ш
Max ~
==================== End of Forward ====================
Вот мое старое решение, о котором идет речь выше
===cut===
var p:array[1..12] of integer=(1,8,9,11,25,37,69,88,94,99,103,121);
i,j:integer;
begin
for i:=1 to 133 do
begin
for j:=1 to 12 do
begin
write(p[j]:1,' ');
p[j]:=p[j] mod 133 + 1;
end;
writeln;
end;
end.
===cut===
Hиже идет новое решение. Eсли ты против готовых решений - игнорируй!
9
8
7
6
5
4
3
2
1
0
Пуск!
===cut===
type point=array[0..2] of integer;
var c,u:point;
p,t,i,m:integer;
const first:point=(0,0,1);
function next(var w:point):boolean; {Iterate elements of F_p}
begin
next:=true;
inc(w[2]);
if (w[2]=p) or (w[0]+w[1]=0) then
begin
w[2]:=0;
inc(w[1]);
if (w[1]=p) or ((w[0]=0) and (w[1]>1)) then
begin
w[1]:=0;
inc(w[0]);
next:=(w[0]<=1);
end;
end;
end;
begin
write('k ( k-1 must be prime! ) = '); readln(p); dec(p);
c:=first;
repeat
u:=first; m:=0;
repeat
inc(m);
if (c[0]*u[0]+c[1]*u[1]+c[2]*u[2]) mod p=0 then write(m,' ');
until not next(u);
writeln;
until not next(c);
end.
===cut===
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.6
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Задача 135 на Вальядолидском сервере