trang chủ / đề bài / icpc23_mb_b

Robot lau nhà

Đề bài

Mô tả

Người ta dự định dùng một robot để lau dọn một mặt phẳng tọa độ. Robot có dạng hình vuông kích thước k×k, các cạnh song song với các trục tọa độ. Ban đầu, góc dưới bên trái của robot nằm ở điểm (0;0), góc trên bên phải nằm ở điểm (k;k).

Robot thực hiện lần lượt n lần di chuyển. Lần di chuyển thứ i được mô tả bởi hướng di chuyển di và số nguyên ai là quãng đường robot đi được. Hướng di chuyển nhận một trong các giá trị:

  • 'N': lên trên (tọa độ Y tăng);
  • 'S': xuống dưới (tọa độ Y giảm);
  • 'W': sang trái (tọa độ X giảm);
  • 'E': sang phải (tọa độ X tăng).

Tại mọi thời điểm, robot lau sạch toàn bộ phần mặt phẳng nằm dưới nó. Nói cách khác, một điểm được coi là sạch khi và chỉ khi nó thuộc hình vuông k×k mà robot chiếm tại một thời điểm nào đó. Dựa vào các lần di chuyển của robot, hãy tính tổng diện tích phần mặt phẳng đã được lau sạch.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên: kích thước robot k và số lần di chuyển n (1≤k≤104; 1≤n≤105).

Dòng thứ i trong n dòng tiếp theo chứa hướng di chuyển di và quãng đường ai (di là một trong các chữ cái 'N', 'S', 'W', 'E'; 1≤ai≤109).

Dữ liệu ra

In ra tổng diện tích phần mặt phẳng đã được robot lau sạch.

Ràng buộc

  • 1≤k≤104
  • 1≤n≤105
  • di∈{'N', 'S', 'W', 'E'}
  • 1≤ai≤109

Ví dụ

Input Output Giải thích
1 5
E 2
N 2
W 4
S 4
E 4
17 Robot 1×1 quét các dải [0,3]×[0,1], [2,3]×[0,3], [−2,3]×[2,3], [−2,−1]×[−2,3] và [−2,3]×[−2,−1]. Các dải có diện tích 3,3,5,5,5; mỗi dải sau chung với dải trước đúng một ô 1×1, nên tổng diện tích là 21−4=17.
3 4
W 2
N 1
W 1
N 2
27 Lần đi đầu lau [−2,3]×[0,3] (diện tích 15); ba lần sau lau thêm lần lượt 3, 3 và 6 đơn vị diện tích.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0