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


Първо контролно за BOI 2004, Задача 3. НИЗОВЕ

Уловието на задачата може да прочетете тук.

Решение

Задачата може да се реши по различни начини, с използване на различни структури и подходи. Но възползвайки се от ограниченията на задачата може да приложим много лесен подход, който включва едно сортиране и едно обхождане на низовете.

Първо ще сортираме низовете лексикографски. След сортирането, еднаквите низове ще стоят един след друг. После ще обходим сортираната последователност като броим еднаквите низове и съответно ще запазим този, който се среща най-малко. Освен това за всяка последователност от еднакви низове трябва да запазваме този с най-малък номер в началната последователност. Това се прави с цел при равен брой срещания на два низа да изберем този, който се среща по-рано.

Горе-описания подход най-лесно ще се реализира ако направим един масив с числата от 1 до N, като всяко ще бъде индекс в оригиналния масив с низове. Така сортирайки числата относно низовете, ще имаме и поредните номера на всеки низ в началната последователност.

Примерна реализация

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;


const int maxn = 100000;
const int maxl = 12;


int n, ans;
int ix[maxn];
char s[maxn][maxl];


void solve();

int main()
{
	solve();

	return 0;
}

void solve()
{
	int i, cb, cc, cm;

	void readf();
	void writef();
	int icmp(const void* i1, const void *i2);

	readf();

	for (i = 0; i < n; i++)
		ix[i] = i;

	qsort(ix, n, sizeof(int), icmp);

	cb = maxn + 1;
	cc = 1;
	cm = ix[0];
	for (i = 1; i < n; i++)
	{
		if (strcmp(s[ix[i]], s[ix[i-1]]) == 0)
		{
			cc++;
			cm = min(cm, ix[i]);
		}
		else
		{
			if (cc < cb || cc == cb && cm < ans)
			{
				cb = cc;
				ans = cm;
			}
			cc = 1;
			cm = ix[i];
		}
	}

	writef();
}

void readf()
{
	int i;

	cin >> n;
	for (i = 0; i < n; i++)
		cin >> s[i];
}


void writef()
{
	cout << s[ans] << '\n';
}

int icmp(const void* i1, const void *i2)
{
	int r, x1, x2;

	x1 = *(int*)i1;
	x2 = *(int*)i2;
	r = strcmp(s[x1], s[x2]);

	return ((r != 0) ? r : x1 - x2);
}
			

Автор: Иван Анев


обратно към брой 26