Editorial for Panta Rei


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.

Author: milisav

Posmatrajmo brojeve sa n cifara. Primetimo da je suma kvadrata njegovih cifara najviše n \cdot 9^2, ukoliko broj ima sve devetke, a vrednost, bar 10^{n-1}, što je najmanji broj sa n cifara. Primetimo da nejednakost n \cdot 9^2 < 10^{n-1} važi za sve n \geq 4, tj. da su svi brojevi sa bar četiri cifre pravilni. To tvrdjenje možemo pokazati matematičkom indukcijom po n:

Baza indukcije: n = 4

Primetimo da je suma kvadrata cifara broja sa 4 cifre najviše 4 \cdot 9^2 = 324, a da je najmanji broj sa 4 cifre 1000, pa je svaki broj sa četiri cifre pravilan.

Korak indukcije:  n \implies n+1

Po induktivnoj pretpostavci, važi:

n \cdot 9^2 < 10^{(n-1)}.

Treba da pokažemo da važi:

(n+1) \cdot 9^2 < 10^n

Primetimo:

10^n = 10 \cdot 10^{(n-1)} > 10 \cdot n \cdot 9^2.

Primetimo da je: 10 \cdot n \cdot 9^2 > (n+1) \cdot 9^2, jer 10 \cdot n \cdot 9^2 > (n+1) \cdot 9^2 \iff 10 \cdot n > (n+1) \iff
    9 \cdot n > 1, što je tačno za sve pozitivne cele brojeve n.

Dakle:

(n+1) \cdot 9^2 < 10 \cdot n \cdot 9^2 < 10 \cdot 10^{(n-1)} = 10^n

Čime je induktivna pretpostavka dokazana i dokaz indukcijom gotov.

Analiza složenosti:

Dakle, pokazali smo da su svi brojevi sa bar četiri cifre pravilni. Dovoljno je da za svaki upit L R prođemo kroz najmanjih 1000 brojeva u upitu i proverimo koji od njih su pravilni, a za ostale znamo da su sigurno pravilni jer su veći od L + 1000 > 1000. Tada postižemo rešenje u složenosti O(Q) (uz nezanemarljivu konstantu). Takođe je moguće preračunati sve pravilne brojeve do 1000 i zapamtiti ih u nekom nizu prefiksnih suma.


Comments

There are no comments at the moment.