2025 · Chọn Đội tuyển Học sinh giỏi Quốc gia · Quảng Trị

Nhân dịp đầu năm học, để gắn kết các bạn trong lớp với nhau, bạn Dũng Bí thư chi đoàn, tổ chức trò chơi tập thể như sau: có ~M~ câu hỏi đố vui, mỗi câu có hai phương án trả lời YES/NO. Mỗi học sinh tham gia phải đưa ra các phương án trả lời tương ứng với ~M~ câu hỏi và mỗi câu hỏi tương ứng với một điểm.

Với câu hỏi thứ ~i~ hai học sinh ~A, B~ trả lời cùng YES hoặc cùng NO thì điểm chênh lệnh hai bạn là không thay đổi, trong trường hợp ngược lại thì chỉ có một người được điểm. Nếu hai học sinh ~A, B~ có số câu trả lời khác nhau là số chẵn thì có thể trường hợp hai bạn học sinh bằng điểm nhau, nếu là lẻ thì có điểm chênh lệch giữa hai bạn học sinh.

Yêu cầu: Với ~N~ học sinh tham gia trò chơi có ~M~ câu hỏi, hãy tính số cặp học sinh có điểm số chênh lệch nhau.

Input

Vào từ file văn bản LUCKY.INP gồm:

• Dòng đầu tiên ghi hai số nguyên ~N,M~ tương ứng với số học sinh và câu hỏi;
• ~N~ dòng tiếp theo ghi ~M~ kết quả trả lời của học sinh thứ ~i~ tương ứng xâu bao gồm hai chữ cái Y(YES) và N(NO).

Output

Ghi ra file văn bản LUCKY.OUT gồm một dòng ghi số nguyên dương duy nhất là kết quả tìm được.

Scoring

• Subtask ~1~ ~(50\%)~: ~N \leq 1000, 1 \leq m \leq 20~;
• Subtask ~2~ ~(50\%)~: ~N \leq 100000, 1 \leq m \leq 20~.

Example input 1

3 2
YY
NY
YN

Example output 1

2

Note 1

• Ghép cặp ~(1, 2)~ là: số câu trả lời khác nhau là 1;
• Ghép cặp ~(1, 3)~ là: số câu trả lời khác nhau là 1;
• Ghép cặp ~(2, 3)~ là: không có chênh lệch điểm vì số câu trả lời khác nhau là chẵn; Vậy có hai cặp chênh lệch điểm: ~(1, 2)~ và ~(1, 3)~.

Example input 2

4 4
NNYY
YNNN
NYYN
YNYN

Example output 2

3

Để bảo vệ các lãnh đạo cao cấp tham gia trong lễ diễu binh và diễu hành kỷ niệm 80 năm Quốc khánh nước Cộng hòa xã hội chủ nghĩa Việt Nam, bộ phận an ninh triển khai dãy các cảm biến dọc hành lang các lãnh đạo cấp cao đang ngồi trong lúc buỗi lễ diễn ra. Mỗi cảm biến có ngưỡng cảnh báo tức là giới hạn cảnh báo trước khi phát tín hiệu không an toàn.

Để đánh giá độ an toàn của một hành lang từ cảm biến ~i~ đến cảm biến ~j~ (~1 \leq i \leq j \leq n~) trung tâm sử dụng công thức:

$$Risk(i, j) = a_i + a_j + \min(a_i, a_{i+1}, \dots, a_j)$$

Trong đó:

• ~a_i~: ngưỡng của cảm biến đầu đoạn.
• ~a_j~: ngưỡng của cảm biến cuối đoạn.
• ~min(a_i,a_{i+1},...,a_j)~: ngưỡng nhỏ nhất trong đoạn, điểm có giới hạn cảnh báo thấp nhất trong đoạn.

Một đoạn hành lang từ vị trí ~i~ đến vị trí ~j~ được coi là an toàn nếu ~Risk(i, j) \leq k~. Ngược lại, nếu vượt quá ~k~ thì đoạn hàng lang đó sẽ không an toàn.

