HSG9 Đồng Hới 2024 - 2025

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Số chính phương 20 (p) 1.0s 1G
2 T-Prime 25 (p) 1.0s 1G
3 Quyên góp 25 (p) 1.0s 1G
4 Đoạn con 30 (p) 1.0s 1G

1. Số chính phương

Điểm: 20 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: SOCP.INP Output: SOCP.OUT

Cho số nguyên dương \(N(1 \leq N \leq 2.10^9)\). Hãy đếm số lượng các số chính phương từ \(1\) đến \(N\).

Dữ liệu vào

Được cho bởi tệp SOCP.INP có cấu trúc như sau:

  • Dòng \(1\): Ghi số nguyên dương \(N\).

Dữ liệu ra

Được cho bởi tệp SOCP.OUT có cấu trúc như sau:
- Dòng \(1\): Ghi 1 số nguyên duy nhất là số lượng các số chính phương từ \(1\) đến \(N\).

Sample
Input 
10
Output 
3

2. T-Prime

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: TPRIME.INP Output: TPRIME.OUT

Số T-Prime là số nguyên dương có đúng \(3\) ước số nguyên dương khác nhau. Ví dụ \(49\) là số T-Prime vì \(49\) có đúng \(3\) ước nguyên dương là \(1,7,49\).
Cho trước số nguyên dương \(N(0 < N \leq 10^9)\). Hãy đếm xem có bao nhiêu số T-Prime không vượt quá \(N\).

Dữ liệu vào

Cho file văn bản T-PRIME.INP có cấu trúc như sau:

  • Dòng thứ nhất: Ghi số nguyên \(N\).

Dữ liệu ra

Ghi ra file văn bản T-PRIME.OUT có cấu trúc như sau:
- Một số nguyên duy nhất là kết quả của bài toán.

Sample
Input 
100
Output 
4
Giải thích 
Các số 4,9,25,49 là số có 3 ước số

3. Quyên góp

Điểm: 25 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: DONATE.INP Output: DONATE.OUT

Trong buổi lễ phát động ủng hộ gia đình nạn nhân bị tai nạn giao thông có rất nhiều người tham gia. Để quản lý tốt số tiền quyên góp, ban tổ chức đề xuất phương án như sau: họ sẽ đưa các lá phiếu bỏ vào thùng kín, trên mỗi lá phiếu ghi một số tự nhiên không phải số chính phương trong đoạn từ \(1\) đến \(N\) sao cho không có hai lá phiếu nào có số trùng nhau. Từng người một sẽ bốc một lá phiếu và ủng hộ số tiền có giá trị bằng số ghi trên lá phiếu, mỗi phiếu được bốc và sử dụng một lần duy nhất.

Yêu cầu

Tính tổng số tiền quyên góp được sau khi các phiếu được bốc hết.

Dữ liệu vào

Được cho bởi tệp DONATE.INP có cấu trúc như sau:

  • Ghi một số nguyên dương \(N(1 \leq N \leq 10^9)\)

Dữ liệu ra

Được cho bởi tệp DONATE.OUT có cấu trúc như sau:
- In ra một số nguyên duy nhất là tổng tiền quyên góp được.

Sample
Input 
6
Output 
16

Ràng buộc

  • \(60\%\) số test: \(N \leq 10^6\).
  • \(40\%\) số test: không có ràng buộc gì thêm

4. Đoạn con

Điểm: 30 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: SUB.INP Output: SUB.OUT

Cho một dãy số gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n\) và hai số nguyên dương \(p,q\). Mỗi dãy \(a_i,a_{i+1},a_{i+2},...,a_j\) với \(1 \leq i \leq j \leq n\) với \(1 \leq i \leq j \leq n\) được gọi là dãy con liên tiếp của dãy đã cho.

Yêu cầu

Hãy lập tình đếm số các dãy con liên tiếp của dãy số đã cho có tổng các số lớn hơn hoặc bằng \(p\) và nhỏ hơn hoặc bằng \(q\).

Dữ liệu vào

Được cho bởi tệp SUB.INP có cấu trúc như sau:

  • Đong đầu ghi ba số nguyên \(n,p,q(1 \leq n \leq 10^5,1 \leq p < q \leq 10^{15})\)
  • Dòng thứ hai ghi \(n\) số nguyên \(a_1,a_2,...,a_n(1 \leq a_i \leq 10^7, i = 1,2,...,n)\)

Dữ liệu ra

Được cho bởi tệp SUB.OUT có cấu trúc như sau:
- Ghi một số nguyên là số các dãy con liên tiếp thỏa mãn có tổng các số lớn hơn hoặc bằng \(p\) và nhỏ hơn hoặc bằng \(q\).

Sample
Input 
10 20 30
3 2 4 2 1 2 9 12 3 7
Output 
12

Ràng buộc

  • \(50\%\) số test: \(1 \leq n \leq 10^4; 1 \leq p < q \leq 10^9\)
  • \(50\%\) số test: \(10^4 < n \leq 10^5; 10^9 < p < q \leq 10^{15}\)