» Hlavní » Vzkazy  101110000111010110 

Myslenku mam (nejspis spravnou) ale pocet kroku nesedi + u posledniho cyklu muzete vybrat funkci PC a pak budete pptrebovat jeste jedno kolo vylouceni spatneho...

Vzdy pro potvrzeni funkcniho PC stavi jen polobina z puvodniho N PC ale pro potvrzeni nefunkcniho staci jen rozdil poloviny puvodni a cele aktualni skupiny. M-N/2

Vyberu nahodne jeden PC a ostatnimiho budu testovat dokud NEJMENE polovina zbytku (N-1)/2 neprohlasi ze je OK, pote vim ze tento PC je OK a mohu s nim testovat vsechny ostatni PC ktere neodpovedeli zaporne.
Pokud ale ALESPON polovina odpovi ze je vadny, tak je vadny a vim ze pocitace kere odpovedeli kladne jsou take vadne.
PC kere kere neodpovedeli kladne oznacim jako mnozinu M a postupuji s ni jako s mnozinou N dokud se alespon polovina neschodne na kladnem testu.

Nejhorsi mozny scenar je kdyz spatne PC budou odpovidat vzdy pravdive a ja si vzdy vyberu spatny PC. nadpolovicni vetsina PC = (N+1)/2
Pote bude potreba (N+1)/2*(N-1)/2=(N^2-1)/4