B - KEYENCE building Editorial by en_translator

The original version of this problem was proposed by members of KEYENCE Corp.

It is sufficient to solve the following problem \(N\) times: “do there exist \(a\) and \(b\) such that the area is equal to some given \(S\)?” Let us brute force over every \(a\) and \(b\).

If \(a > S\) or \(b > s\), then the area \(4ab+3a+3b\) is obviously greater than \(S\). Therefore, we may brute force over \(a\le S\) and \(b\leq S\).

The complexity is \(O(N \max(S_i)^2)\).

Sample code (C)
Sample code (Python)

  • Bonus 1:Solve for \(N\leq 10^6\)\(S_i\leq 10^3\). (Worth 300 points?)
  • Bonus 2:Solve for \(N\leq 10^6\)\(S_i\leq 10^5\) (Worth 400 points?)
  • Bonus 3:Solve for \(N\leq 10^3\)\(S_i\leq 10^8\) (Worth 400 points?)

last update: