Submit solution
Points:
0.20 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
CAU3.INP
Output:
CAU3.OUT
Author:
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
ai giải thik hộ test mẫu với ạ huhu
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
cách xóa thứ 4 của test 1 là gì vậy b
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=((
giải thích code với ạ
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.