Международна олимпиада по информатика 2005, Задача 1.1. GARDEN
Уловието на задачата
може да прочетете тук.
Решение
За всеки два правоъгълника, които не се припокриват,може да се намери вертикална или
хоризонтална линия, спрямо която те са в различни половини на градината.
Нека правоъгълник, който съдържа k рози
наричаме k-правоъгълник. За всяка линия
(хоризонтална или вертикална) може да се намери за всяка от двете половини, на
които тя дели полето, k-правоъгълника с най-малък периметър.
Ако се обходят всички линии и се вземе тази, за която сумата от периметрите на
двата най-малки k-правоъгълника от двете й страни е минимална,
то тази сума ще бъде отговорът на задачата.
Първо за всяка хоризонтална линия търсим най-малкия k-правоъгълник, който има за долна граница дадената
линия и този, който има за горна граница дадената линия. Аналогично се пресмята
и за всички вертикални линии. За целта се търсят всички k-правоъгълници и за всеки ако се наложи се обновява
досега пресметнатата оптимална стойност за четирите линии, които се явяват крайни
за дадения правоъгълник. Тук може да се забележи, че е нужно да се намерят само
тези k-правоъгълници, които не съдържат в
себе си други k-правоъгълници.
Нека имаме функция r(x1,y1,x2,y2), която връща броя рози в даден правоъгълник. Дефинираме
функция p(x,y), която връща броя рози във всеки
правоъгълник от вида (1,1,x,y). Тя се
пресмята по следния начин:
p(x,y) = p(x-1,y) + p(x,y-1) – p(x-1,y-1) +
m(x,y),
като m(x,y)е броят рози в квадрат с координати (x,y). Използвайки горната функция, за
да се пресметнат всички
стойности p(x,y) са
нужни общо О(l*m)операции.
r(x1,y1,x2,y2)може да се пресметне по следния
начин:
r(x1,y1,x2,y2) = p(x2,y2) – p(x1-1,y2)
– p(x2,y1-1) + p(x1-1,y1-1).
За да се намерят всички k-правоъгълници
последователно за всяка двойка y
координати (y1,y2) се използват две
хоризонтални линии x1 и x2. В началото x1=1 и x2=1, тоест са
разположени на първия ред. Стойностите на x1
и x2 се променят по следните правила:
Ако
r(x1,y1,x2,y2) = k,
то е
намерен нов k-правоъгълник, x1 се увеличава с 1;
Ако r(x1,y1,x2,y2) < k, x2 се
увеличава с 1;
Ако r(x1,y1,x2,y2) > k, x1 се увеличава
с 1;
Горните стъпки се изпълняват докато x2≤l.
Тази стъпка
отнема време О(w2l).
След това за всяка вертикална линия y1се избира тази вертикална линия y2, за която y2≤y1 и
линията y2 е дясна граница на k-правоъгълника с минимален периметър. Така за всяка вертикална линия се
изчислява най-малкия периметър на k-правоъгълник,
разположен наляво от нея. Аналогично се пресмятат и стойностите надясно. След
това по същия начин се определят оптималните k-правоъгълници, които са съответно под и над всяка хоризонтална
линия.
Остава да се обходят всички линии (вертикални и хоризонтални)
и да се намери за всяка от тях сумата от периметрите на оптималните k-правоъгълници, разположени от двете и страни.
Минималната сума, която получим, е отговорът на задачата.
Примерна реализация
#include <stdio.h>
#define MAXL 256
#define INF 2000000000
int l,w;
int n,k;
// map of the roses
int map[MAXL][MAXL];
// array with precoputed number of roses
int numros[MAXL][MAXL];
// the smallest k-rectangle around every vertical line
int ver[MAXL][2];
// the smallest k-rectangle around every horizontal line
int hor[MAXL][2];
// the smallest k-rectangle to the left and to the right
// of every vertical line
int verbest[MAXL][2];
// the smallest k-rectangle up and down from
// every horizontal line
int horbest[MAXL][2];
int ans;
void init()
{
int i;
for(i=0;i<MAXL;i++)
{
ver[i][0] = ver[i][1] = INF;
hor[i][0] = hor[i][1] = INF;
}
}
void input()
{
int i;
int x,y;
scanf("%d %d %d %d",&l,&w,&n,&k);
for(i=0;i<n;i++)
{
scanf("%d %d",&x,&y);
map[x][y]++;
}
}
int calcArea(int x1, int y1, int x2, int y2)
{
return numros[x2][y2] - numros[x1-1][y2] -
numros[x2][y1-1] + numros[x1-1][y1-1];
}
void updateArea(int x1, int y1, int x2, int y2)
{
int per;
per = 2*(x2-x1+y2-y1+2);
if(ver[x1-1][1]>per)
ver[x1-1][1] = per;
if(ver[x2][0]>per)
ver[x2][0] = per;
if(hor[y1-1][1]>per)
hor[y1-1][1] = per;
if(hor[y2][0]>per)
hor[y2][0] = per;
}
int minv(int a, int b)
{
return (a<b)?a:b;
}
void solve()
{
int i,i2;
int leftb,rightb;
int res;
// precomputing the number of roses in squares with
// lower left corner at (1,1)
for(i=0;i<=l;i++)
for(i2=0;i2<=w;i2++)
{
if(i==0 || i2==0)
numros[i][i2] = 0;
else
numros[i][i2] = numros[i-1][i2] +
numros[i][i2-1] - numros[i-1][i2-1] +
map[i][i2];
}
// finding all the k-rectangles and updating the values for
// all vertical and horizontal lines
for(i=1;i<=w;i++)
for(i2=i;i2<=w;i2++)
{
leftb = rightb = 1;
while(rightb<=l)
{
res = calcArea(leftb,i,rightb,i2);
if(res==k)
{
updateArea(leftb,i,rightb,i2);
leftb++;
}
else
{
if(res<k)
rightb++;
else
leftb++;
}
}
}
// finding for every line the smallest k-rectangle on both sides
// of the line
verbest[0][0] = INF;
for(i=1;i<=l;i++)
{
verbest[i][0] = minv(verbest[i-1][0],ver[i][0]);
}
verbest[l][1] = INF;
for(i=l-1;i>=0;i--)
{
verbest[i][1] = minv(verbest[i+1][1],ver[i][1]);
}
horbest[0][0] = INF;
for(i=1;i<=w;i++)
{
horbest[i][0] = minv(horbest[i-1][0],hor[i][0]);
}
horbest[w][1] = INF;
for(i=w-1;i>=0;i--)
{
horbest[i][1] = minv(horbest[i+1][1],hor[i][1]);
}
// finding the answer
ans = INF;
for(i=1;i<l;i++)
if(ans > verbest[i][0]+verbest[i][1])
ans = verbest[i][0]+verbest[i][1];
for(i=1;i<w;i++)
if(ans > horbest[i][0]+horbest[i][1])
ans = horbest[i][0]+horbest[i][1];
}
void output()
{
if(ans != INF)
printf("%d\n",ans);
else
printf("NO\n");
}
int main()
{
init();
input();
solve();
output();
return 0;
}
Автор: Антон Димитров
обратно към брой 27
|