Yêu cầu: Cho ~n~ cảm biến được đặt dọc hành lang theo thứ tự từ ~1~ đến ~n~, tại một thời điểm cảm biến thứ ~i~ có ngưỡng cảnh báo ~a_i~. Hãy đếm số lượng đoạn ~[i, j]~ là đoạn hành lang an toàn.

Input

Vào từ file văn bản SECINT.INP:

• Dòng đầu tiên: chứa hai số nguyên dương ~n, k~
  • ~n~: số lượng cảm biến (~1 \leq n \leq 100000~);
  • ~k~: ngưỡn an toàn tối đa cho phép (~0 \leq k \leq 10^9~).
• Dòng 2: chứa ~n~ số nguyên ~a_1,a_2,...,a_n~;
  • ~a_i~: ngưỡng cảnh báo của cảm biến thứ i (~0 \leq a_i \leq 10^9~)

Lưu ý: Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra file văn bản SECINT.OUT số nguyên dương duy nhất là kết quả bài toán.

Scoring

• Subtask ~1~ ~(20\%)~: ~n \leq 5000~.
• Subtask ~2~ ~(20\%)~: ~n \leq 10^5, a_i \leq a_{i+1}, 1 \leq i \leq n~.
• Subtask ~3~ ~(20\%)~: Tồn tại vị trí ~t~ sao cho ~a_1 \leq a_2 \leq ... \leq a_t \geq a_{t+1} \geq ... \geq a_n, n \leq 10^5~.
• Subtask ~4~ ~(40\%)~: Không có giới hạn gì thêm.

Example input 1

6 5 
3 4 2 6 1 3

Example output 1

4

Note 1

• Có 4 đoạn an toàn ~[1, 5]~, ~[3, 5]~, ~[5, 5]~, ~[5,6]~.

Example input 2

6 6 
4 3 1 2 5 3

Example output 2

7

Note 2

• Có 7 đoạn an toàn ~[1, 3]~, ~[2, 3]~, ~[2, 4]~, ~[3,3]~, ~[3,4]~, ~[3,6]~, ~[4,4]~.

An rất thích làm toán, đặc biệt các bài toán số học. Có bài toán như sau: Cho dãy số nguyên ~a_1,a_2,...,a_n~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~, để tính tổng các số trong đoạn ~[i, j]~ cho trước thì ta tính ~a_i + a_{i+1} + ... + a_j~. Ví dụ cho dãy số ~2,5,-3,7,-9~ thì tổng đoạn ~[2, 4]~ là ~5 - 3 + 7 = 9~. Biết các bạn lớp 10I năm nay học toán rất tốt nên An đã mở rộng bài toán như sau:

Có ~Q~ truy vấn, mỗi truy vấn có hai loại:

• ~1~ ~x~ ~y~: gắn lại ~a_x = y~.
• ~2~ ~l~ ~r~ ~k~: tính tổng ~(a_u + a_{u+1} + ... + a_v)^k~, với tất cả ~u, v~: ~l \leq u \leq v \leq r~ và ~k = 1~ hoặc ~k = 2~.

Yêu cầu: Cho dãy số nguyên ~a_1,a_2,...,a_n~ với ~Q~ truy vấn như trên, các bạn hãy viết chương trình giải bài toán trên.

Input

Vào từ file văn bản KSUM.INP:

• Dòng đầu tiên ghi số nguyên dương ~n, Q~ (~1 \leq n,Q \leq 5*10^5~);
• Dòng tiếp theo ghi dãy số nguyên dương ~a_1,a_2,...,a_n~ (~1 \leq a_i \leq 10^6~);
• ~Q~ dòng tiếp theo mỗi dòng ghi lần lượt mỗi trong hai truy vấn sau:
  • ~1 ~ ~x ~ ~y ~: ~1 \leq x \leq n, 1 \leq y \leq 10^9~;
  • ~2 ~ ~l ~ ~r ~ ~k~ : ~1 \leq l \leq r \leq n,~ ~k = 1~ hoặc ~k = 2~.

