1048 : Find the Distance
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
ถ้ามีเลขฐานสอง 2 จำนวนซึ่งมีจำนวนหลักเท่ากันแล้ว Hamming distance ของเลขสองจำนวนนี้ หาได้จาก จำนวนหลักที่มีเลขต่างกัน ตัวอย่างเช่น

010010
และ
100010

มี Hamming distance เป็น 2 เนื่องจากหลักทางซ้ายสุด 2 หลักแรกแตกต่างกัน อีกตัวอย่างหนึ่งคือ

0111110
และ
0011100

ก็จะมี Hamming distance เป็น 2 เช่นกัน

ถ้าพิจารณาเลขฐานสองที่มี K หลัก และกำหนดให้ N เป็นเลขจำนวนเต็มโดยที่ N <= 2k-1 แล้ว หน้าที่ของคุณคือ ให้หาผลรวมของ Hamming distance ของค่า 0 และ 1, 1 และ 2, เรื่อยไปจนถึงระหว่าง N-1 และ N

ตัวอย่างเช่น ถ้า K=3 และ N=4 แล้วคำตอบคือ 7 ซึ่งได้มาจากการหา Hamming distance ระหว่าง 000 และ 001 (หรือจาก 0 และ 1 เมื่อเขียนเป็นเลขฐานสอง) มี Hamming distance เป็น 1, 001 และ 010 มี Hamming distance เป็น 2, 010 และ 011 มี Hamming distance เป็น 1, และ 011 และ 100 มี Hamming distance เป็น 3 ดังนั้นผลรวมของ Hamming distance คือ 1+2+1+3 เป็น 7 นั่นเอง

ในโจทย์ข้อนี้ คุณจะได้รับค่า K และ N หน้าที่ของคุณคือต้องหาผลรวมของ Hamming distance ของเลขฐานสอง K หลัก ระหว่างค่า 0 และ 1, 1 และ 2, ..., N-1 และ N

ข้อมูลนำเข้า
บรรทัดเดียวที่มีจำนวนเต็มสองจำนวน คือ ค่าของ K และ N

ข้อมูลส่งออก
บรรทัดเดียวที่แสดงค่าผลรวมของ Hamming distance ดังได้อธิบายไปแล้ว

ข้อจำกัดของชุดทดสอบ
 K ≤ 32 and N ≤ 232-1

ที่มา: Indian National Olympiad in Informatics
Online Programming Contest, 24-25 December 2005


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 4
7

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 16 ผู้เยี่ยมชมและ 5 สมาชิก (2 บอท)