E D R , A S I H C RSS
ZeroWiki

The Priest Mathematician

์›๋ฌธ๋ณด๊ธฐ
----
์ธ๊ธฐ๋„:C(A,B,C), ์„ฑ๊ณต๋ฅ :๋†’์Œ(๋‚ฎ์Œ,๋ณดํ†ต,๋†’์Œ), ๋ ˆ๋ฒจ:2(1~4)

About ThePriestMathematician

"ํ•˜๋…ธ์ด์˜ ํƒ‘(Tower of Hanoi)" ํผ์ฆ์— ๊ด€ํ•œ ๊ณ ๋Œ€ ์‹ ํ™”๋Š” ์ด๋ฏธ ์ž˜ ์•Œ๋ ค์ ธ ์žˆ๋‹ค. ์ตœ๊ทผ ๋ฐํ˜€์ง„ ์ „์„ค์— ์˜ํ•˜๋ฉด, ๋ธŒ๋ผํ๋งˆ๋‚˜ ์ˆ˜๋„์‚ฌ๋“ค์ด 64๊ฐœ์˜ ์›๋ฐ˜์„ ํ•œ ์ชฝ ์นจ์—์„œ ๋‹ค๋ฅธ ์ชฝ ์นจ์œผ๋กœ ์˜ฎ๊ธฐ๋Š” ๋ฐ ์–ผ๋งˆ๋‚˜ ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋Š”์ง€๋ฅผ ์•Œ์•„๋‚ด๊ณ  ๋‚˜์„œ๋Š” ๋” ๋น ๋ฅด๊ฒŒ ์˜ฎ๊ธฐ๋Š” ๋ฐฉ๋ฒ•์„ ์ฐพ์•„๋‚ด์ž๋Š” ๊ฒฐ๋ก ์„ ๋‚ด๋ ธ๋‹ค. ๋‹ค์Œ ๊ทธ๋ฆผ์€ ์นจ์ด ๋„ค ๊ฐœ์ธ ํ•˜๋…ธ์ด์˜ ํƒ‘์ด๋‹ค.
http://online-judge.uva.es/p/v102/p10254b.jpg
์‚ฌ์›์— ์žˆ๋Š” ์ˆ˜๋„์‚ฌ ์ค‘ ํ•œ ๋ช…์ด ๋™๋ฃŒ ์ˆ˜๋„์‚ฌ์—๊ฒŒ ์นจ์„ ํ•˜๋‚˜๋งŒ ์ถ”๊ฐ€ํ•˜๋ฉด 1์ดˆ์— ์›๋ฐ˜์„ ํ•˜๋‚˜์”ฉ ์˜ฎ๊ธด๋‹ค๊ณ  ํ•  ๋•Œ ํ•œ ๋‚˜์ ˆ์ด๋ฉด ๋ชจ๋“  ์›๋ฐ˜์„ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋ผ๊ณ  ์•Œ๋ ค์ฃผ์—ˆ๋‹ค. ๊ทธ๊ฐ€ ์ œ์•ˆํ•œ ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.
{{|
1. ๋งจ ์œ„์— ์žˆ๋Š” ์›๋ฐ˜(๋งจ ์œ„์— ์žˆ๋Š” k๊ฐœ์˜ ์›๋ฐ˜)์„ ๋‹ค๋ฅธ ์นจ์œผ๋กœ ์˜ฎ๊ธด๋‹ค.
2. ์นจ์ด ์„ธ ๊ฐœ ์žˆ๋Š” ๊ฒฝ์šฐ์— ์“ฐ๋Š” ๋ฐฉ๋ฒ•์„ ๊ทธ๋Œ€๋กœ ์ ์šฉํ•ด์„œ ๋‚˜๋จธ์ง€ n-k๊ฐœ์˜ ์›๋ฐ˜(์ „์ฒด ์›๋ฐ˜์˜ ๊ฐœ์ˆ˜๋ฅผ n๊ฐœ๋ผ๊ณ  ๊ฐ€์ •)์„ ๋ชฉํ‘œ ์ง€์ ์œผ๋กœ ์˜ฎ๊ธด๋‹ค.
3. ๋งˆ์ง€๋ง‰์œผ๋กœ ๋„ค ๊ฐœ์˜ ์นจ์„ ์ด์šฉํ•ด์„œ ๋งจ ์œ„์— ์žˆ๋˜ k๊ฐœ์˜ ์›๋ฐ˜์„ ์ตœ์ข… ๋ชฉ์ ์ง€๋กœ ์˜ฎ๊ธด๋‹ค.
|}}
์ด๋™ ํšŸ์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•  ์ˆ˜ ์žˆ๋Š” k๊ฐ’์„ ๊ณ„์‚ฐํ•œ ๋‹ค์Œ 18,433๋ฒˆ๋งŒ ์˜ฎ๊ธฐ๋ฉด ๋œ๋‹ค๋Š” ๊ฒฐ๋ก ์„ ๋‚ด๋ ธ๋‹ค. ๋”ฐ๋ผ์„œ ์นจ์ด ์„ธ ๊ฐœ๋งŒ ์žˆ์„ ๋•Œ๋Š” 5์ฒœ์–ต๋…„์ด ๊ฑธ๋ฆด ์ผ์„ ์นจ ํ•˜๋‚˜๋งŒ ์ถ”๊ฐ€ํ•˜๋ฉด 5์‹œ๊ฐ„ 7๋ถ„ 13์ดˆ๋งŒ์— ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ์•„๋ƒˆ๋‹ค.

