Rozwiązanie zadania obserwatorzy
W zadaniu obserwatorzy odpowiedzi obliczamy dla wszystkich osób w kolejce, poczynając od osoby na początku kolejki. Pierwsza osoba która będzie zasłaniać widok osobie na pozycji i, to albo osoba na pozycji i+1, albo pierwsza osoba która zasłania widok osobie na pozycji i+1, albo pierwsza osoba która zasłania widok tejże osobie, i tak dalej, aż do znalezienia pierwszej wyższej osoby albo osiągnięcia początku kolejki.
Pomimo że w pesymistycznym przypadku, dla danego obserwatora musi w ten sposób rozważyć wszystkie osoby stojące wcześniej w kolejce, to gdy raz jakiegoś obserwatora pominiemy, nie będzie on już rozważany ponownie, więc wszystkie odpowiedzi możemy wyznaczyć w czasie liniowym.
Suggested Topics
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| Fraktal XX | Konkursy | 6 | 197 | Mar 25 |