TLEOJ Contest #14 - Stupidly Large
Xem PDFHình như đâu đấy có một khái niệm về một hội chứng “sợ từ ngữ dài”. Gọi là \text{hippopotomonstrosesquippedaliophobia}, đúng không nhỉ (lmao).
Và đây là một bài toán đặc biệt được viết ra dành cho những người mắc hội chứng này, vì kết quả của bài toán có thể lớn khủng khiếp, rất phù hợp.
Cho một số N và một số n (0 \le n \le 63; 0 \le N \le 2^{63} - 1). Tìm số nguyên X nhỏ nhất không nhỏ hơn N sao cho X có đúng n bit 1. Nếu không tồn tại số X thỏa mãn, in ra -1.
Kết quả được đảm bảo rằng trên trục số thực, X nằm trên đoạn số từ 0 đến +\infty và chỉ là một số nguyên.
\text{Input} XXXXL.inp
- Mỗi test bao gồm nhiều testcases. Dòng đầu gồm một số T (1 \le T \le 10^4), thể hiện số lượng testcases. Dưới đây là dữ liệu của T testcases, mỗi testcase có cấu trúc được trình bày như dưới đây.
- Dòng đầu của mỗi testcase có hai số n (0 \le n \le 63) và N (0 \le N \le 2^{63} - 1).
\text{Output} XXXXL.out
- Đối với mỗi testcase, in ra một giá trị là đáp án nhỏ nhất của X thỏa mãn X \ge N và trong biểu diễn nhị phân của X có đúng n bit 1.
- Nếu không tồn tại số X nào, in ra -1.
\text{Scoring}
- Subtask \text{#}1 (20\% số điểm): N có số lượng bit 1 không quá n.
- Subtask \text{#}2 (50\% số điểm): 1 \le n \le 30, 1 \le N \le 10^9.
- Subtask \text{#}3 (30\% số điểm): Không có điều kiện gì thêm.
\text{Examples}
\text{Test #}1
\text{Input}
2
5 12
1 6
\text{Output}
31
8
\text{Explanations}
Ở testcase \text{#}1, ta có biểu diễn nhị phân của số 31 là 11111_2, có 5 bit 1.
Ở testcase \text{#}2, ta có biểu diễn nhị phân của số 8 là 1000_2, có 1 bit 1.
Bình luận