Problem:


Score : 1000 points

Problem Statement

There are N integers written on a blackboard. The i-th integer is A_i, and the greatest common divisor of these integers is 1.

Takahashi and Aoki will play a game using these integers. In this game, starting from Takahashi the two player alternately perform the following operation:

Select one integer on the blackboard that is not less than 2, and subtract 1 from the integer.

Then, divide all the integers on the black board by g, where g is the greatest common divisor of the integers written on the blackboard.

The player who is left with only 1s on the blackboard and thus cannot perform the operation, loses the game.
Assuming that both players play optimally, determine the winner of the game.

Constraints

1 ≦ N ≦ 10^5

1 ≦ A_i ≦ 10^9

The greatest common divisor of the integers from A_1 through A_N is 1.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 … A_N

Output

If Takahashi will win, print First. If Aoki will win, print Second.

Sample Input 1

3
3 6 7

Sample Output 1

First

Takahashi, the first player, can win as follows:

Takahashi subtracts 1 from 7. Then, the integers become: (1,2,2).

Aoki subtracts 1 from 2. Then, the integers become: (1,1,2).

Takahashi subtracts 1 from 2. Then, the integers become: (1,1,1).

Sample Input 2

4
1 2 4 8

Sample Output 2

First

Sample Input 3

5
7 8 8 8 8

Sample Output 3

Second



Sample input:
3
3 6 7


Sample output:
First

Submission status: Time Limit Exceeded

Solution code:


import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)

def score(A):
	return(sum(A)-len(A))

