[TASK] [TRANSLATION] COCI#4 2006-2007

 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Translated by SmiLe-DoG
COCI#4 2006-2007
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

4.ZBRKA | 64 MB | 1 sec
    กำหนดให้ลำดับของจำนวนเต็ม N จำนวนประกอบด้วยจำนวนเต็มในช่วง 1 ถึง N โดยแต่ละจำนวนปรากฏแค่เพียงครั้งเดียวเท่านั้นในลำดับนั้น ( เช่น N=6 : ลำดับคือ 4 3 2 6 1 5 เป็นต้น )
    เรากำหนดคู่อันดับที่สับสน คือ คู่อันดับที่ตัวเลขที่อยู่ก่อนหน้าในลำดับนั้นมีค่ามากกว่าตัวเลขที่อยู่หลัง เช่น ถ้าเรามีลำดับ N=4 : ลำดับคือ (1,4,3,2) เราจะได้ว่าคู่อันดับที่สับสนในลำดับนี้มี 3 คู่อันดับคือ (4,3), (4,2) และ (3,2)
    ให้เขียนโปรแกรมเพื่อหาจำนวนของลำดับ N ตัวทั้งหมดที่ทำให้จำนวนคู่อันดับที่สับสนในลำดับ N ตัวนั้น มีจำนวนเท่ากับ C คู่อันดับ

Input
มีบรรทัดเดียวเท่านั้นประกอบด้วยจำนวนเต็มสองจำนวนคือ N (1<=N<=1000) และ C (0<=C<=10000)

Output
แสดงจำนวนของลำดับทั้งหมดที่สอดคล้องกับเงื่อนไขข้างต้นโดยมอดูโลจำนวนนั้นด้วย 1 000 000 007

Sample of input

input 10 1 output 9

input 4 3 output 6

input 9 13 output 17957

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

5. JOGURT | 32 MB | 1 sec
    ต้นไม้ทวิภาคเต็มต้น (Complete Binary Tree) ประกอบด้วยโหนดรากหนึ่งโหนดซึ่งเรากำหนดว่าอยู่ที่ระดับ 0 และมีโหนดลูกต่ออกมาจากโหนดราก 2 โหนดซึ่งอยู่ในระดับที่ 1 โหนดลูกแต่ละโหนดก็ยังมีลูกอีก 2 โหนดในระดับที่ 2 และเป็นเช่นนี้ไปเรื่อยๆ
    ตามปกติแล้วต้นไม้ทวิภาคแบบเต็มต้นที่มี N ระดับจะประกอบด้วย 2^N-1 โหนด โดยแต่ละโหนดจะมีโหนดลูกอยู่ 2 โหนดยกเว้นโหนดที่อยู่ในระดับที่ N-1
    เราสามารถใส่ตัวเลข 1 ถึง 2^N-1 เข้าไปในต้นไม้ทวิภาคแบบเต็มต้น N ระดับนั้นโดยที่ไม่มีโหนดในมีตัวเลขที่ซ้ำกับโหนดอื่นๆ แล้วมีเงื่อนไขว่าสำหรับแต่ละโหนดที่ระดับ D ค่าผลต่างระหว่างผลรวมของตัวเลขในโหนดลูกด้านซ้ายในและผลรวมของตัวเลขในโหนดลูกด้านขวาในระดับนั้นเท่ากับ 2^D
    ตัวอย่างเช่นโหนดรากต้องมีผลต่างของตัวเลขในโหนดลูกด้านซ้ายและตัวเลขในโหนดลูกด้านขวาเท่ากับ 1 และผลต่างของผลรวมของตัวเลขในโหนดด้านซ้ายและผลรวมของตัวเลขในโหนดด้านขวาของโหนดในระดับที่ 1 ต้องเท่ากับ 2
    ให้เขียนโปรแกรมเพื่อสร้างต้นไม้ทวิภาคตามเงื่อนไขข้างต้น ตัวเลขแต่ละตัวต้องถูกใช้เพียงครั้งเดียวเท่านั้น และผลเฉลยอาจมีได้หลายรูปแบบ

Input
มีบรรทัดเดียวเท่านั้นประกอบด้วยจำนวนเต็ม N (1<=N<=15) ซึ่งบอกจำนวนระดับของต้นไม้ทวิภาคนั้น

Output
แสดงผลจำนวน 2^N-1 ตัวแยกกันด้วยช่องว่างในบรรทัดเดียว โดยจะเป็นตัวเลขที่เก็บในแต่ละโหนดของทรีในลำดับของการท่องแบบ Preorder Traversal (โหนดราก โหนดลูกด้านซ้าย และโหนดลูกด้านขวาตามลำดับ)

Sample of input

input 2 output 3 1 2

input 3 output 3 1 7 5 6 2 4

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>