Độ khó: Dễ (1/4 điểm)

Một trí tuệ nhân tạo cần kết nối với một máy chủ từ xa để đồng bộ hóa dữ liệu. Máy chủ này hoạt động theo một chu kỳ cố định để bảo trì và tối ưu hiệu năng:

• ~X~ giây ở trạng thái "Online" (cho phép kết nối);
• Sau đó, ~S~ giây ở trạng thái "Offline" (từ chối mọi kết nối).

Chu kỳ này lặp lại liên tục và bắt đầu từ giây thứ ~1~ với trạng thái "Online".

Yêu cầu: Một trí tuệ nhân tạo gửi yêu cầu kết nối đến máy chủ vào giây thứ ~T~. Hãy kiểm tra tại giây thứ ~T~, máy chủ đang ở trạng thái "Online" hay "Offline"?

Dữ liệu vào từ tệp văn bản TTNT.INP:

• Dòng đầu tiên gồm số nguyên dương ~X~ ~(1 \le X \le 10^9)~;
• Dòng thứ hai gồm số nguyên dương ~S~ ~(1 \le S \le 10^9)~;
• Dòng thứ ba gồm số nguyên dương ~T~ ~(1 \le T \le 10^9)~.

Kết quả ghi ra tệp văn bản TTNT.OUT:

• Nếu tại giây thứ ~T~ máy chủ đang "Offline" ghi ra số ~0~, máy chủ đang "Online" ghi ra số ~1~.

Ràng buộc:

• Có ~80\%~ số test ứng với ~80\%~ số điểm có ~T \le 10^6~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

5
7
5

Sample Output 1

1

Sample Input 2

5
7
20

Sample Output 2

0

Độ khó: Trung bình (2/4 điểm)

Nhân dịp Tết Trung thu, khu phố đã treo ~N~ chiếc đèn lồng có màu vàng và màu đỏ, từ trái sang phải. Một dãy đèn lồng liên tiếp được gọi là "đẹp" nếu số lượng đèn màu vàng gấp đôi số lượng đèn màu đỏ.

Yêu cầu: Cho một xâu ~S~ chỉ gồm các ký tự 'V' và 'D' mô tả dãy đèn lồng, ký tự 'V' mô tả đèn lồng màu vàng và ký tự 'D' mô tả đèn lồng màu đỏ. Hãy tìm độ dài của dãy đèn lồng "đẹp" dài nhất.

Dữ liệu vào từ tệp văn bản DL.INP:

• Một xâu ~S~ chỉ gồm các ký tự 'V' và 'D' mô tả dãy đèn có độ dài không vượt quá ~10^5~.

Kết quả ghi ra tệp văn bản DL.OUT:

• Một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc:

• Có ~60\%~ số test ứng với ~60\%~ số điểm có độ dài xâu ~S~ không vượt quá ~100~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có độ dài xâu ~S~ không vượt quá ~1000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

VDVVDDVVD

Sample Output

6

Giải thích: Dãy đèn lồng "đẹp" dài nhất được in đậm: VDVVDDVVD.

Độ khó: Khá (3/4 điểm)

Trong một khu rừng có ~N~ cây. Các cây được đánh số từ ~1~ đến ~N~, có tất cả ~M~ loại cây.

Cây thứ ~i~ thuộc loại ~B_i~ ~(1 \le B_i \le M)~ và có chiều cao là ~C_i~.

Chênh lệch chiều cao của rừng cây được tính theo công thức: tổng các giá trị tuyệt đối của hiệu chiều cao giữa tất cả các cặp cây khác loại nhau. Nghĩa là chênh lệch chiều cao của rừng cây được tính bằng công thức:

$$\sum |C_i - C_j| \quad \forall\, 1 \le i < j \le N \text{ và } B_i \ne B_j.$$

Yêu cầu: Hãy tính chênh lệch chiều cao của rừng cây đã cho.

Dữ liệu vào từ tệp văn bản RC.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ ~(1 \le N \le 10^5; M \le N)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~B_i~ ~(1 \le B_i \le M)~;
• Dòng thứ ba gồm ~N~ số nguyên dương ~C_i~ ~(1 \le C_i \le 10^9)~.

Kết quả ghi ra tệp văn bản RC.OUT:

• Một số nguyên duy nhất là chênh lệch chiều cao của rừng cây đã cho.

Ràng buộc:

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~1 \le N \le 1000; 1 \le C_i \le 200~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~1 \le N \le 10^5; M = 2~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

5 3
1 2 3 2 1
3 4 5 6 7

Sample Output

14

Giải thích: Chênh lệch chiều cao của rừng cây là:

~|C_1 - C_2| + |C_1 - C_3| + |C_1 - C_4| + |C_2 - C_3| + |C_2 - C_5| + |C_3 - C_4| + |C_3 - C_5| + |C_4 - C_5|~

~= |3 - 4| + |3 - 5| + |3 - 6| + |4 - 5| + |4 - 7| + |5 - 6| + |5 - 7| + |6 - 7|~

