Giá trị của dãy ngoặc
Xem PDF
Điểm:
400
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Người ta định nghĩa một dãy ngoặc đúng như sau:
- Xâu rỗng là một dãy ngoặc đúng.
- Nếu A là dãy ngoặc đúng thì (A); [A]; {A} cũng là một dãy ngoặc đúng
- Nếu A, B là những dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.
Những dãy ngoặc sau được xem là đúng:
- [](())
- ({[]})
- ()[{()[]}]
Những dãy ngoặc sau thì không:
- )(
- ((([]))
- ){}[]{
Bạn được cho 1 dãy ngoặc hợp lệ và 3 số \(a, b, c\). đã quy ước giá trị của dãy ngoặc như sau:
- Xâu rỗng có giá trị là \(0\)
- () có giá trị là \(a\); [] có giá trị là \(b\); {} có giá trị là \(c\)
- Nếu A là dãy ngoặc có giá trị là \(x\) thì (A) có giá trị là \(x.a\); [A] có giá trị là \(x.b\); {A} có giá trị là \(x.c\)
- Nếu A, B là dãy ngoặc có giá trị lần lượt là \(x\) và \(y\) thì AB có giá trị là \(x+y\)
Yêu cầu: Hãy tính giá trị của dãy ngoặc mà đã cho sau khi mod \(10^9+7\)
Input
- Dòng 1 nhập số \(t\) chỉ số test \((t \le 100)\)
- \(t\) block tiếp theo, mỗi block có dạng như sau:
- Dòng 1 nhập vào dãy ngoặc đã cho có độ dài không quá \(10^5\)
- Dòng 2 nhập vào 3 số \(a, b, c(|a|, |b|, |c|\le 10^9)\)
Output
- Mỗi dòng xuất ra kết quả theo yêu cầu của bài toán tương ứng với từng test
Example
Test 1
Input
2
([{}])
2 3 4
[]{()}
1 -14 7Output
24
1000000000Note
Trong test 1:
- {} có giá trị là $4$
- [{}] có giá trị là $3.4=12$
- ([{}]) có giá trị là $2.12=24$
- $24$ $mod$ $10^9+7=24$
Trong test 2:
- [] có giá trị là $-14$
- () có giá trị là $1$
- {()} có giá trị là $7.1=7$
- []{()} có giá trị là $-14+7=-7$
- $-7$ $mod$ $10^9+7=1000000000$
Bình luận
ai thắc mắc gì về test không?
có ai hiểu đề nói gì đâu mà thắc mắc :))
từ đoạn nào?