Chủ Nhật, 29 tháng 11, 2020

Một số gọi là may mắn khi số đó chỉ chứa số 4 hoặc 7. Sắp xếp tất cả các số may mắn theo thứ tự. Nhập từ bàn phím 1 số may mắn, hãy in ra chỉ số của số đó

Đề bài: $\href{https://codeforces.com/problemset/problem/535/B}{Đây}$

 Tóm tắt: Một số gọi là may mắn khi số đó chỉ chứa số 4 hoặc 7. Sắp xếp tất cả các số may mắn theo thứ tự. Nhập từ bàn phím 1 số may mắn, hãy in ra chỉ số của số đó (chỉ số bắt đầu từ 1)

Lời giải: Đây là kĩ thuật bitmask khá quen thuộc , ta ánh xạ số 4 cho 0 và số 7 cho 1 , từ đó ta sinh tất cả các trường hợp và duyệt là xong. Các bạn có thể xem source tại đây

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll po(ll a, ll n){
  5. ll res=a,ans=1;
  6. while(n){
  7. if(n&1) ans=ans*res;
  8. res=res*res;
  9. n/=2;
  10. }
  11. return ans;
  12. }
  13. int main(){
  14. string s;
  15. cin>>s;
  16. string res;
  17. ll i,j;
  18. ll len = s.size();
  19. for(i=0;i<(1<<len);i++){
  20. res="";
  21. for(j=0;j<len;j++){
  22. if((i>>j)&1==1) res=res+'7'; else res=res+'4';
  23. }
  24. reverse(res.begin(),res.end());
  25. if(res==s){
  26. ll ans = po(2,len)-2;
  27. ans = ans +(i+1);
  28. cout<<ans;
  29. return 0;
  30. }
  31. }
  32. return 0;
  33. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...