Тема: Футбольные парадоксы
Была такая задача на ленинградской областной олимпиаде - 2006
Некий мальчик Петя решил проанализировать результаты всех матчей, которые он знает, и выбрать из них самую длинную цепочку игр, обладающую следующим свойством - победитель любого матча этой цепочки(кроме последнего) должен проиграть в следующем матче этой цепочки. Причем, хронологический порядок игр должен сохраниться, т.е. следующий матч в цепочке должен быть сыгран позже предидущего.
Во входном файле - отсортированная хронологически последовательность игр (описание игры имеет вид "WINNER-LOSER", где WINNER и LOOSER - 3х-символьные идентификаторы команд).
В выходной файл необходимо вывести максимальное количество матчей в искомой цепочке, а затем и саму цепочку.
Пример входного файла:
5
FRA-ITA
GER-ITA
ITA-GER
ITA-LUX
RUS-ITA
Пример выходного файла:
3
RUS-ITA-GER-ITA
Вот мое решение (вроде бы вполне логичное, но валится на 6м тесте).
Подскажите, пожалуйста, что не так.
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
using namespace std;
map <string, string> p;
map <string, int> d;
map <string, int>::iterator it;
string game;
int n;
int main()
{
freopen("paradox.in", "rt", stdin);
freopen("paradox.out", "wt", stdout);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> game;
string s1 = game.substr(0, 3);
string s2 = game.substr(4, 3);
if (d[s2] + 1 > d[s1]) {
d[s1] = d[s2] + 1;
p[s1] = s2;
}
}
string max_s = "";
for (it = d.begin(); it != d.end(); it++)
if (it->second > d[max_s])
max_s = it->first;
cout << d[max_s] << "\n";
string s = max_s;
for (int i = 0; i < d[max_s]; i++) {
cout << s << "-";
s = p[s];
}
cout << s << "\n";
return 0;
}