Problemi 108

Kërkesa

Çufoja ka bërë N copa keku të vogla dhe tani po mendon si ti paketojë. Çdo paketë duhet të ketë numër të njëjtë kekësh. Çufoja duhet të zgjedhë një numër të plotë A, nga 1 në N, dhe duhet të vendosë fiks A copa keku në çdo paketë. Pasi ka plotësuar aq paketa sa të jetë e mundur, copat e kekut që kanë mbetur pa paketuar Çufoja mund ti hajë vetë. Çufos i pëlqejnë shumë këta dreq kekë. Sa duhet ta zgjedhë numrin A të paketimit që ti mbeten sa më shumë copa keku për të ngrënë?

Bëni një program që merr numrin N dhe gjen numrin A, ku \(2 \leq N \leq 100000000 (10^8)\) Ky program duhet ta kthejë përgjigjen në më pak se 1 sek.

Referenca: https://www.codechef.com/problems/MUFFINS3

Shembull

$ cat input.txt
2
2
5

$ python3 prog.py < input.txt
2
3

Zgjidhja 1

T = int(input())
for t in range(T):
    n = int(input())
    m = 0   # mbetja
    p = 0   # madhësia e paketës
    for i in range(1, n+1):
        if n % i >= m:
            m = n % i
            p = i
    print(p)

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    print(n // 2 + 1)

Sqarime

Zgjidhja e parë është e ngadaltë kur N-ja është shumë e madhe, p.sh. kur N=100000000 (provojeni!). Kurse zgjidhja e dytë është jashtëzakonisht e shpejtë, sepse nuk i provon të gjitha rastet por e gjen përgjigjen me formulë.