Chia sẻ Giải Pháp: HRBUST 1132 Số Nước

HowieHz
2024-09-02
Di sản Kiến thức > Mật mã Thi Đấu > Hồ sơ Bài Tập

Mô tả bài toán - Nhấn vào đây để mở rộng.

Mô tả

Nguyên soái nhận được rất ít phản hồi tích cực, hóa ra là do mọi người đều không thích làm những bài toán dễ (“nước”). Nhưng thật bất ngờ, chính Nguyên soái lại là “Vua bài nước”, đã từng giải hơn 300 bài toán dễ trước và sau đó. Giờ đây, Nguyên soái muốn kiểm tra trình độ “nước” của mọi người bằng cách đưa ra một bài toán dễ mới.

Nếu một số nguyên dương m được biểu diễn ở dạng nhị phân có n chữ số (không tính các số 0 đứng đầu), thì nó được gọi là một số nhị phân n. Tổng số lượng chữ số 1 trong tất cả các số nhị phân n được gọi là “số nước” tương ứng với n. Ví dụ, có tổng cộng 4 số nhị phân 3 là 4 (100), 5 (101), 6 (110), 7 (111). Tổng số lượng chữ số 1 trong chúng là 1 + 2 + 2 + 3 = 8, vậy số nước tương ứng với 3 là 8.

Đầu vào

Cho bạn một số nguyên T, đại diện cho số lượng bộ dữ liệu đầu vào. Tiếp theo là T dòng, mỗi dòng chứa một số nguyên dương n (1 ≤ n ≤ 25).

Đầu ra

Đối với mỗi giá trị n, xuất ra số nước tương ứng trên một dòng.

Ví dụ Đầu vào

Ví dụ Đầu ra

Ý tưởng

Dưới đây là bảng minh họa sự xuất hiện của chữ số 1 trong các số nhị phân:

n	Liệt kê số nhị phân	Số lần xuất hiện của 1 tại mỗi cột từ cao nhất đến thấp nhất
1	1 0	1
2	10 11	2 + 1
3	100 101 110 111	4 + 2 + 2
4	1000 … 1111	8 + 4 + 4 + 4

Từ bảng trên, ta thấy rằng khi n = x, số nước tương ứng với n sẽ là:

1

(x-1)**2 + ((x-2)**2)*(x-1) # Mã nguồn Python

Thực thi

Dưới đây là đoạn mã C++ để giải bài toán này:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include <iostream>  
#include <math.h>  
#include <iomanip>  
using namespace std;  

int main()  
{  
  int lines;  
  cin >> lines;  
  while (lines--)  
  {  
    int n;  
    cin >> n;  
    cout << fixed << setprecision(0) << (pow(2, (n - 1)) + pow(2, (n - 2)) * (n - 1)) << endl;  
  }  
  return 0;  
}  

Lưu ý

Nếu không thêm << fixed << setprecision(0), kết quả đầu ra sẽ hiển thị dưới dạng khoa học, ví dụ khi n=26, giá trị sẽ hiển thị là 2.18104e+08 thay vì dạng số tự nhiên.

Bài viết đề xuất

2024-11-06 Hrbust ACM Practice Tuần 9 - Đề bài và giải pháp chia sẻ (A-B)
2024-09-24 Hrbust ACM Programming Practice 20240922 - Giải pháp chia sẻ
2024-09-24 Hrbust ACM Practice Tuần 5 - Đề bài và giải pháp chia sẻ (A-C,F-H)

Bài trước: Hrbust ACM Practice Tuần 1-2 - Đề bài và giải pháp chia sẻ
Bài sau: Ba kỹ năng thiết yếu dành cho lập trình viên mới

Trang chủ
Lưu trữ
Nhật ký
Liên kết hữu ích
Giới thiệu về tôi
Tìm kiếm

Menu ;)
Mục lục ;)
Chia sẻ ;)

Số lượt truy cập: 33,108
Số bài đăng: 90

Trang chủ
Lưu trữ
Nhật ký
Liên kết hữu ích
Giới thiệu về tôi

cskh thabet - Mô tả Bài Toán

link i9bet nhận 100k