AtCoder Beginner Contest 040 B - □□□□□

問題について考えたこと

問題文へ

制約が1<=n<=10000より、一つずつ調べてもTLEにならなそうということ。

1メートル四方のタイルなので、整数の乗算除算で解けそうなこと。

使わずに余るタイルの枚数という所から、使い切っているかなどの判定も要らないと考えました。

1*nから、逆転するまで一つずつ調べることにしました。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 100010;


int main(void) {
  int n;
  cin >> n;

  int ans = INF;

  int a = 1;
  int b = n;
  while (a <= b) {
    int num = abs(a - b) + (n - a * b);
    chmin(ans, num);

    ++a;
    b = n / a;
  }

  cout << ans << endl;
  
  return 0;
}