LBC_3B - Dr. Patel và sinh nhật con gái

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Dr. Patel đang chơi trò chơi với con gái của mình nhân ngày sinh nhật của cô bé. Trò chơi được diễn ra như sau:

Bắt đầu từ Dr. Patel đi trước, ông chọn 1 số ~N~ và kiểm tra xem nếu nó tồn tại một số ~X~ mà ~2^X = N~, họ chia ~N~ cho ~2~. Nếu không họ giảm ~N~ đi bằng phép toán ~N - 2^Y~ sao cho ~2^Y < N~ và ~2^Y~ là lớn nhất. Cho tới khi ai thực hiện 1 trong 2 phép toán trên ra ~1~, người đó giành chiến thắng.

Yêu cầu: Cho một số ~N~ hãy giúp Dr. Patel tính xem liệu ông ấy có thể giành chiến thắng hay không?

Input

  • Dòng đầu gồm 1 số nguyên ~T~ là số bộ test ~(1 \leq T \leq 10^5)~.
  • ~T~ dòng tiếp theo, mỗi dòng gồm 1 số nguyên dương ~N~ ~(1 \leq N \leq 2^{64} - 1)~.

Output

  • Gồm ~T~ dòng ứng với mỗi test, nếu Dr. Patel có thể chiến thắng in ra yes ngược lại in ra no.

Sample

Input #1
2
132
6
Output #1
Case #1: yes
Case #2: no

Comments

Please read the guidelines before commenting.



  • 0
    tuanm123  commented on Jan. 15, 2024, 2:17 p.m.

    include <bits/stdc++.h>

    using namespace std;

    define ll unsigned long long

    define fastio iosbase::syncwith_stdio(false); cin.tie(NULL);

    int t; ll n;

    bool islog2(ll n) { double x = log2(n); return (x == (ll)x); }

    bool procs(ll n) { int cnt = 0; while (n != 1) { cnt ++; if (islog2(n)) n = n / 2; else n -= (pow(2, (ll)log2(n))); } if (cnt % 2 == 0) return false; else return true; }

    int main() { fastio

    cin >> t;
    
    for (int i = 1; i <= t; i++) {
        cin >> n;
        if (procs(n))
            cout << "Case #" << i << ": " << "no" << "\n";
        else
            cout << "Case #" << i << ": " << "yes" << "\n";
    }
    
    return 0;
    

    } tại sao lại sai vậy ạ