Olympic Truyền thống 30/4 2023 - Tin học - Khối 10

Xét một bàn cờ vua có kích thước \(m \times n\) gồm có \(m\) dòng, \(n\) cột. Các dòng được đánh số từ 1 đến \(m\), các cột được đánh số từ 1 đến \(n\). Một ô nằm trên dòng \(x\), cột \(y\) được kí hiệu là \((x, y)\).

Một quân mã xuất phát từ một ô trên bàn cờ có thể đi đến một trong bốn ô như hình vẽ.

Ngoài ra, trên bàn cờ có \(k\) ô mà quân mã không được phép đi vào. Những ô này được gọi là ô bị cấm.

Yêu cầu: Tìm số cách di chuyển của quân mã từ ô \((x, y)\) cho trước đến ô \((m, n)\).

Input

• Dòng đầu tiên ghi \(4\) số nguyên \(m, n, k\) và \(Q\ (1<m,n≤1000;0≤k<10; Q≤10)\);
• Trên \(k\) dòng tiếp theo, mỗi dòng ghi \(2\) số nguyên \(k_{x_i}, k_{y_i}\) cho biết ô \((k_{x_i}, k_{y_i})\) bị cấm (\(1 <k_x;<m; 1 < k_y; <n\));
• Trên \(Q\) dòng tiếp theo, mỗi dòng ghi \(2\) số nguyên \(X_i, Y_i\ (1 ≤x_i<m;1≤y_i<n)\).

Output

• Gồm \(Q\) số nguyên \(W_i\), mỗi số trên một dòng cho biết số cách di chuyển quân mã từ ô \((X_i, Y_i)\) cho trước đến ô \((m,n)\). Trong đó \(W_i\) là phần dư của phép chia số cách quân mã di chuyển từ ô \((X_i, Y_i)\) cho trước đến ô \((m, n)\) cho \(10^9\).

Scoring

• \(30\%\) test ứng với \(30\%\) số điểm của bài có \(1 <m, n≤100 ; k=0; Q≤10^2\);
• \(20\%\) test ứng với \(20\%\) số điểm của bài có \(1 <m, n≤100;0<k≤10; Q≤10^2\);
• \(50\%\) test ứng với \(50\%\) số điểm của bài có ràng buộc như đề bài.

Example

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

0
1
0

4 5 0 2
1 2
3 3

2 
1

Tâm rất yêu thích lập trình tạo phần mềm. Vào dịp rảnh rỗi Tâm đã thiết kế một phần mềm đơn giản. Màn hình phần mềm gồm \(N\) địa điểm (đánh số từ 1 đến \(N\)), trong đó mỗi địa điểm có đặt một bóng đèn ở trạng thái sáng hoặc tắt. Có \(N-1\) con đường một chiều nối trực tiếp giữa các cặp địa điểm. Mỗi lần Tâm chạm tay vào một địa điểm \(X_i\) bất kì trên màn hình thì sẽ có một robot xuất phát từ địa điểm \(X_i\) di chuyển theo các con đường một chiều, cuối cùng kết thúc ở địa điểm 1. Robot không thay đổi trạng thái đèn ở địa điểm \(X_i\) và địa điểm 1, các địa điểm còn lại robot đã đi qua thì đèn ở địa điểm đó sẽ thay đổi sang trạng thái ngược lại (sáng thành tắt, tắt thành sáng).

Yêu cầu: Hãy cho biết khi Tâm thực hiện \(K\) lần chạm tay (mỗi lần chạm tay vào một địa điểm) thì sau đó sẽ có tất cả bao nhiêu địa điểm có đèn sáng. Biết rằng robot xuất phát từ địa điểm bất kì luôn có thể di chuyển theo các con đường một chiều đến địa điểm 1.

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(K\) lần lượt là số địa điểm, số lần chạm tay \((1 \le N, K ≤ 100000)\);
• Dòng thứ hai gồm \(N\) số nguyên cho biết trạng thái đèn ở \(N\) địa điểm, lần lượt theo thứ tự từ địa điểm 1 đến địa điểm \(N\). Trạng thái đèn tắt là 0, sáng là 1.
• Dòng thứ \(i\) trong \(N-1\) dòng tiếp theo gồm hai số nguyên dương \(A_n\) và \(B_i\) \((1 \le A_i, B_i \le N)\) cho biết có con đường một chiều nối trực tiếp từ địa điểm \(A_i\) đến \(B_i\);
• Dòng cuối cùng gồm \(K\) số nguyên dương, trong đó số nguyên thứ \(i\) là \(X_i\) \((1 \le X\le N)\) cho biết địa điểm thứ \(i\) mà Tâm thực hiện chạm tay.

Output

• Ghi số nguyên duy nhất là kết quả cần tìm.

Scoring

• \(50\%\) test ứng với \(50\%\) số điểm của bài có \(1 \le N,K≤5000\);
• \(50\%\) test ứng với \(50\%\) số điểm của bài có ràng buộc như đề bài.

Example

5 3 
1 0 0 0 0 
2 1 
4 2 
3 2 
5 4 
4 5 4 

3

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

2 

Chứng khoán là một trong những kênh đầu tư nhiểu rủi ro. Nhà đầu tư cần phân tích nhiều yếu tố thị trường để quyết định đầu tư vào một cổ phiếu. Một trong những tham số được nhiều nhà đầu tư quan tâm là tính ổn định giá của một cổ phiếu. Xét giá bán của một cổ phiếu trong nhiều phiên giao dịch. Cổ phiếu được xem là có giá ổn định trong một khoảng thời gian nếu khoảng chênh lệch của giá bán cao nhất và giá bán thấp nhất của cổ phiếu đó trong khoảng thời gian trên không vượt quá ngưỡng ổn định giá \(T\) cho trước.

Yêu cầu: Cho biết giá bán một cổ phiếu trong \(N\) phiên giao dịch. Hãy viết chương trình tính số phiên giao dịch dài nhất mà cổ phiếu đó có giá ổn định.

Input

• Dòng đầu chứa hai số nguyên \(T\ (0≤T≤2 \times 10^9)\) và \(N\) lần lượt cho biết ngưỡng ổn định giá và số phiên giao dịch.
• Dòng thứ hai chứa \(N\) số nguyên \(G_i\ (0 \le G_i≤ 2\times 10^9))\) lần lượt cho biết giá bán của cổ phiếu trong N phiên giao dịch.

Output

• Ghi ra một số nguyên là số phiên giao dịch dài nhất mà cổ phiếu có giá ổn định. .

Scoring

• \(30\%\) test ứng với \(30\%\) số điểm của bài có \(1 <N\le 10 000\);
• \(20\%\) test ứng với \(20\%\) số điểm của bài có \(10 000<N\le 500 000\);
• \(50\%\) test ứng với \(50\%\) số điểm của bài có \(500 000<N\le3 000 000\);

Example

5 10 
5 7 9 20 15 13 20 12 11 1 

3