MARBLE - A Marble Game

Giới hạn
  • Thời gian: 2.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Bắn bi

Trong những ngày hè rảnh rỗi, ktuan thường chơi bắn bi trên một bảng hình vuông gồm NxN ô vuông nhỏ. Trò chơi được thực hiện như sau:

  • Ban đầu, ktuan đặt K vật cản vào K ô vuông của bảng.
  • Sau đó, ktuan thực hiện lần lượt Q lượt chơi. Ở lượt chơi thứ i, ktuan lần lượt bắn D i viên bi từ ngoài bảng vào một trong 4 đường biên của bảng. Kích thước của mỗi viên bi đúng bằng kích thước của một ô vuông nhỏ. Viên bi sẽ đi qua các ô thuộc cùng một hàng / cột cho đến khi đi ra ngoài bảng hoặc gặp một vật cản hay viên bi khác. Nếu có vật cản hay viên bi khác ở ngay ô đầu tiên thì viên bi đó không được đưa vào bảng.
  • Ở mỗi lượt bắn, ktuan ghi lại tổng số ô mà các viên bi đã đi qua.

Bạn hãy viết chương trình mô phỏng lại trò chơi và với mỗi lượt bắn, in ra tổng số ô mà các viên bi của lượt bắn đó đã đi qua.

Dữ liệu

  • Dòng đầu ghi 3 số N, K, Q.
  • K dòng sau, mỗi dòng ghi một cặp số (u,v) thể hiện toạ độ (dòng, cột) của một vật cản.
  • Q dòng sau, mỗi dòng ghi 4 giá trị c, D, u, v. Ký tự c có thể là 'L', 'R', 'T', hoặc 'B' cho biết viên bi được đưa vào từ biên trái, phải, trên hoặc dưới của bảng. (u,v) thể hiện toạ độ ô đầu tiên mà viên bi được đưa vào. Đây phải là một ô nằm trên biên của bảng ứng với ký tự c. D là số lượng viên bi sẽ bắn ở lượt chơi này.

Kết quả

  • Với mỗi lượt chơi, in ra tổng số ô mà các viên bi của lượt đó đã đi qua

Ví dụ 

Dữ liệu 
5 1 3
3 3
L 2 3 1
T 1 1 1
B 5 5 5

Kết quả
3
2
25

Giải thích

  • Viên bi đầu tiên của lượt 1 sẽ đi qua 2 ô (3,1) và (3,2) trước ghi gặp vật cản ở ô (3,3)
  • Viên bi tiếp theo của lượt 1 sẽ đi qua ô (3,1) trước khi gặp viên bi ở ô (3,2). Vậy tổng số ô bị đi qua ở lượt này là 3.
  • Viên bi đầu tiên của lượt 2 sẽ đi qua 2 ô (1,1) và (2,1) trước khi gặp viên bi ở ô (3,1).
  • Mỗi viên bi của lượt cuối cùng đều không gặp vật cản và sẽ đi ra ngoài bảng sau khi đi qua 5 ô.

Giới hạn

  • N ≤ 50000, K ≤ 10, Q ≤ 100000
  • Trong 1/3 số test, N và Q không vượt quá 1000.

  • Người up: paulmcvn
  • Nguồn bài: VNOI Marathon 2009Round 2Problem Setter: Khúc Anh Tuấn