Lưu ý: Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra file văn bản KSUM.OUT với mỗi truy vấn loại 2 (~2~ ~l~ ~r~ ~k~) in kết quả khi chia lấy dư cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(17\%)~: ~n,Q \leq 500~.
• Subtask ~2~ ~(17\%)~: ~n,Q \leq 5000~.
• Subtask ~3~ ~(21\%)~: Không có truy vấn loại 1, ~a_i = 1~.
• Subtask ~4~ ~(22\%)~: ~k = 1, n \leq 5*10^5~.
• Subtask ~5~ ~(23\%)~: Không có ràng buộc gì thêm.

Example input 1

4 4
1 2 3 4
2 1 3 1
1 2 1
2 1 3 1
2 1 3 2

Example output 1

20
16
56

Example input 2

2 4
1 2
2 1 2 2
1 1 2
2 1 2 1
2 1 2 2

Example output 2

14
8
24

Trong một buổi sinh hoạt tập thể có ~N~ bạn nam và ~N~ bạn nữ tham gia. Để thực hiện một trò chơi, mỗi bạn nam sẽ ghép với một bạn nữ thành một cặp. Các bạn nữ xếp thành một hàng ngang, bạn đầu tiên có số hiệu là ~1~, bạn thứ hai có số hiệu là ~2~, ..., bạn cuối cùng có số hiệu là ~N~. Các bạn nam cũng được gán số hiệu từ ~1~ đến ~N~. Mỗi lượt chơi tương ứng, với một cách ghép cặp là cách mỗi bạn nam tìm cho mình một bạn nữ để ghép thành một cặp.

Yêu cầu: Cho hai số nguyên không âm ~A, B~. Có bao nhiêu cách ghép cặp mà số lượng các cặp ghép có số hiệu của bạn nam trùng với số hiệu của bạn nữ nằm trong khoảng từ ~A~ đến ~B~.

Input

Vào từ file văn bản MATCH.INP: Gồm một dòng ba số nguyên ~N, A, B~ ~(1\leq N\leq 4*10^6, 0\leq A, B\leq N)~ các số cách nhau một dấu cách.

Output

Ghi ra file văn bản MATCH.OUT: Gồm một dòng ghi một số là số dư của số lượng cách ghép thỏa mãn yêu cầu khi chia cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(15\%)~: ~N\leq 10~
• Subtask ~2~ ~(15\%)~: ~N\leq 14~
• Subtask ~3~ ~(22\%)~: ~A = B = 0~
• Subtask ~4~ ~(17\%)~: ~N\leq 1000~
• Subtask ~5~ ~(20\%)~: ~N\leq 4*10^5~
• Subtask ~6~ ~(11\%)~: Không còn ràng buộc gì thêm.

Example input 1

3 0 3

Example output 1

6

Note 1

Mô tả cách ghép tương ứng với các bạn nam trên ví dụ như sau:

Với ~N=3, A=0~ và ~B=3~:

• Có hai cách ghép sao cho không có cặp nào có số hiệu trùng nhau: ~2, 3, 1; 3, 1, 2~.
• Có ba cách ghép sao cho có đúng ~1~ cặp có số hiệu trùng nhau: ~1, 3, 2; 3, 2, 1; 2, 1, 3~.
• Không có cách ghép nào sao cho có đúng ~2~ cặp có số hiệu trùng nhau, nếu có hai cặp có số hiệu trùng nhau thì cặp còn lại sẽ luôn có số hiệu trùng nhau.
• Chỉ có một cách ghép sao cho có ~3~ cặp có số hiệu trùng nhau: ~1, 2, 3~. Vậy có tất cả: ~2 + 3 + 0 + 1 = 6~ cách ghép thỏa mãn yêu cầu.

Ngôn ngữ ab là ngôn ngữ chỉ dùng hai chữ cái '~a~' và '~b~' để tạo các văn bản. Trong ngôn ngữ này người ta dùng một tập từ vựng, mỗi từ tương ứng với một xâu chỉ gồm các chữ cái '~a~' và '~b~' và quy định một số từ không thể đứng liền nhau để đọc các văn bản.

Cho một văn bản trong ngôn ngữ này tương ứng với một xâu ~S~ có độ dài ~N~ chỉ gồm các chữ cái '~a~' và '~b~', một tập gồm ~M~ từ vựng đánh số từ ~1~ đến ~M~ và ~K~ cặp từ không thể đứng liền nhau.

Một cách đọc xâu ~S~ là cách chia xâu ~S~ thành các xâu con gồm các kí tự liên tiếp sao cho mỗi xâu con tương ứng với một từ trong tập ~M~ từ vựng đã cho. Nếu trong một cách đọc có một cặp từ vi phạm tính không đứng liền nhau thì cách đọc đó là không hợp lệ.

Yêu cầu: Hãy tìm số lần xuất hiện của mỗi từ vựng trong các cách đọc hợp lệ có thể có của ~S~. Biết rằng trong một cách đọc hợp lệ, một từ có thể xuất hiện nhiều lần, tất cả các lần xuất hiện đó đều được tính trong kết quả.

Input

Vào từ file văn bản ABLANG.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(1\leq N\leq 50000, 1\leq M\leq 50, 1\leq K\leq 255)~.
• Dòng thứ hai chứa xâu ~S~ chỉ gồm các chữ cái '~a~' và '~b~'.
• ~M~ dòng tiếp theo mỗi dòng chứa một từ vựng, tương ứng như một xâu chỉ gồm các chữ cái '~a~' và '~b~'. Không có hai từ nào trùng nhau và có độ dài không vượt quá độ dài xâu ~S~.
• ~K~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~i, j~ ~(1\leq i, j\leq M)~ cách nhau dấu cách với nghĩa là từ ~i~ và từ ~j~ không được đứng liền nhau theo thứ tự ~i~ trước ~j~ sau tính từ trái sang trong xâu ~S~. Có thể có trường hợp ~i = j~.

Các số trên một dòng cách nhau một dấu cách.

Output

Ghi ra file văn bản ABLANG.OUT: Tương ứng với mỗi từ theo thứ tự từ tệp dữ liệu vào ghi ra một số là phần dư của phép chia số lần xuất hiện từ đó trong các cách đọc hợp lệ cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(20\%)~: ~K=0, S~ và các từ chỉ gồm chữ cái '~a~'.
• Subtask ~2~ ~(22\%)~: Chỉ có một cách đọc đúng và tất cả các từ có độ dài khoảng ~100~.
• Subtask ~3~ ~(13\%)~: Chỉ có một cách đọc đúng.
• Subtask ~4~ ~(10\%)~: ~K=0~ và tất cả các từ có độ dài không quá ~100~.
• Subtask ~5~ ~(13\%)~: Tất cả các từ có độ dài không quá ~100~.
• Subtask ~6~ ~(22\%)~: Không còn ràng buộc gì thêm.

Example input 1

6 3 0
aabaaa
aab
aaa
aba

Example output 1

1
1
0

Note 1

Chỉ có một cách đọc và hợp lệ: ~aab | aaa~.

Từ thứ nhất xuất hiện ~1~ lần.

Từ thứ hai xuất hiện ~1~ lần.

Từ thứ ba không xuất hiện lần nào.

Example input 2

14 5 1
baabaaababbbbb
bbbb
a
abab
baa
ba
4 3

Example output 2

2
3
2
1
3

Note 2

Có bốn cách đọc:

1. ~baa|ba|a|abab|bbbb~
2. ~baa|baa|abab|bbbb~
3. ~ba|a|baa|abab|bbbb~
4. ~ba|a|ba|a|abab|bbbb~

Các cách đọc ~2, 3~ không hợp lệ bởi hai từ ~4, 3~ đừng liền nhau.

Một khu du lịch sinh thái có ~N~ địa điểm tham quan đánh số từ ~1~ đến ~N~ và ~M~ con đường hai chiều nối giữa các địa điểm được đánh số từ ~1~ đến ~M~. Giữa hai địa điểm bất kì luôn có đường đi giữa chúng bằng một con đường trực tiếp hoặc các con đường kết nối nhau. Khu sinh thái là nơi hiểm trở nên người ta đánh giá các con đường tương ứng với một độ an toàn. Cụ thể, con đường thứ ~i~ ~(1\leq i\leq M)~ nối giữa hai địa điểm ~u_i~ và ~v_i~ có độ an toàn là ~t_i~.

Để phục vụ khách tham quan đi lại trong khu sinh thái người ta cho thuê các loại xe, mỗi loại tương ứng với một độ an toàn. Chỉ có những chiếc xe có độ an toàn lớn hơn hoặc bằng độ an toàn của con đường mới có thể đi qua đó.

Có ~Q~ khách tham quan cần thuê xe, người thứ ~i~ ~(1\leq i\leq Q)~ muốn thuê một chiếc xe có độ an toàn nhỏ nhất sao cho từ địa điểm xuất phát ~x_i~ trong khu sinh thái có thể đi đến ~k~ địa điểm tham quan khác ~x_i~.

Yêu cầu: Hãy tìm độ an toàn nhỏ nhất của chiếc xe cần thuê cho mỗi khác tham quan.

Input

Vào từ file văn bản SAFETY.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, M, Q~ ~(N, Q\leq 2*10^5, M\leq 4*10^5)~.
• ~M~ dòng đầu tiên chứa ba số nguyên ~u_i, v_i, s_i~ ~(1\leq u_i, v_i\leq N, u_i\ne v_i, 1\leq s_i\leq 10^9)~.
• Q dòng tiếp theo mỗi dòng chứa hai số nguyên ~x_i, k_i~ ~(1\leq x_i\leq N, 1\leq k_i<N)~. Các số trên một dòng cách nhau dấu cách.</li>

Output

Ghi ra file văn bản SAFETY.OUT: Tương ứng với mỗi yêu cầu của khác tham quan theo thứ tự trong tệp dữ liệu vào ghi ra một dòng gồm một số là độ an toàn nhỏ nhất của chiếc xe cần thuê của vị khách đó.

Scoring

• Subtask ~1~ ~(20\%)~: ~N, Q\leq 1000,~ ~M\leq 2000~.
• Subtask ~2~ ~(10\%)~: ~N, Q\leq 1000,~ ~M\leq 4*10^5~.
• Subtask ~3~ ~(10\%)~: ~N, Q\leq 4000,~ ~M\leq 4*10^5~.
• Subtask ~4~ ~(10\%)~: ~N, Q\leq 2*10^5, M\leq 4*10^5~ và ~k_i=1~.
• Subtask ~5~ ~(20\%)~: ~N, Q\leq 2*10^5, M\leq 4*10^5~ và ~k_i=k_j~ với mọi ~i, j~.
• Subtask ~6~ ~(30\%)~: Không còn ràng buộc gì thêm.

Example input 1

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

Example output 1

3
3

Note 1

Trong ví dụ trên:

• Với vị khách đầu tiên sẽ có thể chọn chiếc xe có độ an toàn là ~3~ và từ địa điểm ~1~ có thể đi đến 3 địa điểm ~2, 3~ và ~4~(hoặc ~5~).
• Với vị khách thứ hai sẽ có thể chọn chiếc xe có độ an toàn là 3 và từ địa điểm ~4~ có thể đi đến 4 địa điểm ~1, 2, 3, 5~.