| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P176PROE - ROUND 6E - Chuỗi con đẹp |
Bạn được cho một chuỗi s, bao gồm các chữ cái tiếng anh in thường. Một số chữ cái tiếng anh là đẹp, những chữ còn lại là xấu.
Một chuỗi con s[l...r] (1 ≤ l ≤ r ≤ |s|) của chuỗi s = s1s2...s|s| (với |s| là độ dài của chuỗi s) là chuỗi slsl + 1...sr.
Một chuỗi con s[l...r] là đẹp, nếu trong tất cả chữ cái sl, sl + 1, ..., sr có nhiều nhất k chữ cái xấu (xem giải thích của test để hiểu rõ hơn).
Nhiệm vụ của bạn là tìm ra số lượng các chuỗi con đẹp khác nhau của chuỗi đã cho. Hai chuỗi con s[x...y] và s[p...q] được cho là khác nhau nếu nội dung của chúng khác nhau, tức là s[x...y] ≠ s[p...q].
Input
Dòng đầu tiên chứa một chuỗi không rỗng s, gồm chữ cái tiếng anh in thường, độ dài của chuỗi tối đa là 1500 kí tự.
Dòng thứ hai chứa một chuỗi chỉ bao gồm các kí tự "0" và "1", có độ dài chính xác là 26 kí tự.
Nếu kí tự thứ i của chuỗi bằng "1" thì chữ cái tiếng anh thứ i là đẹp, nếu không nó là xấu. Tức là, kí tự đầu tiên của chuỗi này tương ứng với chữ "a", kí tự chứ hai tương ứng với chữ "b" và vân vân.
Dòng thứ ba chứa một số nguyên k k (0 ≤ k ≤ |s|) – số lượng lớn nhất của các chữ cái xấu trong một chuỗi con đẹp.
Output
In ra số nguyên duy nhất – số lượng chuỗi con đẹp của chuỗi s.
Example
Test 1:
Input:
ababab
01000000000000000000000000
1
Output:
5
Test 2:
Input:
acbacbacaa
00000000000000000000000000
2
Output:
8
Giải thích:
- Test 1: Có các chuỗi con đẹp sau : "a", "ab", "b", "ba", "bab".
- Test 2: Có các chuỗi con đẹp sau : "a", "aa", "ac", "b", "ba", "c", "ca", "cb".
| Được gửi lên bởi: | adm |
| Ngày: | 2017-03-24 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
