About HanoiTowerTroublesAgain! ¶
ํ๋
ธ์ด์ ํ ๋ฌธ์ ๋ฅผ ๋ณํ์ํจ ๋ฌธ์ ๋ค ์ค์๋ ํฅ๋ฏธ๋ก์ด ๋ฌธ์ ๋ค์ด ๋ง์ด ์๋ค. ์ด ๋ฌธ์ ๋ N๊ฐ์ ๊ธฐ๋ฅ๊ณผ 1๋ถํฐ ๋ฌดํ๋๊น์ง์ ์ ์๊ฐ ์ ํ์๋ ๊ณต์ ๊ดํ ๋ฌธ์ ๋ค. ๋ ๊ณต์ ์ ํ ๋ฒํธ์ ํฉ์ด ์์ ์ ๊ณฑ์(์ด๋ค ์ ์๋ฅผ ์ ๊ณฑํ ์)๊ฐ ์๋๋ฉด ๊ทธ ๋ ๊ณต ์ฌ์ด์๋ ์๋ก ๋ง๋ฟ์์์ ์ ์์ ๋งํผ ํฐ ์ฒ๋ ฅ์ด ์์ฉํ๊ฒ ๋๋ค.
http://online-judge.uva.es/p/v102/p10276.jpg
๊ณต์ ํ ๋ฒ์ ํ๋์ฉ, ๋ฒํธ๊ฐ ์ปค์ง๋ ์์๋ก ๊ธฐ๋ฅ์ ๋ผ์ฐ๋ ๊ฒ์์ ํ๋ค(์ฆ 1๋ฒ์ ๋ผ์ฐ๊ณ ๋์ 2๋ฒ์ ๋ผ์ฐ๊ณ , ๊ทธ๋ฆฌ๊ณ ๋์ 3๋ฒ์ ๋ผ์ฐ๊ณ ํ๋ ์์ผ๋ก ๊ณต์ ๊ธฐ๋ฅ์ ๋ผ์). ๋ ์ด์ ์๋ก ๋ฐ์ด๋ด์ง ์๋๋ก ๊ณต์ ๋ผ์ธ ์ ์๊ฒ ๋๋ฉด ๊ฒ์์ด ๋๋๋ค. ๊ฒ์์ ๋ชฉํ๋ ์ต๋ํ ๋ง์ ๊ฐ์์ ๊ณต์ ๋ผ์ฐ๋ ๊ฒ์ด๋ค. ์์ ์๋ ๊ทธ๋ฆผ์๋ ๊ธฐ๋ฅ์ด ๋ค ๊ฐ์ธ ๊ฒฝ์ฐ์ ์ต๋ํ ๋ง์ ๊ณต์ ๋ผ์ด ๊ฒฐ๊ณผ๊ฐ ๋์ ์๋ค.
http://online-judge.uva.es/p/v102/p10276.jpg
๊ณต์ ํ ๋ฒ์ ํ๋์ฉ, ๋ฒํธ๊ฐ ์ปค์ง๋ ์์๋ก ๊ธฐ๋ฅ์ ๋ผ์ฐ๋ ๊ฒ์์ ํ๋ค(์ฆ 1๋ฒ์ ๋ผ์ฐ๊ณ ๋์ 2๋ฒ์ ๋ผ์ฐ๊ณ , ๊ทธ๋ฆฌ๊ณ ๋์ 3๋ฒ์ ๋ผ์ฐ๊ณ ํ๋ ์์ผ๋ก ๊ณต์ ๊ธฐ๋ฅ์ ๋ผ์). ๋ ์ด์ ์๋ก ๋ฐ์ด๋ด์ง ์๋๋ก ๊ณต์ ๋ผ์ธ ์ ์๊ฒ ๋๋ฉด ๊ฒ์์ด ๋๋๋ค. ๊ฒ์์ ๋ชฉํ๋ ์ต๋ํ ๋ง์ ๊ฐ์์ ๊ณต์ ๋ผ์ฐ๋ ๊ฒ์ด๋ค. ์์ ์๋ ๊ทธ๋ฆผ์๋ ๊ธฐ๋ฅ์ด ๋ค ๊ฐ์ธ ๊ฒฝ์ฐ์ ์ต๋ํ ๋ง์ ๊ณต์ ๋ผ์ด ๊ฒฐ๊ณผ๊ฐ ๋์ ์๋ค.
Input ¶
์ฒซ๋ฒ์งธ ์ค์๋ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ T(1โคTโค50)๊ฐ ์
๋ ฅ๋๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ง๋ค ์ธ ์ ์๋ ๊ธฐ๋ฅ์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ N(1โคNโค50)์ด ์
๋ ฅ๋๋ค.
Output ¶
๊ฐ ํ
์คํธ ์ผ์ด์ค์ ๋ํด ๊ธฐ๋ฅ์ ๋ผ์ธ ์ ์๋ ๊ณต์ ์ต๋ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์๋ฅผ ์ถ๋ ฅํ๋ค. ๋ผ์ธ์ ์๋ ๊ณต์ ๊ฐ์๊ฐ ๋ฌดํ๋๋ฉด '-1'์ ์ถ๋ ฅํ๋ค.
Sample Input ¶
{{| 2
4
25 |}}
4
25 |}}
Sample Output ¶
{{| 11
337 |}}
337 |}}
ํ์ด ¶
| ์์ฑ์ | ์ฌ์ฉ์ธ์ด | ๊ฐ๋ฐ์๊ฐ | ์ฝ๋ |
| ๋ฌธ๋ณด์ฐฝ | C++ | 10๋ถ | HanoiTowerTroublesAgain!/๋ฌธ๋ณด์ฐฝ |
| ํฉ์ฌ์ | Java | 50๋ถ | HanoiTowerTroublesAgain!/ํฉ์ฌ์ |
| ํ๊ธฐ์ | C++ | ์๋ 1์๊ฐ, ๋ฌธ๋ณด์ฐฝ XXX ๋๋ฌธ์ ๋ง๋ ธ์ใ กใ ก; | HanoiTowerTroublesAgain!/ํ๊ธฐ์ |
| ์ด๋ํ | C++ | Closed Form ๊ตฌํ๋ ๋ฐ(1์๊ฐ 30๋ถ), ์ฝ๋ฉ 5๋ถ | HanoiTowerTroublesAgain!/์ด๋ํ |
| ์กฐํํ | C++ | ? | HanoiTowerTroublesAgain!/์กฐํํ |