def Ifavor(A):
	return(score(A)%2==1)	

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	
def testmove(N,A,i):
	if A[i]<=1:
		return(False)
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	if Ifavor(A):
		return(False)
	else:
		j=0
		while j<N:
			if A[j]<=1:
				continue
			A[j]-=1
			h=gcdm(A)	
			if Ifavor([x//h for x in A])==False:
				return(False)
			A[j]+=1
			j+=1
		return(True)

N=int(input())
B=[int(x) for x in input().split()]
'''
inp=St.splitlines()
N=int(inp[0])
B=[int(x) for x in inp[1].split()]
'''
if Ifavor(B):
	print('First')
else:
	e=0
	while e<N:
		A=copy.copy(B)
		if testmove(N,A,e):
			break
		e+=1
	
	if e==N:
		print('Second')
	else:
		print('First')

Submission status: Time Limit Exceeded

Solution code:


import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)

def score(A):
	return(sum(A)-len(A))

def Ifavor(A):
	return(score(A)%2==1)	

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	
def testmove(N,A,i):
	if A[i]<=1:
		return(False)
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	if Ifavor(A):
		return(False)
	else:
		j=0
		while j<N:
			if A[j]<=1:
				continue
			A[j]-=1
			h=gcdm(A)	
			if Ifavor([x//h for x in A])==False:
				return(False)
			A[j]+=1
			j+=1
		return(True)

N=int(input())
B=[int(x) for x in input().split()]
'''
inp=St.splitlines()
N=int(inp[0])
B=[int(x) for x in inp[1].split()]
'''
if Ifavor(B):
	print('First')
else:
	e=0
	while e<N:
		A=copy.deepcopy(B)
		if testmove(N,A,e):
			break
		e+=1
	
	if e==N:
		print('Second')
	else:
		print('First')

Submission status: Time Limit Exceeded

Solution code:
import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)

def score(A):
	return(sum(A)-len(A))

def Ifavor(A):
	return(score(A)%2==1)	

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	
def testmove(A,i):
	B=copy.deepcopy(A)
	N=len(B)
	playmove(B,i)
	if Ifavor(B):
		return('False')
	else:
		e=0
		while e<N:
			C=copy.deepcopy(B)
			playmove(C,e)
			e+=1
			if Ifavor(C)==False:
				return(False)
		return('True')
	

N=int(input())
A=[int(x) for x in input().split()]
#inp=St.splitlines()
#N=int(inp[0])
#A=[int(x) for x in inp[1].split()]

B=copy.deepcopy(A)


if Ifavor(B):
	print('First')
else:
	maxply=sum(B)-N
	ply=1
	while min(B)>1 and ply<=maxply:
		e=0
		while e<N:
			if testmove(B,e):
				break
			e+=1
			
		if e==N:
			break
		else:
			playmove(B,e)
			ply+=1

	if (ply%2==1)!=Ifavor(B):
		print('Second')
	else:
		print('First')

Submission status: Time Limit Exceeded

Solution code:
import random
import copy
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)
def candi(x):
	d=dict()
	for i in range(len(x)):
		d[x[i]]=i
	y=list(d.values())
	return(y)
def sto(N,AAA,tryno,isFirst=True):
	AA=copy.deepcopy(AAA)
	ply=0
	moves=[]
	moves_win=[]
	
	if max(AA)<=1: 	return(0,0,True)
	cAA=candi(AA)
	for j in cAA:
		if AA[j]>1:
			win=0
			
			for r in range(tryno):
				A=copy.deepcopy(AA)
				ply=1
				A[j]-=1
				g=gcdm(A)
				A=[x//g for x in A]
				while max(A)>1 and min(A)>1:
					ca=candi(A)
					i=ca[random.randint(0,len(ca)-1)]
					if A[i]>1:
						ply+=1
						A[i]-=1
						g=gcdm(A)
						A=[x//g for x in A]
				ply+=sum(A)-N
				if (ply %2==0)!=isFirst:win+=1
				
			moves.extend([j])
			moves_win.extend([win])
		
	if isFirst:
		player='First'
		ans=max(moves_win)
	else:
		player='Second'
		ans=min(moves_win)
	selected=moves[moves_win.index(ans)]
	#print(AAA)
	#print(cAA)
	#print(moves_win,player,selected)
	
	AAA[selected]-=1
	g=gcdm(AAA)
	AAA=[x//g for x in AAA]
	#print(AAA)
	return([selected,ans,False,AAA])



N=int(input())
AAA=[int(x) for x in input().split()]


tryno=100
F=[]
isFirst=True
while max(AAA)>1 and min(AAA)>1:
	y=sto(N,AAA,tryno,isFirst)
	if y[2]: break
	F.extend([y[0]])
	isFirst=(isFirst!=True)
	AAA=y[3]

judge=len(F)+sum(AAA)-N

if judge%2==1:
	print('First')
else:
	print('Second')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = raw_input()
s = map(int,raw_input().split(" "))


def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

def checker(s):
    ze =np.array([])
    y=[]
    for i in s:
        a = [gcd(z,i-1) for z in s]
        ze = np.append(ze,np.array([int(sum(a))]))
        y.append(a)
    da=np.argmin(ze)
    return y[da]

count = 0
while len(s)!=sum(s):
    s =checker(s)
    count +=1

if count%2 == 1:
    print "First"
else:
    print "Second"

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()

if N == 1:
    print('Second')
    exit()

if N == 2:
    print('First')
    exit()

from math import gcd

r = 0  # 0:高橋君の番、1:青木君の番
while True:
    if (sum(A)-N) % 2 == 1:
        if r == 0:
            print('First')
        else:
            print('Second')
        break
    else:
        a = 0  # 奇数の要素の個数
        b = 0  # 1の個数
        for i in range(N):
            if A[i] % 2 == 1:
                a += 1
            if A[i] == 1:
                b += 1
        if a != 1 or b > 0:
            if r == 0:
                print('Second')
            else:
                print('First')
            break
        else:
            g = 0
            for i in range(N):
                if A[i] % 2 == 1:
                    g = gcd(g,A[i]-1)
                else:
                    g = gcd(g,A[i])
            for i in range(N):
                A[i] = A[i]//g
            r = 1-r

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
def gcds(ls):
  ret = 0
  for i in ls:
    ret = gcd(ret,i)
  return ret
def flg(ls):
  if (sum(ls)-len(ls))%2:
    ret = 1
  else:
    ret = 2
  return ret
if n%2 == 0:
  if sum(a)%2:
    print("First")
  else:
    print("Second")
else:
  cnt = 0
  while flg(a)%2 == 0:
    odd = 0
    oddidx = -1
    even = 0
    for i,x in enumerate(a):
      if x%2:
        odd += 1
        oddidx = i
      else:
        even += 1
    if odd == 1 and a[oddidx] > 1:
      a[oddidx] -= 1
      g = gcds(a)
      for i in range(n):
        a[i] //= g
      cnt += 1
    else:
      break
  if (flg(a)+cnt)%2 == 1:
    print("First")
  else:
    print("Second")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from functools import reduce
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def calc(A):
    N = len(A)
    if N == 1:
        return A[0]%2 == 0

    K = sum(1 for a in A if a % 2 == 0)
    if K & 1:
        return True
    if N-K != 1:
        return False
    if min(A) == 1:
        return False
    A = [a-a%2 for a in A]
    g = reduce(gcd, A)
    A = [a//g for a in A]
    return not calc(A)


N = int(readline())
A = list(map(int, readline().split()))
print('First' if calc(A) else 'Second')

Submission status: Accepted

Solution code:
#d
#the niumbers of evens is important
#the point is, there is no influence to odd/even if you divide them by odd numbers.
#You should do simulation only in the case where there is one odd over 3 and even numbers of even numbers

from fractions import gcd

def count(a):
    odd, even = 0,0
    for x in a:
        if x % 2 == 1: odd = odd + 1
        else: even = even + 1
    return odd,even

def deal(n,a):
    odd,even = count(a)
    if even == 0:
        return False
    if even % 2 == 1:
        return True
    if odd > 1:
        return False
    
    #the case where there is one odd (over 3) and even numbers of even numbers
    #calculate gcd by step by step
    #if you write g = 1, it is a lie.
    if a[0] % 2 == 0:
        g = a[0]
    else:
        g = a[1]
        
    for i in range(0,n):
        if a[i] % 2 == 1:
            if a[i] == 1: 
                return False
            a[i]  -= 1
        g = gcd(a[i], g)
    return not deal(n,list(map(lambda x: x//g,a)))

n = int(input())
a = [int(i) for i in input().split()]
if deal(n,a):
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def gcd_list(A):
    res = A[0]
    for a in A:
        res = gcd(a, res)
    return res

def check(N,A):
    if 1 in A:
        if((sum(A)-N) & 1):
            return 0 #先手
        else:
            return 1 #後手
    odd_cnt, even_cnt = 0, 0
    for a in A:
        if(a&1):
            odd_cnt += 1
        else:
            even_cnt += 1
    if(even_cnt & 1):
        return 0
    else:
        if(odd_cnt >= 2):
            return 1
        else: ##奇数のを選ぶしかないのでその後どうなるかを調べる
            odd_idx = [i for i in range(N) if A[i]&1 ][0]
            A[odd_idx] -= 1
            G = gcd_list(A)
            return check(N, [a//G for a in A]) ^ 1
def main():
    N=I()
    A=LI()
    print(["First","Second"][check(N,A)])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

N = int(readline())
A = np.array([int(x) for x in readline().split()])

if N == 1:
    print('Second')
    exit()

# np.gcdがバージョン違いでないので仕方なく
def gcd(A):
    B = A.copy()
    while len(B) > 1:
        i = np.argmin(B)
        d = B[i]
        B %= d
        B[i] = d
        B = B[B!=0]
    return B[0]

def can_win(A):
    od = (A&1).sum()
    ev = N-od
    if ev % 2 == 1:
        # 自分は偶数→奇数として、2での約分を拒否し続けられる
        return True
    if od > 1:
        # 逆の立場。永遠に2での約分を拒否されて負け
        return False
    i = np.where(A&1)[0][0]
    if A[i] == 1:
        # これも永遠に2で約分できない
        return False
    # A[i]から1を引いて、約分を試して手渡しするしかない
    A[i] -= 1
    d = gcd(A)
    A //= d
    return not(can_win(A))

answer = 'First' if can_win(A) else 'Second'
print(answer)

Submission status: Accepted

Solution code:
from fractions import gcd
 
def gcdL(L):
    g=L[0]
    for i in range(1,len(L)):
        if g==1:
            return(g)
        g=gcd(g,L[i])
    return g
def play(A,i):
    A[i]-=1
    g=gcdL(A)
    return [x//g for x in A]
def cnt(A):
    odd,even=0,0
    for a in A:
        if a%2:
            odd+=1
        else:
            even+=1
    return odd,even    

n=int(input())
A=list(map(int,input().split()))
First=1
while True:
    odd,even=cnt(A)
    if even%2:
        print('First' if First else 'Second')
        break
    elif odd>1:
        print('Second' if First else 'First')
        break
    else:
        for i in range(n):
            if A[i]%2:
                break
        if A[i]==1:
            print('Second' if First else 'First')
            break
        else:
            A=play(A,i)
            First^=1

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
S=sum(A)
def gcd(x,y):
  if x<y:
    x,y=y,x
  if x%y==0:
    return y
  return gcd(y,x%y)
if (S-N)%2:
  print("First")
else:
  First=False
  while True:
    odd=-1
    for i in range(N):
      if A[i]%2:
        if odd>=0 or A[i]==1:
          if First:
            print("First")
          else:
            print("Second")
          exit()
        A[i]-=1
        odd=i
      if i==0:
        g=A[0]
      else:
        g=gcd(g,A[i])
    S=0
    for i in range(N):
      A[i]=A[i]//g
      S+=A[i]
    if (S-N)%2==0:
      if First:
        First=False
      else:
        First=True
    else:
      if First:
        print("First")
      else:
        print("Second")
      exit()

Submission status: Accepted

Solution code:
import random
def tester(N=0):
	'''制約
1≦N≦105
1≦Ai≦109
'''
	maxno1=1e5
	maxno2=1e9
	s=input()
	if s!='':return(s)
	
	if N==0:
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		return(' '.join(list(map(str,A))))

import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		if g==1:
			return(g)
		g=gcd(g,x[i])
	return(g)

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	return([x//g for x in A])

def noofevens(A):
	r=0
	for i in A:
		if i%2==0:
			r+=1
	return(r)
			

N=int(tester())
A=[int(x) for x in tester(N).split()]


isFirstmove=True
while True:
	e=noofevens(A)
	if e%2==1:
		if isFirstmove:
			print('First')
		else:
			print('Second')
		break
	elif N-e>1:
		if isFirstmove:
			print('Second')
		else:
			print('First')
		break
	else:	
		for i in range(N):
			if A[i]%2==1:
				break
		if A[i]==1:
			if isFirstmove:
				print('Second')
			else:
				print('First')
			break
		else:
			A=playmove(A,i)
			isFirstmove=(isFirstmove!=True)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from fractions import gcd

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

def count(a):
    odd, even = 0,0
    for x in a:
        if x % 2 == 1: odd = odd + 1
        else: even = even + 1
    return odd,even

def deal(n,a):
    odd,even = count(a)
    if even == 0:
        return False
    if even % 2 == 1:
        return True
    if odd > 1:
        return False
    if a[0] % 2 == 0:
        res = a[0]
    else:
        res = a[1]
    for i in range(0,n):
        if a[i] % 2 == 1:
            if a[i] == 1: return False
            a[i] = a[i] - 1
        res = gcd(a[i],res)
    return not deal(n,list(map(lambda x: x//res,a)))

n = int(input())
a = readln(' ')
if deal(n,a):
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
from fractions import gcd
def solve(a):
    n = len(a)
    s = [(x + 1) & 1 for x in a]
    ss = sum(s)
    if ss == n:
        a[0] -= 1
    elif ss == n - 1:
        for i in xrange(n):
            if s[i] == 0 and a[i] > 1:
                a[i] -= 1
                break
        else:
            return ss & 1
    else:
        return ss & 1
    g = reduce(gcd, a)
    return not solve([x / g for x in a])

def main():
    n = int(raw_input())
    a = map(int, raw_input().split())
    print "First" if solve(a) else "Second"
main()

Submission status: Runtime Error

Solution code:
from math import gcd
n = int(input())
a = list(map(int,input().split()))
def gcds(ls):
  ret = 0
  for i in ls:
    ret = gcd(ret,i)
  return ret
def flg(ls):
  if (sum(ls)-len(ls))%2:
    ret = 1
  else:
    ret = 2
  return ret
if n%2 == 0:
  if sum(a)%2:
    print("Second")
  else:
    print("First")
else:
  cnt = 0
  while flg(a)%2 == 0:
    odd = 0
    oddidx = -1
    even = 0
    for i,x in enumerate(a):
      if x%2:
        odd += 1
        oddidx = i
      else:
        even += 1
    if odd == 1 and a[oddidx] > 1:
      a[oddidx] -= 1
      g = gcds(a)
      for i in range(n):
        a[i] //= g
      cnt += 1
    else:
      break
  if (flg(a)+cnt)%2 == 1:
    print("First")
  else:
    print("Second")

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
from functools import reduce
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def calc(A):
    N = len(A)
    K = sum(1 for a in A if a % 2 == 0)
    if K & 1:
        return True
    if N-1 != K:
        return False
    A = [a-a%2 for a in A]
    g = reduce(gcd, A)
    A = [a//g for a in A]
    return not calc(A)


N = int(readline())
A = list(map(int, readline().split()))
print('First' if calc(A) else 'Second')

Submission status: Runtime Error

Solution code:
#d
#the niumbers of evens is important
#the point is, there is no influence to odd/even if you divide them by odd numbers.
#You should do simulation only in the case where there is one odd over 3 and even numbers of even numbers

from math import gcd

def count(a):
    odd, even = 0,0
    for x in a:
        if x % 2 == 1: odd = odd + 1
        else: even = even + 1
    return odd,even

def deal(n,a):
    odd,even = count(a)
    if even == 0:
        return False
    if even % 2 == 1:
        return True
    if odd > 1:
        return False
    
    #the case where there is one odd (over 3) and even numbers of even numbers
    #calculate gcd by step by step
    g = 1
    for i in range(0,n):
        if a[i] % 2 == 1:
            if a[i] == 1: 
                return False
            a[i]  -= 1
        g = gcd(a[i], g)
    return not deal(n,list(map(lambda x: x//g,a)))

n = int(input())
a = [int(i) for i in input().split()]
if deal(n,a):
    print('First')
else:
    print('Second')

Submission status: Runtime Error

Solution code:
n = int(input())
x = list(map(int, input().split()))
j = 1
k=1
while j:
    s=0
    if 1 in x:
        s = sum(x)-n
        break
    for i in range(n):
        if x[i]%2 == 0:
            x[i]/=2
            s+=1
        else:
            x[i] = (x[i]-1)/2
    if s == n-1 and s%2==0):j = 1
    else:j=0
if s %2 != 0:
    print("First")
else:
    print("Second")

Submission status: Runtime Error

Solution code:
import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)

def score(A):
	return(sum(A)-len(A))

def Ifavor(A):
	return(score(A)%2==1)	

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	
def testmove(A,i):
	N=len(A)
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	if Ifavor(A):
		A=[x*g for x in A]
		A[i]+=1
		return(False)
	else:
		j=0
		while j<N:
			A[j]-=1
			h=gcdm(A)	
			if Ifavor([x//h for x in A])==False:
				A[j]+=1
				A=[x*g for x in A]
				A[i]+=1
				return(False)
			A[j]+=1
			j+=1
		A=[x*g for x in A]
		A[i]+=1	
		return(True)

N=int(input())
B=[int(x) for x in input().split()]

#inp=St.splitlines()
#N=int(inp[0])
#B=[int(x) for x in inp[1].split()]

if Ifavor(B):
	print('First')
else:
	maxply=sum(B)-N
	ply=1
	e=0
	while e<N:
		if testmove(B,e):
			break
		e+=1
			
	if e!=N:
		playmove(B,e)
		ply+=1

	if (ply%2==1)!=Ifavor(B):
		print('Second')
	else:
		print('First')