trang chủ / đề bài / icpc26_nat_h

Robot dọn nhà

Đề bài

Mô tả

Minh vừa mua một con robot dọn nhà. Sàn nhà của Minh có thể xem là một lưới vuông kích thước (2·109+1)×(2·109+1), chia thành các ô 1×1. Mỗi ô được ký hiệu bởi tọa độ (x,y), trong đó x và y là các số nguyên với |x|≤109 và |y|≤109. Ban đầu, Minh đặt robot ở ô (0,0), chính giữa sàn nhà.

Robot được lập trình sẵn bằng một xâu s gồm n ký tự, mỗi ký tự là U, D, L hoặc R. Ở bước thứ i, robot di chuyển từ ô hiện tại (x,y) như sau:

  • Nếu si= U, robot đi tới ô (x,y+1).
  • Nếu si= D, robot đi tới ô (x,y−1).
  • Nếu si= L, robot đi tới ô (x−1,y).
  • Nếu si= R, robot đi tới ô (x+1,y).

Sau một lần chạy thử, Minh thấy robot thăm chưa đủ nhiều ô khác nhau nên muốn lập trình lại nó. Tuy nhiên robot rất phức tạp, Minh chỉ có thể chèn một xâu t gồm không quá 10 ký tự (cũng gồm các ký tự U, D, L, R) vào một vị trí nào đó của xâu s.

Tìm cách tối ưu hóa ra quá khó, nên Minh quyết định thử một số phương án. Có q phương án. Ở phương án thứ j, Minh chèn xâu tj ngay sau ký tự thứ pj của s (nếu pj=0 thì tj được chèn trước ký tự đầu tiên của s). Với mỗi phương án, Minh muốn biết số ô khác nhau mà robot thăm, tính cả ô xuất phát (0,0).

Lưu ý các phương án là độc lập: mỗi phương án chèn tj vào xâu s ban đầu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và q (1≤n,q≤105), độ dài xâu s và số phương án.

Dòng thứ hai chứa xâu s gồm n ký tự, mỗi ký tự là U, D, L hoặc R.

Dòng thứ j trong q dòng tiếp theo chứa một số nguyên pj (0≤pj≤n) và một xâu tj (1≤|tj|≤10) gồm các ký tự U, D, L và R, mô tả phương án thứ j.

Dữ liệu ra

Với mỗi phương án, in ra số ô khác nhau mà robot thăm, mỗi số trên một dòng.

Ràng buộc

  • 1≤n,q≤105.
  • s chỉ gồm các ký tự U, D, L, R.
  • 0≤pj≤n; 1≤|tj|≤10, tj chỉ gồm các ký tự U, D, L, R.

Ví dụ

Input Output Giải thích
5 4
RRULL
0 L
2 DDL
3 RD
5 UUU
6
9
6
9
Phương án 1 cho xâu LRRULL, robot đi qua (0,0),(−1,0),(0,0),(1,0),(1,1),(0,1),(−1,1): 6 ô khác nhau. Phương án 2 cho xâu RRDDLULL, robot đi qua (0,0),(1,0),(2,0),(2,−1),(2,−2),(1,−2),(1,−1),(0,−1),(−1,−1): 9 ô khác nhau.
4 3
URDL
1 LLRR
4 DU
2 RRRD
6
5
9
Ví dụ bổ sung (không có trong đề gốc). Phương án 1: xâu ULLRRRDL, robot quay lại (−1,1) và (0,1) nên chỉ có 6 ô. Phương án 2: xâu URDLDU, ô mới duy nhất là (0,−1). Phương án 3: xâu URRRRDDL, phần sau của s bị dịch đi (3,−1).

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