HSG THPT - Nghệ An 2026
Điểm: 32
Công ty ~X~ chuyên sản xuất các sản phẩm theo dây chuyền. Các sản phẩm khi đưa lên băng chuyền để hoàn thiện các công đoạn cuối sẽ được đánh một mã hàng để dễ dàng quản lí. Mỗi sản phẩm được gán một mã số là một số tự nhiên, các số liên tiếp bắt đầu từ 1. Do chưa kịp bảo dưỡng nên có hai công đoạn trên dây chuyền này không đảm bảo. Trong đó công đoạn thứ nhất cứ tạo ra ~a~ sản phẩm lại có một sản phẩm bị lỗi, công đoạn thứ 2 cứ tạo ra ~b~ sản phẩm lại có sản phẩm bị lỗi. Vì vậy những sản phẩm có mã số chia hết cho ~a~ hoặc chia hết cho ~b~ đều bị lỗi nên hệ thống tự động loại ra các sản phẩm đó. Trong khi làm việc nhân viên trực ca muốn biết mã số ghi trên sản phẩm hoàn chỉnh đảm bảo chất lượng thứ ~N~ để theo dõi.
Hãy tìm mã số ghi trên sản phẩm hoàn thiện thứ ~N~.
Dữ liệu vào
Dòng 1: Chứa 3 số nguyên dương ~a, b, N (2 \le a, b \le 10^9, 2 \le N \le 10^{18})~.
Kết quả
Một dòng duy nhất chứa mã số của sản phẩm thứ ~N~ cần tìm.
Ví dụ
Input 1
2 5 10
Output 1
23
Các sản phẩm hoàn chỉnh có mã số lần lượt là ~1, 3, 7, 9, 11, 13, 17, 19, 21, 23, \ldots~ Vậy sản phẩm thứ 10 có mã số 23.
Ràng buộc
- Subtask 1 (60% số điểm): ~2 \le N \le 10^6~.
- Subtask 2 (40% số điểm): ~10^6 < N \le 10^{18}~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).
Điểm: 32
Một công ty vận tải là khách hàng thường xuyên của công ty kinh doanh nhiên liệu. Công ty kinh doanh nhiên liệu đã công bố giá bán nhiên liệu của ~N~ ngày sắp tới là dãy giá trị ~a_1, a_2, \ldots, a_N~. Vì là khách hàng quen nên công ty vận tải được cho chính sách ưu đãi đặc biệt như sau: Giá bán nhiên liệu ngày thứ ~i~ không lớn hơn giá bán các ngày trước đó. Như vậy nếu giá bán công bố ngày thứ ~i~ là ~a_i~ mà lớn hơn giá đã mua ở ngày thứ ~i - 1~ thì công ty vận tải sẽ được mua nhiên liệu ở ngày thứ ~i~ với giá đã mua ở ngày thứ ~i - 1~.
Để ước tính chi phí, công ty vận tải đã đưa ra ~q~ truy vấn có dạng ~L, R, x~ có nghĩa là: Trong đoạn các ngày từ ngày thứ ~L~ đến ngày thứ ~R~ có bao nhiêu ngày được mua nhiên liệu với giá ưu đãi bằng ~x~.
Dữ liệu vào
Gồm các dòng:
- Dòng 1: Chứa số nguyên ~N (1 \le N \le 2 \times 10^5)~.
- Dòng 2: Chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)~.
- Dòng 3: Chứa số nguyên ~q (1 \le q \le 2 \times 10^5)~.
- ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~L, R, x (1 \le L, R \le N)~.
Kết quả
Với mỗi truy vấn, in ra số lượng ngày tìm được trên 1 dòng.
Ví dụ
Input 1
8
12 15 10 11 9 20 8 8
3
3 7 8
5 8 12
2 5 10
Output 1
1
0
2
Dãy giá ưu đãi thực tế là 12, 12, 10, 10, 9, 9, 8, 8. Truy vấn (3, 7, 8) có đúng ngày thứ 7; truy vấn (5, 8, 12) không có ngày nào; truy vấn (2, 5, 10) có ngày thứ 3 và ngày thứ 4.
Ràng buộc
- Subtask 1 (60% số điểm): ~1 \le N, q \le 10^3~.
- Subtask 2 (40% số điểm): ~10^3 < N, q \le 2 \times 10^5~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).
Điểm: 53
Nhà Tuấn có một hàng ~N~ chậu hoa đơn sắc. Hàng ngày ngắm nhìn hàng chậu hoa, Tuấn thấy rằng nếu các chậu hoa được đặt cùng màu nằm về cùng một phía (nửa trái hoặc nửa phải) của hàng thì sẽ rất đẹp.
Dãy màu các chậu hoa đã được biểu diễn thành một xâu ~S~ có độ dài chẵn ~N~ chứa các kí tự latin thường hoặc in hoa được đánh chỉ số từ 1 đến ~N~. Xâu ~S~ được gọi là xâu đẹp nếu tất cả các kí tự giống nhau của xâu ~S~ đều cùng nằm về nửa trái hoặc nửa phải của xâu. Ví dụ xâu "abcd", "AbaB" là các xâu đẹp, còn "aaaa" hay "Bbba" thì không.
Bạn phải thực hiện ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~x, y (1 \le x, y \le N)~. Đưa ra số lượng xâu ~T~ thỏa mãn: ~T~ là một hoán vị của ~S; T~ là một xâu đẹp; kí tự ~S_x~ và ~S_y~ phải nằm cùng về một phía (có thể trái hoặc phải) trong xâu ~T~.
Dữ liệu vào
Gồm các dòng:
- Dòng 1: Chứa xâu ~S~ có độ dài ~N (N \le 10^5)~.
- Dòng 2: Chứa số nguyên dương ~Q (Q \le 10^5)~.
- ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x, y (x, y \le N)~.
Kết quả
Gồm ~Q~ dòng, mỗi dòng trả lời cho mỗi truy vấn, kết quả chia lấy dư cho ~10^9 + 7~.
Ví dụ
Input 1
Abdb
2
1 3
1 2
Output 1
4
0
Với ~S =~ "Abdb" (số lượng: ~A \times 1, b \times 2, d \times 1~), có hai cách chia nửa hợp lệ: nửa trái là ~\{b\}~ hoặc nửa trái là ~\{A, d\}~. Truy vấn 1 hỏi hai kí tự ~'A'~ và ~'d' -~ cả hai cách chia đều xếp chúng cùng phía, cho 4 xâu. Truy vấn 2 hỏi ~'A'~ và ~'b' -~ không cách chia nào xếp được chúng cùng phía, cho 0.
Ràng buộc
- Subtask 1 (20% số điểm): ~Q = 1, 0 < N \le 10^3~.
- Subtask 2 (80% số điểm): ~1 < Q \le 10^3, 0 < N \le 10^5~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).