Quả cân

Xem PDF



Tác giả:
Dạng bài
Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cửa hàng của duyhung123abc có một cái cân và các quả cân có khối lượng có dạng \(3k\) (tức lũy thừa của 3). VD: \(1, 3, 9, 27, 81, ...\)

Khối lượng của các quả cân khác nhau từng đôi một. Duyhung123abc có một vật nặng \(M\) kg, vật nặng được đặt vào đĩa bên trái của cái cân. Hãy giúp anh ta đặt các quả cân vào 2 đĩa sao cho cân thãng bằng

Input

  • Chứa 1 số nguyên \(M\) duy nhất (\(0 \le M \le 10^8\))

Output

  • Dòng 1: số \(A\) là số quả cân đặt vào đĩa bên trái, theo sau gồm \(A\) số là khối lượng của các quả cân theo thứ tự tăng dần
  • Dòng 2: số \(B\) là số quả cân đặt vào đĩa bên phải, theo sau gồm \(B\) số là khối lượng của các quả cân theo thứ tự tăng dần

Example

Test 1

Input
42 
Output
3 3 9 27
 1 81 

Bình luận


  • 9
    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\)\(2*3^i\) => Bỏ quả cân \(3^i\) từ đĩa A qua đĩa B.
    2. \(x\) chia \(3*3^i\)\(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;
    }
    

    • 2
      todonghai2k7 3:30 p.m. 24 Tháng 8, 2020

      3 ^ k chứ nhỉ