Editorial for Sazvezdja


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Ukoliko imamo x tačaka i sve leže na istoj pravoj, svaka trojka je kolinearna, pa je broj takvih trojki jednak \binom{x}{3}. Jedno rešenje je da se napravi niz brojeva b_1, b_2, \ldots, b_m takav da važi \binom{b_1}{3} + \binom{b_1}{3} + \ldots + \binom{b_m}{3} = K i da se izgeneriše m pravih, da se na i-tu pravu nanese b_i tačaka, i da se sve ovo uradi na takav način da nijedne tri tačke ne budu kolinearne osim ukoliko potiču sa iste prave.

Ovaj niz brojeva se može naći grabljivim postupkom - dokle god je K > 0, biramo najveće x takvo da je \binom{x}{3} \leq K, dodajemo x na niz i smanjujemo K za \binom{x}{3}. Može se pokazati (na primer, primenom grube sile) da ovaj postupak rezultira u ne više od 1049 tačaka, i to u ne više od 10 koraka.

Za prave možemo izabrati uzastopne različite prave koje su paralelne x-osi, odnosno prave y=1, y=2, \ldots. Tačke možemo ređati počev od koordinate q_i = i^2 \times 10^6 za i-tu pravu, odnosno, na pravoj sa rednim brojem i biće tačke {(q_i, i)}, {(q_i+1, i)}, \ldots, {(q_i+b_i-1, i)}. Ova "konveksnost" obezbeđuje da nijedne tri tačke sa različitih pravih ne budu kolinearne.

Podzadaci se mogu rešiti primenom grube sile ili nekog jednostavnijeg postupka postavljanja pravih.


Comments

There are no comments at the moment.