A | B | C | D | E | F | G |
---|---|---|---|---|---|---|
AC | AC | AC | AC | - | - | - |
E
๋ฅผ 1๋ถ ์ฐจ์ด๋ก ์ ์ถํ์ง ๋ชปํ ์
์ด๋ค. ๊ทธ๋์ ํ๋ฌธ์ ์ฐจ์ด๋ก ์๋นํ ๋งํ ํผํฌ๊ฐ ๋์๋ค.
Do you know ๋ฐ๋ณต๋ฌธ?
B ์น๊ณ ๋์ด๋๊ฐ ์๋ ๋ฌธ์ ์๋ค. ์ถ๋ ฅ ๋ฌธ์ ๋ก 1ํ์ ํ๋ค. (์ผ์ด์ค์ค 1๊ฐ์์ ๊ณต๋ฐฑ ์ถ๋ ฅ์ ์ํ๋ค;;) L
๋ณด๋ค ์ผ์ชฝ์ ์์ผ ๊ฒฝ์ฐ L
์ด, R
๋ณด๋ค ์ค๋ฅธ์ชฝ์ ์์ผ ๊ฒฝ์ฐ R
์ด, ๊ทธ ์ฌ์ด์ ๋ค์ด์ฌ ๊ฒฝ์ฐ ์๊ธฐ ์์ ์ด ๋์ด์ผ ๊ฑฐ๋ฆฌ๊ฐ ์ต์๊ฐ ๋๋ค.
์ํ ๋ฌธ์ . ์ํ ๋ฌธ์ ์ธ ๋งํผ ์๋ฃจ์
์ ์ฌ๋ฌ๊ฐ์ง๊ฐ ์์ ์ ์๋๋ฐ, ๋๋ ๊ทธ๋ฅ ๋งค๊ฐ๋ณ์ํ์
์ผ๋ก ํด์น์ ๋ค. ์ ํด๋ ์ด๋ค.
void solve() {scanf("%lld", &N);ll sN = sqrt(N);ll ans = 0x7FFFFFFFFFFFFFFFLL;for(ll y = 0; y <= sN; ++y) {ll l = 0, r = sN + 1;ll yy = y * y;for(ll m = (l + r) >> 1; l <= r; m = (l + r) >> 1) {ll cur = yy + m * m;if (cur <= N) {l = m + 1;ans = min(ans, min(abs(cur - N), abs(yy + (m + 1) * (m + 1) - N)));} else {r = m - 1;}}}printf("%lld\n", ans);}
๋ฌธ์ ๋ ์ฅํฉํ๋ฐ, ๊ฒฐ๊ตญ ์ผ์ด์ค๋ฅผ ๋ฐ์ ธ๊ฐ๋ฉด์ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ฐ์ ธ๋ณด๋ฉด, ๊ฐ row
, col
๋ณ๋ก o
์ ์๋ฅผ ๋ฏธ๋ฆฌ ์ธ์ด๋๊ณ , ๋ชจ๋ ์์ ๋ํด ans += (rcnt[i] - 1) * (ccnt[j] - 1)
๋ฅผ ํด์ฃผ๋ ๊ฒ์ด ๋ต์ด๋ค.
AC
๊ฐ ๋์๋๋ฐ 1๋ถ ๋ฆ์ด์ ์ ์ถ์ ๋ชปํ๋ค. mex
์ฐ์ฐ์ ์ผ์ข
์ ์ฐ๋
ผ ์ฐ์ฐ์ด๊ณ (๋๊ฒ์ ๋ฑ์์ ์ฐ์ด๋๋ฏ), ์ด๋ป๊ฒ ๋น ๋ฅด๊ฒ ๋ค์ ์๋ฅผ ์ฐพ๋์ง๊ฐ ๊ด๊ฑด์ด์๋ค. ์ ํด๋ set
์ด๋ Segment Tree
์๊ณ , ๋๋ ๊ตฌ๊ฐ ๊ด๋ฆฌํ๋ ์์ผ๋ก ํ์๋ค. ๋๋ฌด ์ด๋ ต๊ฒ ํ์ด์ ์๊ฐ๋ด์ ๋ชป๋ธ๊ฑฐ ๊ฐ๋ค.
๋ญ๊ฐ ์ฐ๋ ผ์ ๋์๊ฐ ๋์ ์ ์๋น ์์ .
Skip