BOI 2011 - Ngày 1

Egon chăm sóc một khu vườn có \(N\) cây táo. Công việc của anh gồm hai loại: bón phân cho cây và thống kê chiều cao của chúng.

Để bón phân, Egon có một số chai MegaBoostFertilizer. Khi được bón loại phân này, một cây lập tức cao thêm một xentimét. Mỗi chai có dung lượng \(c_i\), là số cây có thể được bón bằng chai đó, và chỉ dùng được cho những cây cao ít nhất \(h_i\) xentimét. Vì muốn tất cả cây đều cao nhất có thể, Egon luôn bón cho \(c_i\) cây thấp nhất trong số những cây cao ít nhất \(h_i\) xentimét.

Khi thống kê, Egon cần biết số cây có chiều cao nằm trong một khoảng cho trước. Anh rất bận chăm sóc khu vườn, nên nhờ bạn viết chương trình nhận danh sách công việc và tính các kết quả thống kê giúp anh.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số cây trong vườn và số công việc. Dòng thứ hai chứa \(N\) số nguyên thuộc đoạn \([1,N]\), mô tả chiều cao ban đầu của các cây, tính bằng xentimét.

\(M\) dòng tiếp theo mô tả các công việc theo thứ tự thời gian. Mỗi dòng bắt đầu bằng ký tự \(t_i\), là F hoặc C:

• Nếu \(t_i\) là F, tiếp theo là hai số nguyên \(c_i\) và \(h_i\). Egon bón phân cho \(c_i\) cây thấp nhất trong số những cây cao ít nhất \(h_i\) xentimét. Nếu có ít hơn \(c_i\) cây đủ cao, anh bón cho tất cả những cây đó rồi bỏ chai đi, dù vẫn còn phân trong chai.
• Nếu \(t_i\) là C, tiếp theo là hai số nguyên \(\mathit{min}_i\) và \(\mathit{max}_i\). Egon cần đếm số cây có chiều cao \(H\) thỏa mãn \(\mathit{min}_i \le H \le \mathit{max}_i\).

Dữ liệu ra

Với mỗi công việc loại C, in một dòng chứa số cây táo có chiều cao thuộc khoảng yêu cầu. Thứ tự các kết quả phải trùng với thứ tự những công việc loại C trong dữ liệu vào.

Ràng buộc

• \(1 \le N,M \le 100\,000\).
• \(1 \le c_i \le N\) và \(0 \le h_i \le 1\,000\,000\,000\).
• \(1 \le \mathit{min}_i \le \mathit{max}_i \le 1\,000\,000\,000\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 40 điểm, \(1 \le N \le 7\,000\) và số công việc loại F không vượt quá \(7\,000\).
• 60 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

3
0
5

Rasmus và các bạn đang đi nghỉ ở Ý. Vì trời nóng, họ quyết định mua kem. Cửa hàng có \(N\) vị kem, được đánh số từ \(1\) đến \(N\). Tuy nhiên, một số cặp vị không nên kết hợp với nhau vì sẽ có vị khó chịu. Rasmus muốn biết có bao nhiêu cách chọn ba vị kem khác nhau sao cho không có cặp nào bị cấm. Thứ tự các vị được chọn không quan trọng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên không âm \(N\) và \(M\), lần lượt là số vị kem và số cặp vị bị cấm kết hợp.

Mỗi dòng trong \(M\) dòng tiếp theo chứa số hiệu của hai vị kem khác nhau, mô tả một cặp bị cấm. Không có cặp bị cấm nào xuất hiện hai lần.

Dữ liệu ra

In một số nguyên duy nhất: số cách chọn thỏa mãn yêu cầu.

Ràng buộc

• \(1 \le N \le 200\).
• \(0 \le M \le 10\,000\).

Ví dụ

5 3
1 2
3 4
1 3

3

Casper đang thiết kế một mạch điện trên một tấm bảng hình chữ nhật gồm \(N\) hàng và \(M\) cột ô vuông. Mỗi ô chứa một miếng vuông có dây dẫn nối hai góc đối diện của nó.

Nguồn điện được nối với góc trên bên trái của bảng, còn bóng đèn được nối với góc dưới bên phải. Đèn chỉ sáng khi có một đường đi gồm các dây dẫn nối nguồn điện với bóng đèn. Để làm đèn sáng, có thể xoay một số miếng vuông, mỗi miếng \(90^\circ\) theo một trong hai chiều.

Hãy viết chương trình tìm số miếng vuông ít nhất cần xoay để làm đèn sáng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), là kích thước của bảng.

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) ký tự \ hoặc /, biểu diễn hướng của dây dẫn nối hai góc đối diện trên miếng vuông tương ứng.

Dữ liệu ra

In đúng một dòng. Nếu có thể làm đèn sáng, in một số nguyên duy nhất: số miếng vuông ít nhất cần xoay. Nếu không thể, in chuỗi NO SOLUTION.

Ràng buộc

• \(1 \le N,M \le 500\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 40 điểm, \(1 \le N \le 4\) và \(1 \le M \le 5\).
• 60 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

3 5
\\/\\
\\///
/\\\\

1

Bạn có một bản đồ kho báu được chia thành lưới \(N\times M\). Mỗi ô là biển hoặc một phần của đảo. Bản đồ còn đánh dấu kho báu và một chiếc thuyền Viking của địch chiếm một ô biển. Để tiện theo dõi, bạn cũng đã đánh dấu vị trí của mình.

Bạn cần định trước một lộ trình cố định để lấy kho báu. Lộ trình bắt đầu tại vị trí của bạn, kết thúc tại kho báu và gồm một dãy bước đi. Mỗi bước, bạn chỉ được đi sang một ô kề cạnh theo chiều ngang hoặc chiều dọc không thuộc đảo. Nhưng hãy cẩn thận: thuyền Viking có thể đuổi theo bạn bằng những bước đi cùng loại! Sau mỗi bước đi của bạn theo lộ trình, thuyền Viking có thể đi một bước hoặc đứng yên. Bước đi của bạn và phản ứng của thuyền Viking tạo thành một lượt.

Sau mỗi lượt, lần lượt kiểm tra:

1. Nếu bạn và thuyền Viking nằm trên cùng một đường ngang hoặc đường dọc, và giữa hai bên chỉ có biển, bạn sẽ bị giết.
2. Nếu bạn chưa bị giết và đang ở ô kho báu, bạn lấy được kho báu.

Hãy xác định liệu có thể định trước một lộ trình cố định giúp bạn lấy được kho báu mà không bị giết, bất kể thuyền Viking di chuyển như thế nào hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), là kích thước của bản đồ.

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) ký tự. Mỗi ký tự mô tả một ô: . là biển, I là một phần của đảo, V là thuyền Viking, Y là vị trí của bạn, và T là kho báu. Mỗi ký tự V, Y và T xuất hiện đúng một lần.

Dữ liệu ra

In YES nếu có thể định trước một lộ trình để lấy được kho báu theo yêu cầu; ngược lại, in NO.

Ràng buộc

• \(1 \le N,M \le 700\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 50 điểm, \(1 \le N,M \le 200\).
• 50 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

5 7
Y.....V
..I....
..IIIII
.......
...T...

YES

5 7
Y....V.
..I....
..IIIII
.......
...T...

NO

2 3
.YT
VII

NO