Bình luận

• 
  

  11

  NguyenHuuNhatQuang    3:32 p.m. 24 Tháng 8, 2020

  Hint

  ---

  Giả sử chúng ta bỏ hết tất cả các quả cân sang bên đĩa B cho đến khi khối lượng bên đĩa B lớn hơn đĩa A và tính chênh lệch khối lượng giữa 2 đĩa. Ta giả sử có \(n\) quả cân và chênh lệch giữa 2 đĩa là \(x\).

  Xét lần lượt các quả cân \(3^i\) \(i\) chạy từ đoạn từ 1 đén \(n\). Ta có 3 trường hợp:

  1. \(x\) chia \(3*3^i\) dư \(2*3^i\) => Bỏ quả cân \(3^i\) từ đĩa A qua đĩa B.
  2. \(x\) chia \(3*3^i\) dư \(3^i\) => Bỏ quả cân \(3^i\) ra ngoài.
  3. \(x\) chia hết cho \(3*3^i\) => Giữ nguyên quả cân \(3^i\) trên đĩa B.

  Ta cập nhật lại \(x\) sau các thao tác trên và làm tương tự với các số \(i\) lớn hơn.

  AC Code

  ---

  #include<bits/stdc++.h>
  using namespace std;
  vector<int>A;
  vector<int>B;
  int main()
  {
      long long m;
      cin>>m;
      long long t=1;
      long long k=0;
      while(k<m)
      {
          k+=t;
          t*=3;
      }
      long long r;
      k-=m;
      t/=3;
      for(int i=1;i<=t;i=i*3)
      {
          r=k%(3*i);
          if(r==2*i) A.push_back(i);
          if(r==0) B.push_back(i);
          k-=r;
      }
      cout<<A.size()<<' ';
      for(int i=0;i<=A.size()-1;i++) cout<<A[i]<<' ';
      cout<<endl;
      cout<<B.size()<<' ';
      for(int i=0;i<=B.size()-1;i++) cout<<B[i]<<' ';
      cout<<endl;
  }
  

1 bình luận nữa