MARBLE - A Marble Game

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 Di 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.


Được gửi lên bởi:Jimmy
Ngày:2009-07-17
Thời gian chạy:0.600s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon 2009
Round 2
Problem Setter: Khúc Anh Tuấn

hide comments
2020-03-23 17:32:19
không hiểu sao nộp toàn 0 điểm
2018-01-17 10:31:15
không hiểu sao để N*4 ko đc. cho lên N*8 lại được
2017-11-20 14:57:33


Last edit: 2017-11-20 14:58:04
2017-09-29 06:24:13
sao toàn ok không thế

2016-09-06 10:50:14
Liên hệ lấy code nè https://facebook.com/profile.php=75816879

Last edit: 2016-12-08 13:37:06
2016-09-06 10:49:46
Đừng dùng IT./.
2015-11-11 16:27:08 Prismatic
ai thắc mắc Di nhiu thì cứ để int64 :)) ban đầu bấn loạn tưởng Bigint
2015-06-25 18:57:29 The Flash
KHÔNG DÙNG CÂY IT , 60 ĐIỂM
2013-11-04 18:25:53 up!
Toan 0.ok :((
2012-10-15 03:27:06 Scammers
uc che, nop bai toan 0k
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.