Contest Duration: - (local time) (100 minutes) Back to Home

## 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)$$.

• 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?)

posted:
last update: