Educational Codeforces Round 146 (Rated for Div. 2) - B. Long Legs (1700)

B. Long Legs

$t \le 100$ 인 것에서 눈치를 챌 수 있다.

그냥 $m$을 증가시키면서 검사해주면 된다는 것을

이례적으로 Div.2 B에 1700 이 찍혔다.

$a=b=10^9$ 일 때 어느정도로 $m$을 증가시켜야 최적일까?

$m=10^6$ 까지 해버린다 하자. 그럼 $a,b$에는 $10^3$ 번만에 각각 도달할 수 있지만, 그럼 $10^6+2 \cdot 10^3$ 이 되버린다.

따라서 적절히 루트에 맞추는 것이 최적임을 알 수 있고, 이는 $m \coloneqq 1 \to \sqrt{ \text{Min}(a,b) }$ 정도까지 해보면 된다는 것을 알 수 있다.

그냥 $10^5$ 까지 하면 된다.

void solve() {  
   int a, b;  
   cin >> a >> b;  
   int ans = 1e9;  
   for (int m = 1; m <= 100000; m++) {  
      mina(ans, m - 1 + (a + m - 1) / m + (b + m - 1) / m);  
   }  
   cout << ans << endl;  
}