~= 1 + 2 + 3 + 1 + 3 + 1 + 2 + 1 = 14~

Độ khó: Khá (3/4 điểm)

Với hai số nguyên dương ~X, Y~ cho trước, dãy F-Fibonacci là dãy số được định nghĩa như sau:

• ~F_0 = X; F_1 = Y~;
• ~F_i = F_{i-1} + F_{i-2}~ với mọi ~i \ge 2~.

Cho dãy ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_N~. Người ta muốn chia dãy ~A~ thành các đoạn con liên tiếp sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Yêu cầu: Hãy đếm số cách chia dãy ~A~ thành các đoạn con sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Dữ liệu vào từ tệp văn bản DF.INP:

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_N~ ~(1 \le A_i \le 10^9; 1 \le i \le N)~;
• Dòng thứ ba gồm hai số nguyên dương ~X, Y~ ~(1 \le X \le Y \le 100)~.

Kết quả ghi ra tệp văn bản DF.OUT:

• Một số nguyên duy nhất là kết quả bài toán sau khi chia dư cho ~10^9 + 7~.

Ràng buộc:

• Có ~40\%~ số test ứng với ~40\%~ số điểm có ~1 \le N \le 20; 1 \le A_i \le 10^5~ ~(1 \le i \le N)~;
• ~40\%~ số test khác ứng với ~40\%~ số điểm có ~1 \le N \le 1000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

6
1 3 2 2 1 4
1 1

Sample Output

4

Giải thích: Có ~4~ cách chia dãy số thỏa mãn như sau:

• ~\{1\}, \{3\}, \{2\}, \{2\}, \{1, 4\}~;
• ~\{1\}, \{3\ 2\}, \{2\}, \{1, 4\}~;
• ~\{1\ 3\ 2\ 2\}, \{1\ 4\}~;
• ~\{1\ 3\ 2\ 2\ 1\ 4\}~.

Độ khó: Khá (3/4 điểm)

Trong sứ mệnh khám phá bản đồ số, một rô-bốt tự hành được giao một nhiệm vụ di chuyển dọc theo một dãy gồm ~N~ điểm thu thập thông tin, được đánh số từ ~1~ đến ~N~.

Điểm thu thập thông tin ~i~ ~(1 \le i \le N)~ có lượng dữ liệu là ~A_i~, nếu rô-bốt thu thập thông tin tại điểm này thì sẽ tiêu thụ ~W_i~ năng lượng.

Rô-bốt được lập trình để quét các điểm thông tin liên tiếp và phải tuân thủ nghiêm ngặt các điều kiện sau:

• Số lượng điểm thu thập thông tin được quét phải là bội số của ~K~ (để đảm bảo tính toàn vẹn của các gói thông tin);
• Tổng năng lượng tiêu thụ để rô-bốt thu thập thông tin không được vượt quá giới hạn ~S~ của pin. Coi năng lượng tiêu thụ khi di chuyển qua các điểm thông tin bằng ~0~.

Yêu cầu: Hãy viết chương trình lập trình cho rô-bốt để tìm ra các điểm thông tin liên tiếp thỏa mãn điều kiện trên mà tổng lượng dữ liệu thu thập được là lớn nhất.

Dữ liệu vào từ tệp văn bản TT.INP:

• Dòng đầu tiên gồm ba số nguyên ~N, K, S~ ~(1 \le K \le N \le 10^5; 1 \le S \le 10^{12})~;
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ ~(|A_i| \le 10^9; 1 \le i \le N)~;
• Dòng thứ ba gồm ~N~ số nguyên ~W_1, W_2, \ldots, W_N~ ~(0 \le W_i \le 10^9; 1 \le i \le N)~.

Kết quả ghi ra tệp văn bản TT.OUT:

• Gồm một số nguyên là lượng dữ liệu thu thập được lớn nhất. Nếu không tồn tại các điểm thông tin liên tiếp nào khả thi, ghi ra số ~0~.

Ràng buộc:

• Có ~25\%~ số test ứng với ~25\%~ số điểm thoả mãn: ~N \le 100~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm thoả mãn: ~W_i = 0~ ~(1 \le i \le N)~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm thoả mãn: ~K = 1~;
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

5 2 6
3 -1 2 5 -2
2 1 2 2 1

Sample Output 1

7

Giải thích: Chọn hai điểm thông tin liên tiếp là: ~3~ và ~4~ (có số lượng điểm thu thập thông tin là ~2~, chia hết cho ~K~); tổng năng lượng tiêu thụ: ~2 + 2 = 4 < 6~; tổng lượng dữ liệu thu thập được: ~2 + 5 = 7~.

Sample Input 2

3 2 5
10 20 5
1 1 1

Sample Output 2

30

Giải thích: Chọn hai điểm thông tin liên tiếp là: ~1~ và ~2~ (có số lượng điểm thu thập thông tin là ~2~, chia hết cho ~K~); tổng năng lượng tiêu thụ: ~1 + 1 = 2 < 5~; tổng lượng dữ liệu thu thập được: ~10 + 20 = 30~.