B. Long Legs

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

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

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

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

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

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

그냥 10510^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;  
}

Comments

You may also enjoy