HSG THPT Thanh Hóa 2020 - Xoá số

View as PDF
Submit solution
Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: CAU3.INP
Output: CAU3.OUT
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho số tự nhiên ~N~. Bằng cách giữ nguyên hoặc xoá đi một số chữ số liên tiếp của ~N~ (nhưng không xoá hết) ta nhận được một số mới, nếu số ~N~ bị chia thành ~2~ phần thì số mới được ghép lại từ hai phần này và giữ nguyên trật tự.

Yêu cầu: Hãy xác định tất cả số cách xoá như trên để số ~N~ mới sau khi xoá chia hết cho ~3~. Lưu ý là hai vị trí khác nhau sẽ tạo ra hai cách xoá khác nhau. Số ~N~ giữ nguyên cũng được coi là một cách xoá.

Input

Đọc từ tệp CAU3.INP chứa số nguyên dương ~N~ (không quá ~10^5~ chữ số)

Output

Ghi ra tệp CAU3.OUT một số nguyên là số cách xoá tìm được

Scoring

Subtask Điểm Giới hạn
1 ~50\%~ Số các chữ số của ~N \le 300~
2 ~25\%~ Số các chữ số của ~N \le 10^4~
3 ~25\%~ Số các chữ số của ~N \le 10^5~

Sample Input 1

1005

Sample Output 1

4

Sample Input 2

2009

Sample Output 2

3

Comments

Please read the guidelines before commenting.


  • -2
    quannmq2009  commented on Dec. 12, 2024, 3:54 p.m.

    ai giải thik hộ test mẫu với ạ huhu


    • -2
      EZGAME  commented on Dec. 13, 2024, 9:04 a.m.

      test 1 sẽ có 4 cách xóa: 1005 1-05 10-5 1005 test 2 sẽ có 3 cách xóa: ---9 -009 --09


      • -2
        vinhlewb123  commented on Feb. 8, 2025, 9:11 a.m.

        cách xóa thứ 4 của test 1 là gì vậy b


  • 2
    Duyanh_TQ  commented on Nov. 5, 2024, 2:28 p.m.

    include <bits/stdc++.h>

    using namespace std; long long solve(string& s){ s = " " + s; long long prefixSum[s.length()] = {0}, sum = 0; int cnt[3] = {0}; for(int i = 1; i < s.length(); ++i){ int digit = s[i] - '0'; sum += digit; prefixSum[i] = prefixSum[i - 1] + digit; cnt[prefixSum[i] % 3]++; } long long res = 0; for(int i = 1; i < s.length(); ++i){ res += cnt[(sum + prefixSum[i - 1]) % 3]; cnt[prefixSum[i] % 3]--; } if(sum % 3 != 0){ res--; } return res; } int main(){ freopen("CAU3.INP", "r", stdin); freopen("CAU3.OUT", "w", stdout); ios::syncwithstdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; cout << solve(s); return 0; } code cho ae tham khao nha dung cho toi down vote plss=((


    • -4
      dmnguyel23  commented on Jan. 5, 2025, 1:07 a.m.

      giải thích code với ạ


  • -49
    fromhgbwithlove  commented on Feb. 8, 2024, 10:34 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -23
      tretrauvl  commented on Feb. 28, 2024, 2:22 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.