2020๋
XNUMX์ ICPC ์ธ๊ณ ํ๋ก๊ทธ๋๋ฐ ์ฑํผ์ธ์ญ ๊ฒฐ์น์ ์ ๋ชจ์คํฌ๋ฐ์์ ์ฒ์์ผ๋ก ๊ฐ์ต๋๋ฉฐ MIPT๊ฐ ์ฃผ์ตํฉ๋๋ค. ์๋์ ์ค์ํ ํ์ฌ ์ ๋
ํ๋ จ์ ์ฐธ๊ฐ๊ฐ ์น๋ฆฌ์ ์ฌ๋ฐ๋ฅธ ๊ธธ์ธ ์ด์ ๋ฅผ ๋งํ๋ค. ํ๋ฆฝ ๋ฃจ์ฝ๋น์น, ๋ชจ์คํฌ๋ฐ ์ํฌ์ ICPC ์ฝ์น, 2007-2009๋ ์ ๋ณดํ ๋ถ์ผ ์ ๋ฌ์์ ํ์์ ์ํ ์ฌ๋ฆผํผ์๋์์ 2014ํ ์ฐ์น์์ด์ ์ฐ์น์, XNUMXํ ICPC ์ค๊ฒฐ์น ์ง์ถ์์ด์ ICPC XNUMX ๊ฒฐ์น ์ง์ถ์์ ๋๋ค.
Philip์ MIPT Shock Content ํ์ ๋ฉค๋ฒ์ธ Evgeny Belykh์ ํจ๊ป ํฌ๋ฅดํฌ์์ ์ด๋ฆฐ 10 ICPC ๊ฒฐ์น์ ์์ 2019์๋ฅผ ์ฐจ์งํ๊ณ ๋๋ฉ๋ฌ์ ํ๋ํ์ต๋๋ค.
ํ๋ จ ์บ ํ ์ฐธ์ฌ ๋ฐฉ๋ฒ ๋ฐ ์๊ธฐํ๋ จ ์บ ํ์๋ ์ ํต์ ์ผ๋ก ๊ฐ์, ์ธ๋ฏธ๋, ์ฝํ
์คํธ๊ฐ ํฌํจ๋ฉ๋๋ค. ์ง์ ์์ค์ ๋ฐ๋ผ ํ์๋ค์ ๋ค ๊ฐ์ง ๋ถ๋ฌธ์ ์ฐธ์ฌํ ์ ์์ต๋๋ค.
A: ICPC ๊ฒฐ์น์ ์์ ์น๋ฆฌ๋ฅผ ์ค๋นํ๊ณ ์์ต๋๋ค.
B: ์ฑํผ์ธ์ญ ์ค๊ฒฐ์น ์ค๋น;
C: ์์ ๋ผ์ด๋ ๋ฐ ICPC ์ฑํผ์ธ์ญ ยผ ์ค๋น;
D: ICPC์ ์ธ๊ณ๋ฅผ ์ฒ์ ์ ํ๋ ์ฌ๋๋ค์ ์ํ ๊ฒ์
๋๋ค.
๊ทธ ์ค ์ฒซ ๋ฒ์งธ ๋ชจ์คํฌ๋ฐ ์ํฌ์ต ICPC์ ํ๋ ฅํ์ฌ ๋ธ๋ผ๋๋ณด์คํ ํฌ๋ฅผ ๋ฐ๊ฒฌํด๋ณด์ธ์ 6๋ 13์ 2019์ผ๋ถํฐ 7์ XNUMX์ผ๊น์ง ๊ทน๋์ฐ๋ฐฉ๋ํ๊ต์์ ๊ฐ์ต๋ฉ๋๋ค. ๊ทธ ๋ค๋ฅผ ์ด์ด XNUMX์ XNUMX์ผ ๋ฒจ๋ก๋ฃจ์์ ๊ทธ๋ก๋๋ ธ์ ํ๋ จ ์บ ํ๊ฐ ์ด๋ ธ์ต๋๋ค. ์ค๊ตญ, ๋ฉ์์ฝ, ์ด์งํธ, ์ธ๋, ๋ฆฌํฌ์๋์, ์๋ฅด๋ฉ๋์, ๋ฐฉ๊ธ๋ผ๋ฐ์, ์ด๋, ๊ธฐํ ๊ตญ๊ฐ ๋ฐ ๋ฌ์์์ ์ฌ๋ฌ ์ง์ญ์์ ์จ ์ ์ ํ๋ก๊ทธ๋๋จธ๋ค์ด ํ๋ จ์ ์ํด ์์ต๋๋ค.
์์๋ฃ ์ผ์
6์ 13์ผ๋ถํฐ XNUMX์ผ๊น์ง - ๋ธ๋ผ์๋ณด์คํ ํฌ๋ฅผ ๋ฐ๊ฒฌํด๋ณด์ธ์ ๋ถ์ B ๋ฐ C๋ฅผ ์ํด ๋ชจ์คํฌ๋ฐ ์ํฌ์ต ICPC์ ํ๋ ฅํฉ๋๋ค.
7์ 14์ผ๋ถํฐ XNUMX์ XNUMX์ผ๊น์งโ ๊ทธ๋ก๋๋ ธ๋ฅผ ๋ฐ๊ฒฌํด๋ณด์ธ์ ๋ถ์ B ๋ฐ C๋ฅผ ์ํด ๋ชจ์คํฌ๋ฐ ์ํฌ์ต ICPC์ ํ๋ ฅํฉ๋๋ค.
7์ 14์ผ๋ถํฐ XNUMX์ผ๊น์ง โ ์ฒ์์ผ๋ก ๋ฐ์ด์นผ์ ๋ฐ๊ฒฌํด๋ณด์ธ์ ๋ถ์ C ๋ฐ D์ ๋ํ ๋ชจ์คํฌ๋ฐ ์ํฌ์ ICPC์ ํ๋ ฅํ์ฌ.
21์ 29์ผ๋ถํฐ XNUMX์ผ๊น์ง โ ์ฒ์์ผ๋ก ์ฑ๊ฐํฌ๋ฅด๋ฅผ ๋ฐ๊ฒฌํด๋ณด์ธ์ ๋ถ๋ฌธ A์ ์ธํธ B ๋๋ C์ ๋ฐ๋ผ ๋ชจ์คํฌ๋ฐ ์ํฌ์ต ICPC์ ํ๋ ฅํฉ๋๋ค.
5์ 13์ผ๋ถํฐ XNUMX์ XNUMX์ผ๊น์ง โ ์ฒ์์ผ๋ก ๋ฆฌ๊ฐ๋ฅผ ๋ฐ๊ฒฌํด๋ณด์ธ์ ๋ชจ์คํฌ๋ฐ ์ํฌ์ต ICPC์ ํ๋ ฅํ์ฌ A ๋ถ๋ฌธ๊ณผ B ๋๋ C ๋ถ๋ฌธ์ด ๊ฐ์ค๋ ์์ ์ ๋๋ค.
๊ทธ๋ฆฌ๊ณ ICPC ์ค๊ฒฐ์น์ ์ ์๋๊ณ ์ค๋นํ ์ ์๋ ๋ง์ง๋ง ๊ธฐํ๋ ํ๋ จ์บ ํ๋ค. ๋ชจ์คํฌ๋ฐ ๊ตญ์ ์ํฌ์ ICPC, ๋ 5์ 14์ผ๋ถํฐ XNUMX์ผ๊น์ง MIPT ์บ ํผ์ค์์ ์ต๊ฐ ๋๋น์ A, B๋ฅผ ๋์์ผ๋ก ์งํ๋ฉ๋๋ค.
์ฒ์ฌ๋ 1%์ ์ฌ๋ฅ๊ณผ 99%์ ๋ ธ๋ ฅ์ด๋ผ๊ณ ํ์์์. ์คํฌ์ธ ํ๋ก๊ทธ๋๋ฐ์ ๊ด์ฌ์ด ์๋ ํ์๋ค๋ ๋ง์ฐฌ๊ฐ์ง์ธ๊ฐ์?
๋๋ ์ด๊ฒ์ ๋์ํฉ๋๋ค. ๋ฌผ๋ก ์ด ๋ถ์ผ์ ํ๊ณ ๋ ์ฌ๋ฅ๊ณผ ์ฑํฅ๋ ์ค์ํ๋ค. ์ด ์ฌ๋๋ค์๊ฒ๋ ์กฐ๊ธ ๋ ์ฌ์ธ ๊ฒ์ด์ง๋ง ์ด์ฌํ ์ผํ๊ณ ๋ง์ ํ๋ จ ์์ด๋ ๋์์๋ ๋ ธ๋ ฅ ์์ด๋ ์ฑ๊ณต์ด ๋ถ๊ฐ๋ฅํฉ๋๋ค. ํ์ง๋ง ๊ทธ๋ณด๋ค ๋ ์ค์ํ ๊ฒ์ ์ฌ๋ฅ, ์ฌ๋ฐ๋ฅธ ํ ์ ํ ๋ฐ ๊ธฐํ ์ฌ๋ฌ ์์์ ๋ํด ์ด์ผ๊ธฐํ ์ ์๋ค๋ ๊ฒ์ ๋๋ค. ์ฌ๋ฆผํผ์๋ ์ฐธ๊ฐ์ ๊ฐ์๋ ์์ ๋ง์ ์ฅ์ ์ ๊ฐ๊ณ ์๋ ๊ฒ์ด ๋ถ๋ช ํฉ๋๋ค. ์ด๋ค ์ฌ๋์ ๋ณต์กํ ์์คํ ์ ์ฝ๋ฉํ๋ ๋ฐ ๋ฅ์ํ๊ณ , ๋ค๋ฅธ ์ฌ๋์ ์ํ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ ๋ฅ์ํฉ๋๋ค. ๊ทธ๋ฌ๋ ๊ทธ๋ค์ด ๋๊ตฌ์ด๋ ๋จผ์ ํ์์ด ํ์ํฉ๋๋ค. ์ฒ์์๋ ์ด๋ฅ๋ ฅ์ด ์์๋ ํ์ด ์ด์ฌํ ์ผํ๊ณ , ์์ฒญ๋ ์์ ํ๋ จ์ ํตํด ์์ฒญ๋ ์ฑ๊ณต์ ๊ฑฐ๋๊ณ , ์ฌ์ง์ด ์คํฌ์ธ ํ๋ก๊ทธ๋๋ฐ ์ธ๊ณ ์ ์๊ถ ๋ํ์์ ์ฐ์นํ๋ ๊ฒฝ์ฐ๊ฐ ์ข ์ข ๋ฐ์ํฉ๋๋ค. ๋ฌผ๋ก ์ฌ๊ธฐ์ ์ผํ๋ ๊ฒ์ ๋งค์ฐ ์ค์ํ๋ฉฐ ์ด๊ฒ์ด ๊ฐ์ฅ ์ค์ํ ๊ฒ์ ๋๋ค. ๋์์ด ๋ ์ ์๋ ๊ฐ์ฅ ์ค์ํ ์์๋ ๋ชจ๋ ๊ฒ์ ์ฆ๊ธฐ๋ ๊ฒ์ ๋๋ค. ์ ์๊ฐ์๋ ์คํฌ์ธ ํ๋ก๊ทธ๋๋ฐ์์ ์ฑ๊ณตํ๋ ค๋ฉด ์คํฌ์ธ ๋ฅผ ์ ๋ง ์ข์ํ๊ณ ๋ฌธ์ ํด๊ฒฐ์ ์ข์ํด์ผ ํฉ๋๋ค.
ํ์๋ค์ด ํ๋ จ ์บ ํ์ ์ฐธ์ฌํ๋ ค๋ฉด ์ด๋ค ๊ธฐ์ ๊ณผ ์ง์์ด ํ์ํฉ๋๊น?
์ฐ๋ฆฌ๋ ์์น์ ์ธ ์ ๋ฐ ๊ณผ์ ์ ๊ฐ๊ณ ์์ง ์์ผ๋ฉฐ, ํ์๋ค์ด ์์ ์ฐธ์ฌํฉ๋๋ค. ํ์ํ ์ง์ ์์ค์ ์
ํํ๋ ๋ถ์์ ๋ฐ๋ผ ๋ค๋ฆ
๋๋ค. ์ฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์ด๋ ค์ด ๋ถ๋ฌธ์ A์
๋๋ค. ์ด๋ณด ํ์ด ๊ฑฐ๊ธฐ๊น์ง ๊ฐ ํ์๋ ์์ต๋๋ค. ๋๋น์ A๋ ์ด๋ฏธ ๋ชจ๋ ์๊ณ ๋ฆฌ์ฆ์ ์๊ณ ์๊ณ ์๋
๊ฐ ๋ฌธ์ ํด๊ฒฐ ๊ฒฝํ์ ๊ฐ๊ณ ์์ผ๋ฉฐ ๋ชจ์คํฌ๋ฐ์์ ์ด๋ฆฌ๋ 2020 ๊ฒฐ์น์ ์ฑํผ์ธ์ญ์ ์ํด ํ๋ จํ ๊ฐ์ฅ ๊ฒฝํ์ด ํ๋ถํ ์ฐธ๊ฐ์๋ฅผ ์ํด ๋ง๋ค์ด์ก์ต๋๋ค. ์ค๊ฒฐ์น์ ์ ์ค๋นํ๋ ๋ถ๋ค, ๊ฒฝํ์ด ์กฐ๊ธ ๋ถ์กฑํ ์ฐธ๊ฐ์๋ค์ ์ํ ๋ถ๋ฌธ B๊ฐ ์์ต๋๋ค. ์ฃผ์ ๋ณ ์ฝํ
์คํธ์ ๋ณต์กํ ์๊ณ ๋ฆฌ์ฆ์ ๋ํ ๊ฐ์๋ ์์ต๋๋ค.
์ด๋ณด์๋ค์ Grodno์ ํ๋ จ ์บ ํ์ ์์ Division C์ ๊ด์ฌ์ด ์์ต๋๋ค. ICPC ๋ํ ์ฐธ๊ฐ์ ๋ํ ์ต์ํ์ ๊ฒฝํ์ด ํ์ํ๋ฉฐ, ๊ฐ๋จํ ์๊ณ ๋ฆฌ์ฆ์ ๋ํ ๊ฐ์๊ฐ ์์ ์์ ์
๋๋ค. ํ์ง๋ง ์ฒ์๋ถํฐ ์ฌ ์ ์๋ค๊ณ ๋งํ ์๋ ์์ต๋๋ค. ํ๋ จ์บ ํ์ ์ฑ๊ณต์ ์ผ๋ก ์ฐธ์ฌํ๋ ค๋ฉด ๋ฌด์์ด ํ์ํฉ๋๊น? ํ๋ก๊ทธ๋๋ฐ ์ธ์ด ์ค ํ๋(์ฃผ๋ก C++ ๋ฐ Java), ์ฝ๊ฐ์ Python, ๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ ๊ต์ก(์ ์ด๋ ์ต์ํ)์ ์ฌ์ฉํ์ฌ ํ ์ ์ฒด๋ฅผ ์์ ๊ฐ ์๊ฒ ์งํํฉ๋๋ค. ๊ทธ๋ฌ๋ ์ฐ๋ฆฌ ํ๋ก๊ทธ๋จ์ ํ์๋ค์ ์ง์๊ณผ ๊ธฐ์ ์ ๋ฐํ์ผ๋ก ๊ตฌ์ฑ๋์์ต๋๋ค. ์ฐ๋ฆฌ๋ ์ฐธ๊ฐ์๋ค์ ๊ธฐ์ ์ ๋ํด ์ธํฐ๋ทฐํ๊ณ ํ๋ จ ์บ ํ์ ์ค๋ ํ์๊ฒ ํฅ๋ฏธ๋กญ๊ณ ํจ๊ณผ์ ์ธ ํ๋ก๊ทธ๋จ์ ๋ง๋ค๊ธฐ ์ํด ๋
ธ๋ ฅํฉ๋๋ค.
์ค๋น ํ์์ด ๊ฒฐ๊ณผ์ ํฐ ์ํฅ์ ๋ฏธ์น๋์? ์ง์์ ์ค๋นํ๋ ๊ฒ๊ณผ ํ๋ จ ์บ ํ์ ์ค๋ ๊ฒ, ๊ทผ๋ณธ์ ์ธ ์ฐจ์ด๊ฐ ์๋์?
๋๊ตฌ๋ ์์ ๋ง์ ์ค๋น ํ์์ ์ ํํ์ง๋ง ์ฑ๊ณต์ ์ธ ์ฐธ์ฌ๋ฅผ ์ํด์๋ ์ฒด๊ณ์ ์ด์ด์ผ ํฉ๋๋ค. ํ๋ จ ์บ ํ์์ ํ ๋ฒ์ ํ๋ จ ์ธ์ ์ ๊ฑฐ์น๊ณ ๋ํ์์ ์ฆ์ ๋ชจ๋ ์ฌ๋์ ์ด๊ธธ ์๋ ์์ต๋๋ค. ๋ด ์๊ฐ์๋ ํ๋ จ ์บ ํ์ ์ฐธ์ฌํ๋ ๊ฒ์ด ํ์ํ๋ค๋ ๊ฒ์ ๋๋ค. ๋จผ์ , ํ ๋ฒ๋ ๊ฐ๋ณธ ์ ์ด ์๋ ๋ค๋ฅธ ๋์์ ๋์ฐฉํฉ๋๋ค. ๋ชจ์คํฌ๋ฐ ์ํฌ์์ ๊ณผ์ฅ ์์ด ์ ์ธ๊ณ์์ ๊ฐ์ต๋๊ธฐ ๋๋ฌธ์ ์ฌํํ ์ ์์ต๋๋ค. ๊ฐ์ฅ ๊ฐ๊น์ด ๋ํ๋ ๋ธ๋ผ๋๋ณด์คํ ํฌ์ ๊ทธ๋ก๋๋ ธ์์ ๊ฐ์ต๋ฉ๋๋ค. ํ์ง๋ง ํ๋ จ์์์ ๊ฐ์ฅ ์ค์ํ ๊ฒ์ ๋ถ์๊ธฐ๋ค. ์ง์์ ์ฝํ ์คํธ๋ฅผ ์์ฑํ๋ฉด ํ์์ฒ๋ผ ํ๋ จํ๊ณ ์ฃผ๋ณ์ ๋ชจ๋ ๊ฒ์ด ๋๊ฐ์ ์ผ์์ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ํ๋ จ์์ ์ค๋ฉด ์ผ์์ ์ธ ํ๊ฒฝ์์ ๋ฒ์ด๋ ํ๋ จ์์๋ง ์ง์คํ๊ฒ ๋๋ค. ์๋ฌด๊ฒ๋, ํ ์ผ๋, ๊ณต๋ถ๋, ์ผ๋ ์๊ฐํ์ง ์์ ๋ ๋๋ฌด ๊ฐ๋ ฌํฉ๋๋ค. ํ๋ จ์ ์ง์คํ๊ณ ๊ณ์ญ๋๋ค. ๊ฒฝํ์ด ํ๋ถํ ์ฐธ๊ฐ์, ICPC ๋ฒ ํ ๋๊ณผ์ ์ปค๋ฎค๋์ผ์ด์ ์ ์ ๊ทผํ ์ ์์ต๋๋ค. ์ด๋ ํ๋ก๊ทธ๋๋ฐ์ ์ข์ํ๊ณ ๊ฐ์ ์๊ฐ์ ๊ฐ์ง ์ฌ๋๋ค์ ๋ง๋ ์ ์๋ ์ข์ ๊ธฐํ์ ๋๋ค. ๊ฒฐ๊ตญ ์คํฌ์ธ ํ๋ก๊ทธ๋๋ฐ์ ๊ฐ์ฅ ์ค์ํ ๊ตฌ์ฑ ์์๋ ๋์ผํ ICPC ์ปค๋ฎค๋ํฐ, ๋ฐ๋ก ์ฐ๊ฒฐ์ ๋๋ค. ์ฌ๋๋ค์ ์ด ๋ถ์ผ์์ ์๋ง์ ์ ๋ฅํ ์ฌ๋๋ค์ ์๊ฒ ๋ ๊ฒ์ด๋ฉฐ, ์ด๋ ๊ทธ๋ค์ ๋ฏธ๋ ๊ฒฝ๋ ฅ์ ๋์์ด ๋ ๊ฒ์ ๋๋ค.
ํ๋ จ ์บ ํ๋ ํ ๋ด ๋ถ์๊ธฐ์ ์ด๋ค ์ํฅ์ ๋ฏธ์น๋์? ์ด๊ฒ์ด ๊ฒฐ์ ์ ์ธ ๊ฒฝ์์์ ๋์์ด ๋ฉ๋๊น?
๋ฌผ๋ก ๋์์ด ๋๊ณ ์์ฃผ ์ข์ต๋๋ค. ์ ์ด๋ ๊ณ ์ ์ ์ธ ํ๋ จ์ ๋ค์๊ณผ ๊ฐ๊ธฐ ๋๋ฌธ์ ๋๋ค. ์ธ ์ฌ๋์ด ํจ๊ป ๋ชจ์ฌ ์ฝํ ์ธ ๋ฅผ ์์ฑํ๊ณ ์ง์ผ๋ก ๋์๊ฐ์ต๋๋ค. ํ๋ จ ์บ ํ์์๋ ์๋ํ์ง ์์ต๋๋ค. ๊ทธ๊ณณ์์ ํ์ ์ผ์ฃผ์ผ ๋ฐ์ ํจ๊ป ๋ณด๋ด๊ณ ์ฐธ๊ฐ์๋ค์ ํจ๊ป ์ํํ๊ณ ํจ๊ป ํ๋ จํ๋ฉฐ ์ด๋ฐ ์๋ฏธ์์ ์กฐํ๋กญ๊ฒ ํธํกํฉ๋๋ค. ๋ชจ์์ ํ ํํฉ์ ํฌ๊ฒ ๊ธฐ์ฌํฉ๋๋ค. ๋ํ์์ ์ต๊ณ ์ ๊ฒฐ๊ณผ๋ฅผ ์ป๊ธฐ ์ํด์๋ ์๋ก๋ฅผ ์์๊ฐ๊ณ , ์๋ก์ ์ฅ์ ์ ํ์ฉํ๋ ๋ฐฉ๋ฒ์ ์ดํดํ๋ ๊ฒ๋ณด๋ค ๋ ์ข์ ๋ฐฉ๋ฒ์ ์์ต๋๋ค.
์ ํต์ ์ผ๋ก ๊ตญ์ ํ๋ จ ์บ ํ๋ ๊ฒฝ์์ด ์น์ดํ ํ๊ฒฝ์์ ์งํ๋ฉ๋๋ค. ์ด๋ค ํ์ ๋ ๊ฐํ๊ณ ์ด๋ค ํ์ ๋ ์ฝํ๋ค๋ ๊ฒ์ ์ดํดํ ๋ ์ฑํผ์ธ์ญ์ ์ํ ๋ฏธ๋์ ๋ผ์ด๋ฒ๊ณผ์ ์์ฌ์ํต์ด ์ ์๋ค์๊ฒ ์ด๋ค ์ํฅ์ ๋ฏธ์น๋์?
๊ทธ๊ฒ์ ๋ชจ๋ ๋จ์๋ค์ด ์ผ์ ์ง์คํ๋๊ฐ์ ๋ฌ๋ ค ์์ต๋๋ค. ์ด๋ก ์ ์ผ๋ก๋ ํ์ด ๋์ฐฉํ์ฌ n์๋ฅผ ์ฐจ์งํ๊ณ ํ๊ฐ ๋์ ๋ฏฟ์์ ์์์ ์๋ ์์ต๋๋ค. ํ์ง๋ง ํฉ์์ ์ข์ ์ ์ ํฉ์ ์์ฒด์ ๊ฒฐ๊ณผ๊ฐ ์ค์ํ์ง ์๊ณ , ๋ํ ์์ฒด์์ ๊ณ ๋ ค๋์ง ์๋๋ค๋ ์ ์ด๋ค. ์ด๋ค ์ฝํ ์คํธ์์๋ ์ง๊ธ ์ฌ๊ธฐ์์ ์ ์๋ ๋ฌธ์ ๋ฅผ ๊ฐ์ฅ ๋ง์ด ํด๊ฒฐํ ์ฌ๋์ด ์น์๊ฐ ๋ฉ๋๋ค. ์ค๋ซ๋์ ๋ํ๋ฅผ ์ฃผ๋ํด์จ ํ์ด ๊ฒฐ์น์ ์ง์ถํ์ง ๋ชปํ๋ ์ ๋ก๋ ์๋ค. ์ด๊ฒ์ ์์ ํ ์คํฌ์ธ ์์น์ ๋๋ค. ์น์๋ ๋ ๋ง์ ๊ฒฝํ์ ๊ฐ์ง ์ฌ๋์ด ์๋๋ฉฐ, ์ด๋ค ์ธก๋ฉด์์๋ ๋ ๊ฐํ ํ์ด ์๋๋ผ ์ง๊ธ ์ฌ๊ธฐ์์ ์ต๊ณ ์ ๊ฒฐ๊ณผ๋ฅผ ๋ณด์ฌ์ฃผ๋ ์ฌ๋์ด ์น์์ ๋๋ค. ํ์ง๋ง ๊ฐ์ฅ ๊ฐํ ์ฌ๋๊ณผ ํจ๊ป ํ๋ จํ๋ฉด ์ค์ ์์ค์๋ณด๋ค ๊ฐ๊ด์ ์ผ๋ก ํ๊ฐํ ์ ์์ต๋๋ค. ๋งค์ฐ ๋์ ์๋ฆฌ๋ฅผ ์ฐจ์งํ์ง ์์ผ๋ฉด ๋ ์ ๊ทน์ ์ผ๋ก ํ๋ จํด์ผ ํจ์ ์ดํดํฉ๋๋ค. ํ๋ จ ์บ ํ์์๋ ์ฃผ์ํด์ผ ํ ์ฌํญ์ ๋ํ ์์ ํ ์์ด๋์ด๋ฅผ ์ป์ ์ ์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ฌ๋ฆฌ์ ์ผ๋ก ์ฐ๋ฆฌ๊ฐ ๋ฆฌ๋๋ค๊ณผ ํจ๊ป ํ๋ จํ ๋ ์ฐ๋ฆฌ๋ ๊ทธ๋ค์ ๋ฐ๋ฅด๊ธฐ ์์ํฉ๋๋ค. ํ๋ จ ์บ ํ์์๋ ๊ทธ๋ค๊ณผ ์ํตํ๊ณ , ํด๊ฒฐ์ฑ ์ ๊ตํํ๊ณ , ์ง๋ฌธํ ์ ์์ต๋๋ค. ์ฌ๊ณ ๋ฐฉ์์กฐ์ฐจ๋ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ํฅ์ ๋ฏธ์น ์ ์๊ธฐ ๋๋ฌธ์ ์ฌ๋ฌ ๊ตญ๊ฐ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ์์ ํน์ ์ถ์ธ๋ฅผ ํ์ ํ ์๋ ์์ต๋๋ค. ์ง์์ ์ค๋นํ๋ ๊ฒ๋ณด๋ค ํ๋ จ์บ ํ์ ์ฐธ์ฌํ๋ ๊ฒ์ด ๊ฐ์น ์๋ ๋ ๋ค๋ฅธ ์ด์ ๋ค.
๊ฐํ ํ์ด ํ๋ จ ์บ ํ์ ์ค๊ณ ์๊ฐ์ด ์ง๋จ์ ๋ฐ๋ผ ์ฒ์์๋ ์กฐ๊ธ ๋ ์ฝํ ํ์๊ฒ ์ง๊ธฐ ์์ํ๋ ์ผ์ด ๋ฐ์ํฉ๋๊น?
์ผ๋ถ ์ํฉ์์ ํ์ด ์ฝํ ๊ฒฐ๊ณผ๋ฅผ ๋ณด์ด๋ ๋ฐ๋ ์ฌ๋ฌ ๊ฐ์ง ์ด์ ๊ฐ ์์ต๋๋ค. ๋จ์ํ ํผ๋ก๋ถํฐ ์์ํ๋ฉด ํ ๋ฌ ์์ ์ธ ๋ฒ์งธ ํฉ์์ด ๋ ์๋ ์๊ธฐ ๋๋ฌธ์ด๋ค. ๋ชจ์คํฌ๋ฐ ์ํฌ์ต ๋ชจ์์ด ์ ์ ๋ ๋ง์์ง๊ณ ์์ผ๋ฏ๋ก ์ฌ๋๋ค์ด ์ด๋ฏธ ์จ ํ์ ๋คํด ๊ฒฝ์ํ๊ณ ์์ ๊ฐ๋ฅ์ฑ์ด ์์ต๋๋ค. ํ๋ จ ์ค ํด์ ๋ฌธ์ ๋ ๊ทธ๋ค์ง ์ค์ํ์ง ์์ต๋๋ค. ๊ณผํ๊ฒ ์ฌ์ฉํ๋ฉด ์์ง๋ ์ํ์ด ์์ต๋๋ค. ์ค์ํ ๋ํ ์ง์ , ํ๋ ์ฃผ ์ ๋ถํฐ ๋ถํ์ํ ๋ํ์ ์๋์ง๋ฅผ ๋ญ๋นํ๋ ๊ฒ์ด ์๋๋ผ, ์์ผ๋ก ๋ค๊ฐ์ฌ ์ผ์ ์ง์คํ๊ณ ์ต์ ์ ๋คํ๋ ๊ฒ์ด ๊ณผ์ ์ ๋๋ค. ์๋ฅผ ๋ค์ด, ์ฌ๋ฌ ๋๋ผ์ ์ฃผ์ ๊ธฐ์ ๋ํ ํ์๋ค์ด ์ฐธ๊ฐํ๋ ์ธ๊ณ ํ๋ก๊ทธ๋๋ฐ ์ฑํผ์ธ์ญ ์ค๊ฒฐ์น์์. ์ ํต์ ์ผ๋ก ์ฝํ ์คํธ๋ ์ผ์์ผ์ ์ด๋ฆฌ๋ฉฐ ํ ์์ผ์ ๋์ฐฉํ๊ณ ๊ฐ๋งํฉ๋๋ค. ์ฌ๋๋ค์ ๋ณดํต ๊ธ์์ผ ์์นจ์ ๋์ฐฉํ๋ฉฐ, ๊ทธ๋ค์ ์๋ฌด๋ ์ด๋ ์ต๋ํ ํด์์ ์ทจํ๊ณ ํ๊ต๋ฅผ ์ค๋จํ๊ณ ์๋ก์ด ๋์์ ๋ํ ์ธ์์ ์ป๋ ๊ฒ์ ๋๋ค.
2020๋ ICPC ๊ฒฐ์น์ ์ ๋ชจ์คํฌ๋ฐ์์ ์ด๋ฆด ์์ ์ด๋ค. ๊ฒฐ์น์ ์ ์ ํฅ๋ถ์ด ๋ชจ์คํฌ๋ฐ ํ๋ จ ์บ ํ์ ์ํฅ์ ๋ฏธ์น ๊น์, ์๋๋ฉด ํ์๋๋ก ์ผ์ด ์งํ๋๊ณ ์์ต๋๊น?
๋ชจ์คํฌ๋ฐ ๊ฒฐ์น์ ์ ์ด๋ก์ ์ธ ํ์ฌ๋ค. ๋ฌผ๋ก ์ด๋ฒ ๊ฒฐ์น์ ์ด ๋ฌ์์์์ ์ฒ์์ ์๋์ง๋ง ๋ชจ์คํฌ๋ฐ์ ์ค๋ ๊ฒ์ ์ฒ์์ด๋ค. ๋๋ ์ด๊ฒ์ด ์๋์์ ๊ฒฐ์น์ ์ ์ค๋นํด์ผ ํ๋ค๋ ๊ฒ์ ์๋ฏธํ๋ ๊ฒ์ด ์๋๋ผ ๋ค๋ฅธ ์ฌ๋๋ค์ ์ํด์๊ฐ ์๋๋ผ๋ ๊ฒ์ ์๋ฏธํ๋ค๊ณ ๋งํ ๊ฒ์ ๋๋ค. ๊ทธ๋ฌ๋ ์ฐ๋ฆฌ๋ ํ์คํ ๊ฑฑ์ ๋ฉ๋๋ค. 5๋ ๋ง์ ๊ฒฐ์น์ ์ด ๋ฌ์์๋ก ๋์์๋ค๋ ๊ฒ์ ํฐ ์๊ด์ด์ ๋ง์คํ ์ฑ ์์ด๊ธฐ๋ ํ๋ค. ์ฌ๋ฆผํผ์๋ ํ๋ก๊ทธ๋๋ฐ์ ์ด์ ์ ๊ฐ๊ณ ์๋ ๋ชจ๋ ํ์๋ค์ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ ํ๋ จ ์บ ํ์ ์ฃผ์ต์์ ์ฐธ๊ฐ์ ๋ชจ๋๋ฅผ ์ง์ค์ ์ผ๋ก ์ค๋นํ๋ ๊ฒ์ด ํ์ํฉ๋๋ค.
Muscovites์ ๊ฒฝ์ฐ XNUMX์๋ถํฐ Klimentovsky Lane์ MIPT ์บ ํผ์ค์์ ์ฃผ๊ฐ ๊ต์ก ์ธ์
์ ์ด ์์ ์
๋๋ค. ์ด๋ ์๊ณ ๋ฆฌ์ฆ ํ๋ก๊ทธ๋๋ฐ์ ๊ฐ๋ฐํ๊ณ ICPC ๊ฒฐ์น์์ ์๋์ ์ด๋ฆ์ ์ฑ๊ณต์ ์ผ๋ก ๋ฐฉ์ดํ๋ ค๋ ์ฌ๋๋ค์๊ฒ ํฐ ๋์์ด ๋ ๊ฒ์
๋๋ค.
์ถ์ฒ : habr.com