Новини
Форум
Актуално
сървърМай съм сгрешил. Ще проверя. Сигурно трябва да се разглеждат поотделно N - четно и N - нечетно.
Май съм сгрешил. Ще проверя. Сигурно трябва да се разглеждат поотделно N - четно и N - нечетно.
Последно (И - работещ, С - скапан):
--------------------------------------------
За N-четно:
---------------
Питаме първите N-2 какъв е (N-1)-ят.
Ако има най-малко N/2 еднакви отговори - те са дадени от И - компове.
В противен случай - последните два компа са И.
--------------------
За N - нечетно:
--------------------
Ако има най-малко (N/2+0,5) еднакви отговори - те са дадени от И - компове.
Ако има (N/2-0,5) еднакви отговори:
- ако отговорите са И, (N-1)-ят наистина е И.
- ако отговорите са С, работещ е N-тият.
---------------------
---------------------
Доказателството на последния случай:
Еднаквите (N/2-0,5) са или всичките С-та или И-та без едно (тогава в двата последни компа се е скрил един С).
Ако болшинството отговори са С, или (N-1)-ят е С наистина, или е И, но отговорът е даден от цялата дружина С-та. И в двата случая следва, че N-тият е И.
Отговор с цитат