Национална олимпиада по информатика 2004, Задача 2.1. БАКТЕРИИ
Уловието на задачата може да прочетете тук.
Решение
Имаме
правоъгълна дъска N на N. В някой клетки от дъската има
бактерии. Ние можем да задаваме въпроси от вида колко бактерии има в
правоъгълна област от дъската. Задачата ни е с минимален брой запитвания да
намерим положението на бактериите върху дъската. Едно тривиално решение е да
питаме за всяко квадратче от дъската, но така ще бъдем много далеч от минимален
брой питания. Очевидно ако в някоя правоъгълна област от дъската няма нито една
бактерия няма смисъл да питаме квадратче по квадратче в нея. Трябва да измислим
стратегия чрез която да намираме подобни области и да си спестяваме
задълбаването, тоест питането за по-малки области (единични квадратчета).
Ще
приложим метод много подобен на двоичното търсене. Ако имаме една правоъгълна
област, в която знаем че имам X бактерии,
ще разделим областта на две части, възможно най-равни по големина. Ще питаме за
едната част колко бактерии има в нея. Ако в нея има Y бактерии, значи в другата част има X – Y бактерии. Сега ако сме установили, че в
някоя от областите няма нито една бактерия, спираме да я разглеждаме занапред.
В противен случай за частите, в които има бактерии прилагаме същата техника и
ги разделяме на две части и т.н. докато някоя част не се окаже единично
квадратче. Тогава ако имаме бактерия в него го обявим чрез извикване на answer. Така започвайки от големия
правоъгълник, чрез последователно разделяне на две части, ще намерим всички
бактерии.
Броят
запитвания за откриването на една бактерия е пропорционален на log2(N2) =
2.log2(N). Ако K е броят бактерии, общия брой
запитвания ще бъде пропорционален на O(K.log(N)).
Примерна реализация
#include "module.h"
int n;
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int all;
void find_em(int x1, int x2, int y1, int y2, int all);
n = getSize();
all = ask(1, n, 1, n);
find_em(1, n, 1, n, all);
}
void find_em(int x1, int x2, int y1, int y2, int all)
{
int m, l;
if (all > 0)
{
if (x1 == x2 && y1 == y2)
{
answer(x1, y1);
}
else
{
if (x1 != x2)
{
m = (x1 + x2) / 2;
l = ask(x1, m, y1, y2);
find_em(x1, m, y1, y2, l);
find_em(m + 1, x2, y1, y2, all - l);
}
else
{
m = (y1 + y2) / 2;
l = ask(x1, x2, y1, m);
find_em(x1, x2, y1, m, l);
find_em(x1, x2, m + 1, y2, all - l);
}
}
}
}
Автор: Иван Анев
обратно към брой 26
|