Брой 26 на Списание Инфоман
 


Национална олимпиада по информатика 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