คอมพิวเตอร์อะตอม (acm15_atom)


Time limit:
1000 ms
Memory limit:
256 MB

การประมวลผลการคำนวณทางคณิตศาสตร์จะไม่ใช่เรื่องยากอีกต่อไป เพราะวันนี้ศาสตราจารย์ดอกเตอร์ท่านหนึ่งคิดคอมพิวเตอร์อะตอมที่ทำงานเร็วกว่าคอมพิวเตอร์ทั่วไปถึง 8,000,000,000 (แปดพันล้าน) เท่าได้สำเร็จแล้ว

คอมพิวเตอร์อะตอมเครื่องนี้เก็บข้อมูลในหน่วยความจำพิเศษราคาแพงหลายแสนบาท วิธีการเก็บข้อมูลก็เก็บเป็นเลขฐานสองเหมือนเครื่องคอมพิวเตอร์ทั่วไป แต่จะมีลักษณะประหลาดอย่างหนึ่งที่แตกต่างออกไปคือ ในแต่ละบิตของหน่วยความจำ สามารถเก็บสถานะได้ถึง 3 สถานะด้วยกัน ซึ่งแสดงค่าได้เป็น -1, 0 และ 1 ตามลำดับ ศาสตราจารย์ดอกเตอร์ท่านนี้ได้นำคุณสมบัติสุดแสนจะมหัศจรรย์ดังกล่าวไปใช้ทำประโยชน์แก่มวลมนุษยชาติมากมาย คุณในฐานะนิสิตชั้นปีสุดท้าย จึงสนใจจะทำโปรเจคจบกับศาสตราจารย์ดอกเตอร์ท่านนี้เป็นอย่างมาก

ศาสตราจารย์ดอกเตอร์ได้แนะนำวิธีการใช้งานคอมพิวเตอร์อะตอมเบื้องต้นให้กับคุณ และคุณก็ได้ลองสั่งให้คอมพิวเตอร์อะตอมเก็บค่าจำนวนเต็มเข้าไปในหน่วยความจำ คุณลองสั่งให้เก็บค่า 1 และพบว่าบางทีมันก็เก็บค่าเป็น (1)2 หรือบางทีมันก็เก็บค่าเป็น (1)(-1)2 ตอนนี้คุณก็เริ่มไม่แน่ใจว่ามันจะเก็บเป็นรูปแบบอื่นได้อีกไหม

จงเขียนโปรแกรมรับค่าจำนวนเต็มที่คุณต้องการจะเก็บเข้าหน่วยความจำ และจำนวนบิตในหน่วยความจำของคอมพิวเตอร์อะตอม แล้วคำนวณหาว่าจำนวนเต็มที่รับมานั้น จะสามารถเก็บในหน่วยความจำของคอมพิวเตอร์อะตอมได้ทั้งหมดกี่แบบ

Input

บรรทัดแรกประกอบด้วยจำนวนเต็มบวก t แทนจำนวนชุดข้อมูลทดสอบทั้งหมด (1 ≤ t ≤ 100) จากนั้นตามด้วยข้อมูลอีก t บรรทัด ซึ่งในบรรทัดที่ i+1 จะประกอบด้วยจำนวนเต็ม xi แทนค่าจำนวนเต็มที่จะเก็บในหน่วยความจำและจำนวนเต็ม yi แทนจำนวนบิตของหน่วยความจำของคอมพิวเตอร์อะตอม (-2,000,000,000 ≤ xi ≤ 2,000,000,000 และ 1 ≤ yi ≤ 20)

Output

มีจำนวน t บรรทัด โดยบรรทัดที่ i จะแสดงจำนวนวิธีการเก็บจำนวนเต็ม xi ลงในหน่วยความจำของคอมพิวเตอร์อะตอมที่มี yi บิต

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None