E D R , A S I H C RSS
ZeroWiki

Complete Tree Labeling

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

About CompleteTreeLabeling

Inputstandard input
Outputstandard output
Time Limit45 seconds
Memory Limit32 MB

๋ชจ๋“  ์žŽ(leaf)์˜ ๊นŠ์ด๊ฐ€ ๊ฐ™๊ณ  ๋ชจ๋“  ๋‚ด๋ถ€ ๋…ธ๋“œ์˜ ์ฐจ์ˆ˜(degree)๊ฐ€ k์ธ(์ฆ‰ ๋ถ„๊ธฐ๊ณ„์ˆ˜(branching factor)๊ฐ€ k์ธ) ํŠธ๋ฆฌ๋ฅผ k์ง„ ์™„์ „ ํŠธ๋ฆฌ(complete k-ary tree)๋ผ๊ณ  ํ•œ๋‹ค. ๊ทธ๋Ÿฐ ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ๋Š” ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์‰ฝ๊ฒŒ ๊ฒฐ์ •ํ•  ์ˆ˜ ์žˆ๋‹ค.
k์ง„ ์™„์ „ ํŠธ๋ฆฌ์˜ ๊นŠ์ด์™€ ๋ถ„๊ธฐ๊ณ„์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ผ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ฒฐ์ •ํ•ด์•ผ ํ•œ๋‹ค. ์ด๋•Œ ๊ฐ ๋…ธ๋“œ์˜ ๋ ˆ์ด๋ธ”์€ ๊ทธ ์ž์†์˜ ๋ ˆ์ด๋ธ”๋ณด๋‹ค ์ž‘์•„์•ผ ํ•œ๋‹ค. ์ด์ง„ ํž™ ์šฐ์„  ์ˆœ์œ„ ํ ์ž๋ฃŒ ๊ตฌ์กฐ๊ฐ€ ๋ฐ”๋กœ ์ด๋Ÿฐ ์†์„ฑ์„ ๊ฐ€์ง„๋‹ค(์ด์ง„ ํŠธ๋ฆฌ์ด๋ฏ€๋กœ k=2). N๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ๋Š” ํŠธ๋ฆฌ์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ผ ๋•Œ, 1์—์„œ N๊นŒ์ง€์˜ ๋ ˆ์ด๋ธ”์„ ๋ถ™์ผ ์ˆ˜ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž.

Input

์ž…๋ ฅ ํŒŒ์ผ์€ ์—ฌ๋Ÿฌ ์ค„๋กœ ๊ตฌ์„ฑ๋œ๋‹ค. ๊ฐ ์ค„์—๋Š” ๋‘ ๊ฐœ์˜ ์ •์ˆ˜ k์™€ d๊ฐ€ ๋“ค์–ด์žˆ๋‹ค. k>0์ด๋ฉฐ, ์ด ๊ฐ’์€ k์ง„ ์™„์ „ ํŠธ๋ฆฌ์˜ ๋ถ„๊ธฐ๊ณ„์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. d>0๋ฉฐ, k์ง„ ์™„์ „ ํŠธ๋ฆฌ์˜ ๊นŠ์ด๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. k X d โ‰ค21์ธ ๋ชจ๋“  k์™€ d์— ๋Œ€ํ•ด ์ž‘๋™ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค.

Output

์ž…๋ ฅ๋œ ๊ฐ ์ค„์— ๋Œ€ํ•ด ํ•œ ์ค„์˜ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๊ทธ ์ค„์—๋Š” ์œ„์—์„œ ์„ค๋ช…ํ•œ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œํ‚ค๋ฉด์„œ k์ง„ ํŠธ๋ฆฌ์— ๋ ˆ์ด๋ธ”์„ ๋ถ™์ด๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

Sample Input 

~cpp 
2 2
10 1

Sample Output 

~cpp 
80
3628800

ํ’€์ด

์ž‘์„ฑ์ž ์‚ฌ์šฉ์–ธ์–ด ๊ฐœ๋ฐœ์‹œ๊ฐ„ ์ฝ”๋“œ
์กฐํ˜„ํƒœ C . CompleteTreeLabeling/์กฐํ˜„ํƒœ
ํ•˜๊ธฐ์›… C++ 1์‹œ๊ฐ„ 30๋ถ„ CompleteTreeLabeling/ํ•˜๊ธฐ์›…

์“ฐ๋ ˆ๋“œ

์œผ์•„ ๋„ˆ๋ฌด์–ด๋ ค์›Œ ใ… ใ… 

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:58
Processing time 0.0348 sec