HSG THPT Thanh Hóa 2020 - Xoá số
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
CAU3.INP
Output:
CAU3.OUT
Tác giả:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
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
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 ạ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.