Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: territoriali.olinfo.it
Creiamo una lista con tutte le persone di cui non conosciamo l'utente seguito, inizialmente questa lista conterrà tutte le persone, ovvero .
Per ogni utente prendiamo persone dalla lista e le assegniamo ad . Questa combinazione non è sempre valido in quanto potrebbe esserci un utente che segue sé stesso, in tal caso riordiniamo a caso l'assegnamento finché non ne troviamo uno valido. In pratica, sono necessari molti pochi riordinamenti per trovarne uno valido.
bool ok(int N, vector<int>& F) {
for (int i = 0; i < N; i++) {
if (F[i] == i) return false;
}
return true;
}
void solve(int t) {
int N;
cin >> N;
vector<int> A(N);
for (int& a : A) {
cin >> a;
}
vector<int> F;
F.reserve(N);
for (int i = 0; i < N; i++) {
F.insert(F.end(), A[i], i);
}
mt19937 rng(696969); // il seed che preferisci
while (!ok(N, F)) {
shuffle(F.begin(), F.end(), rng);
}
cout << "Case #" << t << ":";
for (int f : F) {
cout << " " << f;
}
cout << "\n";
}
Se avessimo che per ogni persona valga , potremmo assegnare i follower in modo circolare, ovvero .
Notiamo adesso che ogni persona ne segue esattamente una, perciò , quindi per ogni valore devono esserci necessariamente persone con follower.
Possiamo quindi far seguire alle persone con follower, le persone con più di un follower in modo che quest'ultime rimangano con solo un follower a testa da assegnare. Facendo ciò è impossibile per una persona con follower seguire sé stessa. Infine possiamo assegnare le persone rimanenti in modo circolare, come descritto prima, garantendo che nessuno segua sé stesso.
void solve(int t) {
int N;
cin >> N;
vector<int> A(N);
for (int& a : A) {
cin >> a;
}
vector<int> Z, C;
for (int i = 0; i < N; i++) {
if (A[i] == 0) {
Z.push_back(i);
} else {
C.push_back(i);
}
}
vector<int> F(N);
for (int i = 0, j = 0; i < N; i++) {
while (A[i] > 1) {
F[Z[j++]] = i;
A[i]--;
}
}
for (int i = 0; i < C.size(); i++) {
F[C[i]] = C[(i + 1) % C.size()];
}
cout << "Case #" << t << ":";
for (int i = 0; i < N; i++) {
cout << " " << F[i];
}
cout << "\n";
}