Kéo Búa Bao Trừ Một

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Trong trò chơi Kéo Búa Bao biến thể, có $N$ ký hiệu được đánh số từ $1$ đến $N$ . Kết quả giữa hai ký hiệu được cho bởi một bảng: nếu ký hiệu $i$ đấu với ký hiệu $j$ , kết quả là W (thắng), L (thua), hoặc D (hòa) từ góc nhìn của ký hiệu $i$ .

Bessie và Elsie chơi $M$ ván. Trong mỗi ván, Elsie chọn hai ký hiệu $x$ và $y$ (công khai). Bessie sau đó chọn hai ký hiệu $a$ và $b$ (có thể trùng nhau). Cả hai người đều chọn một ký hiệu từ cặp của mình để đấu. Bessie thắng nếu cô ấy có ít nhất một ký hiệu đánh bại được cả hai ký hiệu của Elsie (bất kể Elsie chọn ký hiệu nào).

Đếm số cặp $(a, b)$ mà Bessie có thể chọn để đảm bảo thắng.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo: Dòng thứ $i$ chứa $i$ ký tự thuộc ${D, W, L}$ — kết quả khi ký hiệu $i$ đấu với ký hiệu $1, 2, \dots, i$ .
$M$ dòng tiếp theo: Hai số nguyên $x$ , $y$ — cặp ký hiệu của Elsie.

Dữ liệu ra

$M$ dòng, mỗi dòng là số cặp $(a, b)$ giúp Bessie thắng.

Ràng buộc

$1 \leq N \leq 3000$
$1 \leq M \leq 3000$
Giới hạn thời gian: 3 giây

Ví dụ

Input	Output	Giải thích
3 3 D WD LWD 1 2 2 3 1 1	0 0 5	Ván 3: Elsie chọn $(1, 1)$ , Bessie cần ký hiệu thắng 1. Ký hiệu 2 thắng 1, nên mọi cặp $(a, b)$ có chứa 2 đều thắng: $(2, 1), (2, 2), (2, 3), (1, 2), (3, 2)$ = 5 cặp.

Bình luận

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