241
Cerința
Considerăm un ansamblu format din n
roți dințate, numerotate de la 1
la n
, ca în imaginea alăturată. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers.
Exemplu
gears.in
7 4 1 2 1 3 1 4 1 5 3 6 3 7
gears.out
SDDDDSS
Explicație
#include <bits/stdc++.h> using namespace std; ifstream cin("gears.in"); ofstream cout("gears.out"); int n , x , y , m , p , d[1001] , v[1001]; vector <int> G[1001]; void bfs(int s) { queue <int> Q; v[s] = 1; d[s] = 1; Q.push(s); while(!Q.empty()) { int x = Q.front(); for(int i : G[x]) if(!v[i]) { Q.push(i); v[i] = 1; d[i] = d[x] + 1; } Q.pop(); } } int main() { cin >> n >> p; while(cin >> x >> y) { G[x].push_back(y); G[y].push_back(x); } bfs(p); for(int i = 1 ; i <= n ; i++) if(d[i] % 2 == 1) cout << "D"; else cout << "S"; }
Comentarii