AhmedAshraff

Untitled

Aug 1st, 2025
334
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. #define sz(s) (int)(s).size()
  6. #define all(s) s.begin(),s.end()
  7.  
  8. void Speed() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11. }
  12. const int N=101;
  13. int dp[N];
  14. int brute(int x){
  15.     int &ret=dp[x];
  16.     if(~ret)return ret;
  17.     ret=0;
  18.     set<int>st;
  19.     for(int i=1;i<=x;i++){
  20.         if((i&(i-1))==0 && i*2>x)break;
  21.         st.insert(brute(x - i));
  22.     }
  23.  
  24.     while(st.count(ret))ret++;
  25.     return ret;
  26. }
  27. int grundy(int x){
  28.     int pw = 1;
  29.     while(pw * 2 <= x) pw <<= 1;
  30.     int len = pw / 2;
  31.     x -= pw-1;
  32.     int ret=0;
  33.     while(x > 0 && len>0){
  34.         if(x > len) x -= len, len >>= 1;
  35.         else {ret=len+x;break; }
  36.     }
  37.     if(ret)ret--;
  38.     return ret;
  39. }
  40. void solve() {
  41.     int n;
  42.     cin>>n;
  43.     int ans=0;
  44.     for (int i = 0; i < n; ++i) {
  45.         int x;cin>>x;
  46.         ans^= grundy(x);
  47.     }
  48.     cout<<(ans?"First":"Second")<<'\n';
  49. }
  50.  
  51. int main() {
  52.     Speed();
  53.     int tc = 1;
  54.     cin >> tc;
  55.     while (tc--) {
  56.         solve();
  57.     }
  58.     return 0;
  59. }
  60.  
Advertisement
Add Comment
Please, Sign In to add comment