Cześć,
Przygotowuję się do Olimpiady Informatycznej Licealistów. Obecnie próbuję rozwiązać to zadanie: https://oi.edu.pl/pl/archive/oi/14/tet
Mój pomysł na algorytm (wiem, że nie jest optymalny, ale chcę sprawdzić, ile można za niego dostac pkt):
- Szukam w wieży pary kolorów, które leżą najbliżej siebie.
- Zbliżam tą parę do siebie, aż się spotka i 2 klocki znikną.
I tak aż cała wieża zniknie. W międzyczasie sprawdzam też, czy na wieży nie zachodzi taka sytuacja:
x
y
x
y
Wtedy od razu wykonuję dwa ruchy tak, żeby ustawić klocki w pozycji
x
x
y
y
i usuwam wszystkie 4 na raz. Pomysł działa dla wszystkich zestawów danych, dla których zdołałem go sprawdzić (czyli raczej niewielkich - sprawdzenie rozwiązania długiego zestawu na kartce zajęłoby zbyt dużo czasu). Poblem polega na tym, że rozwiązanie w systemie przechodzi 5/7 testów wstępnych (1 raz przekroczony czas, 1 raz błąd o którym napiszę zaraz), natomiast spośród testów właściwych przechodzi tylko 1. 9 testów wyrzuca błąd "Strategia nie usuwa wszystkich elementów". Długo szukałem genezy problemu, ale nie potrafię znaleźć. Może ktoś rzuci okiem i sprawdzi, co może być nie tak?
Oto kod:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> tower;
queue<int> moves;
int input;
int movesCount = 0;
for(int i = 0; i < 2 * n; ++i)
{
cin >> input;
tower.push_back(input);
}
int aSwap = -1;
int bSwap = -1;
while(tower.size() > 0)
{
int indexOf[n];
int distances[n];
int smallestDist = 2147483647;
for(int i = 0; i < n; ++i)
indexOf[i] = -1;
/*cout << "_________________________________\n";
for(int i = 0; i < tower.size(); ++i)
{
cout << tower[i] << endl;
}
cout << "\n_________________________________\n";*/
bool calcDists = true;
for(int i = 0; i < tower.size(); ++i)
{
if(tower[i] == tower[i+1])
{
tower.erase(tower.begin() + i, tower.begin() + i + 2);
calcDists = false;
break;
}
if(i > 2)
{
if(tower[i] == tower[i-2] && tower[i-1] == tower[i-3])
{
//cout << "tower[i] = " << tower[i] << ", tower.size() = " << tower.size() << endl;
//cout << "Ruch inwersji: " << tower.size() - i << endl;
moves.push(tower.size() - i);
//cout << "_____________________\nInwersja:\n" << tower[i-3] << "\n" << tower[i-2] << "\n" << tower[i-1] << "\n" << tower[i] << "\n______________________\n";
tower.erase(tower.begin() + i-3, tower.begin() + i + 1);
calcDists = false;
movesCount++;
break;
}
}
if(indexOf[tower[i] - 1] == -1)
{
indexOf[tower[i] - 1] = i;
}
else
{
distances[tower[i] - 1] = i - indexOf[tower[i] - 1];
if(distances[tower[i] - 1] < smallestDist)
{
smallestDist = distances[tower[i] - 1];
aSwap = indexOf[tower[i] - 1];
bSwap = i;
}
}
}
if(!calcDists)
continue;
//cout << "Swap " << aSwap << " z " << bSwap << endl;
int value = tower[aSwap];
movesCount += (bSwap - aSwap - 1);
for(int i = 0; i < (bSwap - aSwap - 1); ++i)
{
moves.push(tower.size() - (aSwap + 1 + i));
//cout << "Ruch swapa " << tower.size() - (aSwap + 1 + i) << endl;
}
tower.erase(tower.begin() + aSwap, tower.begin() + aSwap + 1);
tower.insert(tower.begin() + bSwap - 1, value);
aSwap = bSwap = -1;
}
//cout << "\n\n_____WYNIK____________\n";
cout << movesCount << "\n";
while(!moves.empty())
{
cout << moves.front() << "\n";
moves.pop();
}
}
Mam książkę o konkursie ("25 lat Olimpiady Informatycznej") i w niej jest wzorcowe rozwiązanie, ale zależy mi na tym, żeby dowiedzieć się, co jest nie tak z tym kodem.
C++ 
Shalom