trang chủ / đề bài / icpc25_mt_c

Con trỏ trong VS Code

Đề bài

Mô tả

Bạn đang làm việc khuya trong VS Code, chỉnh sửa một tệp rất đặc biệt. Tệp này không chứa văn bản bình thường: nó chỉ gồm các ký tự ngoặc ( và ). Dãy ngoặc được đảm bảo cân bằng hoàn hảo, nghĩa là mỗi dấu mở ngoặc ( đều có một dấu đóng ngoặc ) tương ứng.

Con trỏ của bạn hoạt động hơi khác so với con trỏ thông thường của VS Code. Đó là một con trỏ dạng khối luôn nằm đè lên một ký tự, chứ không nằm giữa hai ký tự. Bạn có thể di chuyển con trỏ trong tài liệu bằng một vài thao tác quen thuộc:

  • ← (mũi tên trái): di chuyển con trỏ sang trái một vị trí. Nếu con trỏ đang ở ký tự đầu tiên thì nó đứng yên.
  • → (mũi tên phải): di chuyển con trỏ sang phải một vị trí. Nếu con trỏ đang ở ký tự cuối cùng thì nó đứng yên.
  • Ctrl + Shift + \ : nhảy ngay đến dấu ngoặc tương ứng với dấu ngoặc hiện tại. Nếu đang ở (, con trỏ nhảy đến ) tương ứng; nếu đang ở ), con trỏ nhảy đến ( tương ứng.

Bạn sẽ nhận được một số truy vấn về trạng thái trình soạn thảo. Mỗi truy vấn cho vị trí bắt đầu S và vị trí đích T của con trỏ. Nhiệm vụ của bạn là xác định số thao tác ít nhất cần thiết để di chuyển con trỏ từ S đến T theo các quy tắc trên.

Dữ liệu vào

  • Dòng đầu tiên gồm một số nguyên N: độ dài dãy ngoặc.
  • Dòng thứ hai gồm dãy ngoặc độ dài N.
  • Dòng thứ ba gồm một số nguyên Q: số truy vấn.
  • Q dòng tiếp theo, mỗi dòng gồm hai số nguyên S và T: vị trí bắt đầu và vị trí đích của con trỏ.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng một số nguyên: số thao tác ít nhất để di chuyển con trỏ từ vị trí S đến vị trí T.

Ràng buộc

  • 1≤N≤105; dãy ngoặc cân bằng
  • 1≤Q≤105
  • 1≤S,T≤N

Ví dụ

Input Output Giải thích
6
(()())
3
1 6
2 3
5 2
1
1
3
Từ vị trí 1 nhảy thẳng đến dấu ngoặc tương ứng ở vị trí 6. Từ 5 đến 2: chẳng hạn 5→4 (trái), 4→3 (trái), 3→2 (nhảy).
12
((()))()(())
5
1 12
3 8
6 9
2 11
4 4
5
5
3
7
0
Ví dụ bổ sung.

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