Editorial for COCI '09 Contest 3 #6 Planete

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.

With $X \mid Y$ $X ∣ Y$ we denote that $X$ $X$ divides $Y$ $Y$ , i.e. there exists $k$ $k$ such that $kX = Y$ $k X = Y$ .

Let us denote with $X_1, X_2, \dots, X_m$ $X_{1}, X_{2}, \dots, X_{m}$ duration of events in days. Note that saying:

"Between dates $A$ $A$ and $B$ $B$ there were $\alpha_1$ $α_{1}$ events $1$ $1$ , $\alpha_2$ $α_{2}$ events $2$ $2$ , etc."

is the same as saying:

" $365 \mid (\alpha_1 X_1 + \alpha_2 X_2 + \dots + \alpha_m X_m-(B-A))$ $365 ∣ (α_{1} X_{1} + α_{2} X_{2} + \dots + α_{m} X_{m} - (B - A))$ ".

where $B-A$ $B - A$ is the difference in days between dates $A$ $A$ and $B$ $B$ . Further, we can split that into:

" $5 \mid (\alpha_1 X_1 + \alpha_2 X_2 + \dots + \alpha_m X_m+A-B)$ $5 ∣ (α_{1} X_{1} + α_{2} X_{2} + \dots + α_{m} X_{m} + A - B)$ "
" $73 \mid (\alpha_1 X_1 + \alpha_2 X_2 + \dots + \alpha_m X_m+A-B)$ $73 ∣ (α_{1} X_{1} + α_{2} X_{2} + \dots + α_{m} X_{m} + A - B)$ "

(note that $365 = 5 \times 73$ $365 = 5 \times 73$ ). Since $5$ $5$ and $73$ $73$ are prime numbers, using Gaussian elimination, we can find all possible remainders of $X$ $X$ 's when divided by $5$ $5$ and $73$ $73$ (separately). Using the Chinese remainder theorem, we can further determine the remainder of each $X$ $X$ when divided by $365$ $365$ .

Comments

There are no comments at the moment.