Pagini recente » Borderou de evaluare (job #2620512) | Cod sursa (job #1945156) | Cod sursa (job #379590) | Cod sursa (job #1832209) | Cod sursa (job #922097)
Cod sursa(job #922097)
// Considerand cazul in care am un singur pion, pot face o dinamica DP[i]=1 daca in cazul in care pionul e aflat in nodul i
// primul jucator castiga
// Se observa ca in cazul in care am mai multi pioni, exista doar o stare cand primul jucator pierde sigur
// si anume cand toate nodurile in care sa afla pioni au DP[i]=0
// Daca exista noduri cu pioni in ele si DP[i]=1, atunci mut din acele noduri pionurile in noduri cu DP[i]=0 si al doilea jucator va ajunge
// intr-o stare cu toti DP[i]=0 deci va pierde
#include <fstream>
#include <vector>
#define NM 30010
using namespace std;
ifstream f("pioni.in");
ofstream g("pioni.out");
int T, N, M, K;
int i, j;
vector<int> G[NM];
bool DP[NM];
int Pawns[NM];
bool Vis[NM];
void DF (int Node)
{
DP[Node]=0;
Vis[Node]=1;
for (vector<int>::iterator it=G[Node].begin(); it!=G[Node].end(); ++it)
{
if (!Vis[*it]) DF(*it);
DP[Node]|=!DP[*it];
}
}
void Solve ()
{
bool win=0;
int nr=0;
for (i=1; i<=K; i++)
{
win|=DP[Pawns[i]];
nr+=DP[Pawns[i]];
}
if (win==0)
{
g << "Fumeanu\n";
return;
}
g << "Nargy\n";
g << nr << ' ';
vector<int>::iterator it;
for (i=1; i<=K; i++)
if (DP[Pawns[i]])
{
g << Pawns[i] << ' ';
for (it=G[Pawns[i]].begin(); it!=G[Pawns[i]].end(); ++it)
if (DP[*it]==0)
{
g << *it << ' ';
break;
}
}
g << '\n';
return;
}
int main ()
{
f >> T >> N >> M;
for (i=1; i<=M; i++)
{
int a, b;
f >> a >> b;
G[a].push_back(b);
}
for (i=1; i<=N; i++)
if (!Vis[i])
DF(i);
for (; T>=1; --T)
{
f >> K;
for (i=1; i<=K; i++)
f >> Pawns[i];
Solve();
}
f.close();
g.close();
return 0;
}