HSG THPT Thanh Hóa 2022 - Mật Mã
Xem dạng PDF
Trên một vách đá có ghi rất nhiều các con số bí ẩn mà chúng có mối liên hệ với số ~30~. Sau một thời gian nghiên cứu, các chuyên gia đã tìm được cách giải mã các số đó như sau: Hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của ~30~.
Hãy viết chương trình để giúp các chuyên gia giải mã các số bí ẩn đó.
Input
Cho trong tệp MATMA.INP gồm một dòng duy nhất chứa số nguyên dương ~N~, với ~N~ có tối đa ~10^7~ chữ số là số cần giải mã.
Output
Ghi ra tệp MATMA.OUT một số nguyên duy nhất, là số lớn nhất chia hết cho ~30~, tìm được bằng cách hoán vị các chữ số của ~N~. Nếu không tìm thấy thì đưa ra ~-1~ (âm một).
Sample Input 1
1002
Sample Output 1
2100
Sample Input 2
12498567859
Sample Output 2
-1
Notes
Ở ví dụ đầu tiên, số ~2100~ là hoán vị lớn nhất của số ~1002~ và chia hết cho ~30~.
Ở ví dụ thứ hai, không tồn tại số hoán vị nào chia hết cho ~30~.
Bình luận
Để hoán vị chia hết 30 thì nó phải chia hết cho 3 và 10 , như vậy tổng cách phần tử trong hoán vị phải chia hết cho 3 , và trong hoán vị ít nhất có 1 chữ số 0 . Nếu thoả mãn các đk trên, chỉ cần sort giảm dần và in ra là đc
include <bits/stdc++.h>
using namespace std; int main(){ if(fopen("matma.inp","r")){ freopen("matma.inp","r",stdin); freopen("matma.out","w",stdout); } iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); string s; cin>>s; if(s.find('0')==string::npos){ cout<<-1; return 0; } long long sum=0; for(int i=0;i<s.size();i++){ char c=s[i]; sum+=c-'0'; } if(sum%3!=0){ cout<<-1; return 0; } sort(s.rbegin(),s.rend()); cout<<s; return 0; }
test mạnh thí
em xin góp cách làm ạ
Spoil Một số chia hết cho 30 thì phải chia hết cho 3 và 10 => Cộng các phần tử lại => Nếu như tổng các số đó % 3 == 0 và có số 0 trong đó thì kết quả là N sau khi sort => Nếu ko thì cout -1
include <bits/stdc++.h>
using namespace std;
int a[10000007],n; long long t=0,d=0;
int main() { string s; cin >> s; for (int i = 0; i < s.size(); i++) { a[i] = s[i] - '0'; } n=s.size(); sort(a,a+n,greater<int>()); for(int i=0;i<n;i++) { t+=a[i]; if(a[i]==0) d++; } if(t%3==0 && d>0) { for(int i=0;i<n;i++) { cout<<a[i]; } } else { cout<<-1; } return 0; }
vì sao em code này ko ra ạ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
.
Cách giải: