2025 THT bảng B - Buổi 3

Bộ đề bài

Trở lại kỳ thi

1. Xâu vô tận (THTB Sơn Trà, Đà Nẵng 2024)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một xâu \(S\) dài vô tận được tạo ra bằng cách lặp lại xâu "SONTRA" nhiều lần.

\(S=\) SONTRASONTRASONTRASONT...

Yêu cầu: Cho trước một số nguyên dương \(n\), hãy tìm kí tự thứ \(n\) của của xâu \(S\).

Dữ liệu

Một dòng duy nhất chứa số nguyên dương \(n(n \le 10^9)\).

Kết quả

Một dòng duy nhất chứa kí tự là kết quả bài toán.

Ràng buộc

  • Có \(50\%\) số test tương ứng với \(50\%\) số điểm thỏa mãn: \(n \le 10^6\).
  • Có \(50\%\) số test còn lại tương ứng với \(50\%\) số điểm thỏa mãn: \(n \le 10^9\).

Ví dụ

Test 1

Input 
7
Output 
S

2. Đài phùn nước (THTB Sơn Trà, Đà Nẵng 2024)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong Quảng trường 2/9 có một đài phun nước được thiết kế rất đặc biệt. Đài phun có bốn vòi phun được bố trí tại bốn đỉnh của một hình vuông. Lịch phun nước của các vòi được điều khiển bằng một chương trình tự động. Tại thời điểm bắt đầu, các vòi sẽ bắt đầu phun, vòi thứ \(i\) sẽ phun nước trong thời gian \(T_i\ (i=1 \rightarrow 4)\) phút và ngưng phun \(x\) phút. Các vòi phun lặp lại theo quy trình trên. Thời điểm đẹp nhất là lúc cả 4 vòi cùng bắt đầu phun. Minh đến Quảng trường tại thời điểm \(S\) thì sau bao nhiêu phút nữa sẽ gặp thời điểm đẹp nhất của đài phun nước.

Yêu cầu: Cho \(T_1,T_2,T_3,T_4,x\) và \(S\), hãy tính thời gian chờ ít nhất của bạn Minh để gặp thời điểm đẹp nhất.

Dữ liệu: Nhập từ bàn phím

  • Dòng thứ nhất chứa 4 số nguyên dương \(T_1,T_2,T_3,T_4\)
  • Dòng thứ hai chứa số hai nguyên dương \(x,S (x \le 10000; S≤10^{16})\).

Kết quả: Ghi ra màn hình

  • Thời gian chờ ít nhất

Ràng buộc:

  • 60% tests tương ứng 60% số điểm có \(T_1,T_2,T_3,T_4≤100\)
  • 40% tests tương ứng 40% số điểm có \(T_1,T_2,T_3,T_4≤10000\)

Ví dụ

Test 1

Input 
2 3 1 2
1 6
Output 
6

3. Cà phê muối (THTB Sơn Trà, Đà Nẵng 2024)

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Khôi là một sinh viên nghèo, anh ấy muốn mở một cửa hàng cà phê muối để kiếm thêm thu nhập. Trước ngày khai trương, anh ấy khảo sát \(N\) khách hàng về giá tiền của một ly cà phê muối. Vị khách thứ \(i\) sẽ đến khai trương quán, mua một ly nếu giá tiền không quá \(A_i\) đồng. Nếu giá tiền một ly vượt quá \(A_i\) đồng, khách hàng thứ \(i\) sẽ không đến. Dựa trên khảo sát, anh ấy muốn xác định giá tiền cho một ly cà phê muối sao cho doanh thu từ \(N\) khách hàng trên là lớn nhất. Ngoài mục tiêu doanh thu ngày khai trương, anh ấy cũng mong muốn giá tiền cho ly cà phê muối là nhỏ nhất có thể. Vì đang rất bận cho buổi khai trương ngày mai, anh ấy muốn nhờ bạn tìm giá tiền phù hợp.

Yêu cầu: Hãy tìm giá tiền cho một ly cà phê muối sao cho doanh thu ngày khai trương là lớn nhất. Nếu có nhiều giá tiền cho ra doanh thu lớn nhất, chọn giá tiền nhỏ nhất.

Dữ liệu

  • Dòng đầu chứa số nguyên dương \(n (n \le 10^7)\).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2, \dots, A_n (A_i \le 10^6)\).

Các số trên cùng một dòng cách nhau bởi chính xác một dấu cách.

Kết quả

Ghi ra doanh thu lớn nhất của ngày khai trương và giá tiền của một ly cà phê muối. Hai số được in ra cách nhau bởi chính xác một dấu cách.

Ràng buộc

  • Có \(20\%\) số test tương ứng với \(20\%\) số điểm thỏa mãn: \(A_i \le 1000\).
  • Có \(40\%\) số test khác tương ứng với \(40\%\) số điểm thỏa mãn: \(n \le 5000\).
  • Có \(20\%\) số test khác tương ứng với \(20\%\) số điểm thỏa mãn: \(n \le 10^6\).

Ví dụ

Test 1

Input 
5
50 25 10 50 25
Output 
100 25

4. Cạnh góc vuông (THTB Sơn Trà, Đà Nẵng 2024)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một tam giác vuông, bình phương của cạnh huyền bằng tổng các bình phương của hai cạnh góc vuông. Hãy tìm số lượng tam giác vuông có các cạnh là các số nguyên dương và một trong hai cạnh góc vuông có độ dài là \(n\). Số lượng tam giác này có thể tính bằng số lượng cặp nguyên dương \((x, y)\) sao cho \(n^2 + x^2 =y^2\).

Yêu cầu: Cho trước một số nguyên dương \(n\), hãy tìm số lượng cặp số \((x, y)\) thõa mãn điều kiện.

Dữ liệu

Một dòng duy nhất, chứa một số nguyên dương \(n (n \le 10^{12})\).

Kết quả

Một dòng duy nhất, chứa số lượng tam giác thỏa mãn bài toán.

Ràng buộc

  • Có \(20\%\) số test tương ứng với \(20\%\) số điểm thỏa mãn: \(n \le 5000\).
  • Có \(40\%\) số test khác tương ứng với \(40\%\) số điểm thỏa mãn: \(n \le 10^6\).
  • Có \(40\%\) số test còn lại tương ứng với \(40\%\) số điểm thỏa mãn: \(n \le 10^{12}\).

Ví dụ

Test 1

Input 
3
Output 
1

Test 2

Input 
8
Output 
2
Note
  • Test 1: Có \(1\) cặp \((x;y)\) thỏa mãn là: \(3^2+4^2=5^2\)
  • Test 2: Có \(2\) cặp \((x;y)\) thỏa mãn là: \(8^2+6^2=10^2; 8^2+15^2=17^2\)

5. CSES - Sum of Divisors | Tổng các ước

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Gọi \(\sigma(n)\) là tổng các ước của một số nguyên \(n\). Ví dụ, \(\sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28\).

Nhiệm vụ của bạn là tính tổng \(\sum_{i=1}^n \sigma(i)\) modulo \(10^9 + 7\).

Input

  • Một dòng duy nhất chứa số nguyên \(n\).

Output

  • In ra \(\sum_{i=1}^n \sigma(i)\) modulo \(10^9 + 7\).

Constraints

  • \(1 \le n \le 10^{12}\)

Example

Sample input

5

Sample output
21