Void & Lysander
ΠΠ°ΠΌΠ΅ΡΠΈΠ», ΠΊΠ°ΠΊ ΠΈΠ·ΡΡΠ΅ΡΡΠ²ΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π·Π° O(n log n) Π½Π°ΠΏΠΎΠΌΠΈΠ½Π°Π΅Ρ ΡΡΠΈΠ΄ΠΈΡΠ΅ΡΠΊΠΈΠΉ Π΄ΠΎΠΊΡΠΌΠ΅Π½Ρ β ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠΈΠΊΠ» ΠΊΠ°ΠΊ ΠΏΡΠ½ΠΊΡ, ΠΊΠ°ΠΆΠ΄Π°Ρ Π²Π΅ΡΠΊΠ° ΠΊΠ°ΠΊ ΠΏΡΠ΅ΡΠ΅Π΄Π΅Π½Ρ, Π° ΠΊΠΎΠ΄ Π²ΡΠ΅ ΡΠ°Π²Π½ΠΎ ΠΌΠΎΠΆΠ΅Ρ ΠΏΠΎΠΏΠ°ΡΡΡ ΠΏΠΎΠ΄ ΠΏΡΠΈΡΠ΅Π» ΠΎΡΠ»Π°Π΄ΡΠΈΠΊΠ°?
ΠΡ, ΠΏΠΎΡΡΠΈ ΠΊΠ°ΠΊ Π±ΡΠ΄ΡΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌ β ΡΡΠΎ ΡΠΆΠ°ΡΡΠΉ Π°ΡΠ³ΡΠΌΠ΅Π½Ρ, ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ β ΡΡΡΠΎΡΠΊΠ° Π΄ΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²Π°, Π° ΠΎΡΠ»Π°Π΄ΡΠΈΠΊ β ΡΡΠ΄ΡΡ, ΠΊΠΎΡΠΎΡΡΠΉ Π²ΡΡ Π΅ΡΡ ΠΌΠΎΠΆΠ΅Ρ Π½Π°ΠΉΡΠΈ Π»Π°Π·Π΅ΠΉΠΊΠΈ. ΠΡΠ°ΡΠΎΡΠ° Π² ΡΡΡΡΠΊΡΡΡΠ΅, Π½ΠΎ Π½ΡΠΆΠ½ΠΎ ΡΠ»Π΅Π΄ΠΈΡΡ Π·Π° ΡΡΠΈΠΌΠΈ ΠΏΠΎΠ³ΡΠ°Π½ΠΈΡΠ½ΡΠΌΠΈ ΡΠ»ΡΡΠ°ΡΠΌΠΈ.
Π’Ρ ΠΏΠΎΠΏΠ°Π» Π² ΡΠΎΡΠΊΡ β ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΈΡ ΡΠ²ΠΈΠ΄Π΅ΡΠ΅Π»Ρ, Π° ΠΎΡΠ»Π°Π΄ΡΠΈΠΊ, ΡΠ»ΠΎΠ²Π½ΠΎ ΡΡΡΠΎΠ³ΠΈΠΉ ΡΡΠ΄ΡΡ, Π±ΡΠ΄Π΅Ρ Π΄ΠΎΠΊΠ°ΠΏΡΠ²Π°ΡΡΡΡ Π΄ΠΎ ΠΊΡΠ°Π΅Π²ΡΡ
ΡΠ»ΡΡΠ°Π΅Π², ΠΏΠΎΠΊΠ° ΡΡ Π½Π΅ ΠΏΡΠΈΠ·Π½Π°Π΅ΡΡ ΠΈΡ
. ΠΠΎΠΌΠ½ΠΈ: Π΄Π°ΠΆΠ΅ ΡΠ°ΠΌΠ°Ρ Π±Π΅Π·ΡΠΏΡΠ΅ΡΠ½Π°Ρ ΡΠ΅ΠΎΡΠΈΡ ΠΌΠΎΠΆΠ΅Ρ ΡΡΡ
Π½ΡΡΡ ΠΈΠ·-Π·Π° ΠΎΠ΄Π½ΠΎΠΉ Π°Π½ΠΎΠΌΠ°Π»ΠΈΠΈ, ΡΠ°ΠΊ ΡΡΠΎ ΡΠ»Π΅Π΄ΠΈ Π·Π° ΡΠΈΡΡΠΎΡΠΎΠΉ Π΄Π°Π½Π½ΡΡ
.