Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

HS09NLG2 - Nim-like game 2

It's time to help Julia to play with Robert again. This time the players pick up sticks from four stacks. A move consists of taking away a positive number of sticks from exactly two chosen stacks.

Players take turns to move. The one who cannot make a move loses. Write a program which determines if for a given set of starting sizes of stacks Julia who moves first can force a win. If so help her making the winning move.

If there are several possibilities of such a move, then choose the one which is lexicographically last, i.e. in which you use the stack with the smallest possible index, taking the largest number of sticks.

Input

In the first line of input there is one integer C (1 ≤C ≤ 1 000), representing the number of test cases. Each test case is described by four integers a[1], a[2], a[3], a[4] (0<= a[i]<= 1 000 000), where a[i] denotes the number of sticks in the i-th stack.

Output

For each testcase write a sentence of the form: '$name wins.' as in the example. And if Julia can win write out four numbers two of which are nonzero - the numbers of sticks to take from each stack. Print a blank line after each testcase.

Example

Input:
2
1 1 1 1
2 2 3 4
Output:
Robert wins.

Julia wins.
0 0 1 2

Scoring

For solving this problem you will score 10 points.

Submit solution!
Added by:Adam Dzedzej
Date:2010-03-15
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:High School Programming League (thanks to Talent Association)
hide comments
2022-08-31 22:43:56
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define m_p(x,y) make_pair(x,y)
#define fri(x,n) for(int i = x ; i < n ; i++)
#define frj(x,n) for(int j = x ; j < n ; j++)
#define frk(x,n) for(int k = x ; k < n ; k++)
#define Ceil(x,y) (x + y - 1) / y
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
ll GCD(ll a, ll b) { return (a) ? GCD(b % a, a) : b; }
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
ll fastpow(ll b, ll p) { if (!p) return 1; ll ret = fastpow(b, p >> 1); ret *= ret; if (p & 1) ret *= b; return ret; }
#define llinf 1e15
#define MAX 10000005
#define N 10000
#define MOD 998244353
#define M 310
#define MAXLOG 25
////////////////////////////
ll a[N];
ll dp[M][M][2];
ll abbas(ll idx, ll prev, ll frst){
ll & ans = dp[idx][prev][frst];
if(~ans) return ans;
if(frst){
ans = 0;
for(int i = idx-1;i>1;i--){
ans |= !abbas(i,idx,0);
if(ans) return ans;
}
return ans;
}
ll kam = prev-idx;
kam*=2;
ans = 0;
for(int i = 1 ; i<= kam ; i++){
if(idx-i < 0) break;
ans |= !abbas(idx-i,idx,0);
if(ans) return ans;
}
return ans;
}
void solve(){
ll n;cin>>n;
ll ans = 0;
fri(0,n){
ll x;cin>>x;
ans^=abbas(x,x,1);
}
cout<<ans<<endl;
}
int main()
{
fast;
int TT = 1; cin >> TT;
memset(dp,-1,sizeof(dp));
for (int tc = 1; tc <= TT; tc++)
{
solve();
}
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.