๊ทธ ์˜๋ฆฌํ•œ ์ˆ˜๋„์‚ฌ๊ฐ€ ์ œ์•ˆํ•œ ๋„ค ๊ฐœ์˜ ์นจ์„ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ์›๋ฐ˜์„ ์˜ฎ๊ธฐ๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜์ž. ์›๋ฐ˜์€ ํ•œ ๋ฒˆ์— ํ•˜๋‚˜์”ฉ๋งŒ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์œผ๋ฉฐ ํฐ ์›๋ฐ˜์„ ์ž‘์€ ์›๋ฐ˜ ์œ„์— ๋†“์„ ์ˆ˜๋Š” ์—†๋‹ค. ์ด๋™ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ ค๋ฉด ๋จผ์ € ์›๋ฐ˜ ์ด๋™ ํšŸ์ˆ˜๋ฅผ ์ตœ์†Œํ™”์‹œํ‚ฌ ์ˆ˜ ์žˆ๋Š” k๊ฐ’์„ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค.

Input

์ž…๋ ฅ ํŒŒ์ผ์€ ์—ฌ๋Ÿฌ ์ค„๋กœ ๊ตฌ์„ฑ๋œ๋‹ค. ๊ฐ ์ค„์—๋Š” 0 ์ด์ƒ 10,000 ์ดํ•˜์˜ ์ •์ˆ˜ N์ด ๋“ค์–ด์žˆ์œผ๋ฉฐ, ์ด ๊ฐ’์€ ์˜ฎ๊ฒจ์•ผ ํ•  ์›๋ฐ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ํŒŒ์ผ ๋ ๋ฌธ์ž๊ฐ€ ๋“ค์–ด์˜ค๋ฉด ์ž…๋ ฅ์ด ์ข…๋ฃŒ๋œ๋‹ค.

Output

์ž…๋ ฅ๋œ ๊ฐ ์ค„์— ๋Œ€ํ•ด N๊ฐœ์˜ ์›๋ฐ˜์„ ์ตœ์ข… ์œ„์น˜๋กœ ์˜ฎ๊ธฐ๋Š” ๋ฐ ํ•„์š”ํ•œ ์ด๋™ ํšŸ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

Sample Input

{{| 1
2
28
64 |}}

Sample Output

{{| 1
3
769
18433 |}}

ํ’€์ด

์ž‘์„ฑ์ž ์‚ฌ์šฉ์–ธ์–ด ๊ฐœ๋ฐœ์‹œ๊ฐ„ ์ฝ”๋“œ
๊น€์ƒ์„ญ C++ . ThePriestMathematician/๊น€์ƒ์„ญ
๋ฌธ๋ณด์ฐฝ C++ 1์ฐจ(์‹คํŒจ), 2์ฐจ(5์‹œ๊ฐ„) ThePriestMathematician/๋ฌธ๋ณด์ฐฝ
ํ•˜๊ธฐ์›… C++ 2์‹œ๊ฐ„ 30๋ถ„ ThePriestMathematician/ํ•˜๊ธฐ์›…

์“ฐ๋ ˆ๋“œ

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:13
Processing time 0.0154 sec