x+y#11796

x+y (Розбір)

Since (r \le 10^5) we can brute force with one iteration.

If we iterate through from to , then y=r-x , but we've forced 0 \le x < y thus we keep iterating and computing until x \ge y then we break and report the count.

r=int(input())
ans=0

for x in range(r+1):
    if(r-x<=x):
        break
    ans+=1
print(ans)

Complexity : .

BONUS : We can optimize the brute force in .

We're counting 0 \le x \le r such r-x > x we get :

r-x > x \implies r>2x \implies \frac{r}{2} > x

This keeps us to casework on even and odd :

  1. is even , then we count all x=0,1,2,..,\frac{r}{2}-1 which is exactly \lfloor \frac{r}{2} \rfloor

  2. is odd , then we count all x=0,1,2,...,\frac{r-1}{2} which is exactly \lfloor \frac{r}{2} \rfloor +1

which is equivalent to \lceil \frac{n}{2}\rceil = \lfloor \frac{n+1}{2} \rfloor.

n=int(input())
print((n+1)//2)

Complexity .