Olympic Chuyên KHTN 2020 - Ngày 1 - Bài 1 - BABA

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Cho ~1~ xâu ký tự chứa toàn chữ số khác ~0~. Có ~2~ bài toán con:

  1. Có bao nhiêu xâu con liên tiếp tạo thành ~1~ số chia hết cho ~33~? Xâu con dù giống nhau nhưng ở vị trí khác nhau được coi là khác nhau.
  2. Số (được tạo từ xâu con liên tiếp) lớn nhất chia hết cho ~33~ là số nào? Nếu không có số nào in ra ~-1~.

Input

Dòng đầu chứa ~1~ xâu kí tự ~s~. Dòng tiếp theo chứa chỉ số của bài toán con.

Output

In ra đáp án trên 1 dòng duy nhất.

SUBTASKS

~30\%~ số điểm ~|s| \leq 1000~. ~70\%~ số điểm ~|s| \leq 1000000~.

Sample Input 1

1223
1

Sample Output 1

0

Sample Input 2

12311
2

Sample Output 2

231

Comments

Please read the guidelines before commenting.


  • -1
    thaihsgserk60  commented on Sept. 25, 2025, 2:17 p.m.

    ai co code khong cho minh xem code voi code minh toan bi tle


  • -2
    minhduca2k53  commented on Sept. 24, 2025, 12:36 a.m.

    Đm mày FLaming


  • 1
    PDNAM  commented on July 21, 2024, 2:19 p.m. ← edit 2

    my sol:

    với bài toán con 1 , ta xây dựng một mảng sum , với sum[i] có ý nghĩa là số mà xâu con từ 1 -> i tạo thành modulo cho 33.(hiển nhiên 1 <= i <= n); nhận thấy đoạn con u -> v chia hết cho 33 khi và chỉ khi sum[v] = ( sum[u - 1] * 10 ^ (v - u + 1) ) modulo 33 nhận thấy tính chất dố nên ta cho thể sử dụng mảng d để đếm phân phối , với d[i] (0 <= i <= 32) nghĩa là số lượng (sum[j] * 10 ^ (n - j)) modulo 33 mà = i (1 <= j <= n) cuối cùng duyệt qua từng d[i] và ans += d[i] * (d[i] - 1) / 2; dpt O(n);

    với bài toán con 2 , ta xây dựng thêm một mảng kiểu pair dd , với dd[i].first là số j đầu tiên mà (sum[j] * 10 ^ (n - j)) modulo 33 mà = i , còn dd[i].second là số j cuối thoả mãn chỉ việc so sánh từng số dc tạo thành từ xâu con đánh chỉ số từ dd[i].first + 1 đến dd[i].second thôi tối đa chỉ xét tới 33 số nên dpt là O(33 * n);