Problem:


Score : 600 points

Problem Statement

Nagase is a top student in high school. One day, she's analyzing some properties of special sets of positive integers.  

She thinks that a set S = \{a_{1}, a_{2}, ..., a_{N}\} of distinct positive integers is called special if for all 1 \leq i \leq N, the gcd (greatest common divisor) of a_{i} and the sum of the remaining elements of S is not 1.

Nagase wants to find a special set of size N. However, this task is too easy, so she decided to ramp up the difficulty. Nagase challenges you to find a special set of size N such that the gcd of all elements are 1 and the elements of the set does not exceed 30000.

Constraints

3 \leq N \leq 20000

Input

Input is given from Standard Input in the following format:

N

Output

Output N space-separated integers, denoting the elements of the set S. S must satisfy the following conditions :

The elements must be distinct positive integers not exceeding 30000.

The gcd of all elements of S is 1, i.e. there does not exist an integer d > 1 that divides all elements of S.

S is a special set.

If there are multiple solutions, you may output any of them. The elements of S may be printed in any order. It is guaranteed that at least one solution exist under the given contraints.

Sample Input 1

3

Sample Output 1

2 5 63

\{2, 5, 63\} is special because gcd(2, 5 + 63) = 2, gcd(5, 2 + 63) = 5, gcd(63, 2 + 5) = 7. Also, gcd(2, 5, 63) = 1. Thus, this set satisfies all the criteria.

Note that \{2, 4, 6\} is not a valid solution because gcd(2, 4, 6) = 2 > 1.

Sample Input 2

4

Sample Output 2

2 5 20 63

\{2, 5, 20, 63\} is special because gcd(2, 5 + 20 + 63) = 2, gcd(5, 2 + 20 + 63) = 5, gcd(20, 2 + 5 + 63) = 10, gcd(63, 2 + 5 + 20) = 9. Also, gcd(2, 5, 20, 63) = 1. Thus, this set satisfies all the criteria.



Sample input:
3


Sample output:
2 5 63

Submission status: Accepted

Solution code:
n = int(input())
if n == 3:
    print("2 5 63")
elif n == 4:
    print("2 5 20 63")
elif n == 5:
    print("3 4 6 8 9")
elif n == 6:
    print("2 3 4 8 9 10")
elif n == 7:
    print("2 3 4 6 8 9 10")
else:
    ans = []
    for i in range(n // 8):
        ans += [12 * i + 2, 12 * i + 3, 12 * i + 4, 12 * i + 6, 12 * i + 8, 12 * i + 9, 12 * i + 10, 12 * i + 12]
    if n % 8 == 1:
        ans += [ans[-1] + 6]
    elif n % 8 == 2:
        ans += [ans[-1] + 4, ans[-1] + 8]
    elif n % 8 == 3:
        ans += [ans[-1] + 4, ans[-1] + 6, ans[-1] + 8]
    elif n % 8 == 4:
        ans += [ans[-1] + 2, ans[-1] + 4, ans[-1] + 8, ans[-1] + 10]
    elif n % 8 == 5:
        ans += [ans[-1] + 3, ans[-1] + 4, ans[-1] + 6, ans[-1] + 8, ans[-1] + 9]
    elif n % 8 == 6:
        ans += [ans[-1] + 2, ans[-1] + 3, ans[-1] + 4, ans[-1] + 8, ans[-1] + 9, ans[-1] + 10]
    elif n % 8 == 7:
        ans += [ans[-1] + 2, ans[-1] + 3, ans[-1] + 4, ans[-1] + 6, ans[-1] + 8, ans[-1] + 9, ans[-1] + 10]

    print(" ".join(list(map(str, ans))))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

ls = [n for n in range(2,30001) if n % 2 == 0 or n % 3 == 0]

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

def check(N, ans):
  assert len(ans) == len(set(ans)) == N
  S = sum(ans)
  assert reduce(gcd, ans) == 1
  assert all(gcd(S - a, a) != 1 for a in ans)

def solve(N):
  if N == 3:
    return [2, 5, 63]
  q, r = divmod(N, 8)
  t = q * 8
  ans = ls[:t]
  if r % 2 == 1:
    ans += [ls[t+3]]
  r //= 2
  if r == 1:
    ans += [ls[t], ls[t+2]]
  elif r == 2:
    ans += ls[t:t+3] + [ls[t+5]]
  elif r == 3:
    ans += ls[t:t+3] + ls[t+4:t+7]
  return ans

# for N in range(3, 100):
#   ans = solve(N)
#   print(N, ans, file=stderr)
#   check(N, ans)

N = read()
print(' '.join(str(a) for a in solve(N)))

Submission status: Accepted

Solution code:
N = int(input())

if N == 3:
    print('2\n3\n25')
    exit()

M = (N - 1) // 8
m2s = []
m3s = []
m6s = []
for i in range(1, (M + 1) * 12 + 1):
    if i % 6 == 0:
        m6s += [i]
    elif i % 3 == 0:
        m3s += [i]
    elif i % 2 == 0:
        m2s += [i]

im2 = 4 * M + [0, 2, 2, 2, 2, 4, 4, 4][(N - 1) % 8]
im3 = 2 * M + [0, 0, 0, 2, 2, 2, 2, 2][(N - 1) % 8]
im6 = 2 * M + [1, 0, 1, 0, 1, 0, 1, 2][(N - 1) % 8]

for i in m2s[:im2] + m3s[:im3] + m6s[:im6]:
    print(i)

Submission status: Accepted

Solution code:
N=int(input())

if N == 3:
    print("2 5 63")
    import sys
    sys.exit()
    
ans=[]
for i in range(3,30001):
  if len(ans)==N-1:
    break
  if i%2==0 or i%3==0 or i%5==0:
    ans.append(i)

s=sum(ans)

if s%2==1:
  ans[0]=2
  s=sum(ans)

ans.append(30000 - s%30)

print(*ans)

Submission status: Accepted

Solution code:
# seishin.py
N = int(input())
P = [2, 5, 63, 20, 30]
if N < 6:
    print(*P[:N])
    exit(0)

def gen():
    i = 0
    while 1:
        i += 1
        if i % 6 in [1, 5]:
            i += 1
        yield i
S = set()
s = 0
g = gen()
while len(S) < N:
    v = next(g)
    S.add(v)
    s += v
if s % 6 == 2:
    S.remove(8); s -= 8
    v = next(g)
    while v % 6 != 0:
        v = next(g)
    S.add(v); s += v
elif s % 6 == 3:
    S.remove(9); s -= 9
    v = next(g)
    while v % 6 != 0:
        v = next(g)
    S.add(v); s += v
elif s % 6 == 5:
    S.remove(9); s -= 9
    v = next(g)
    while v % 6 != 4:
        v = next(g)
    S.add(v); s += v
print(*S)

Submission status: Accepted

Solution code:
n = int(input())
h = 30000

if n == 3:
    print("2 5 63")
    exit()
if n == 4:
    print("2 5 20 63")
    exit()
if n == 5:
    print("2 5 20 30 63")
    exit()


pret = [2, 3, 4]
it_count = int(n/4) + 1
pret.extend([6*i for i in range(1, it_count)])
pret.extend( [6*i + 2 for i in range(1, it_count)])
pret.extend([6*i +3 for i in range(1, it_count)])
pret.extend(  [6*i + 4 for i in range(1, it_count)])

pret.sort()
ret = pret[:n]


sum_of_ret = sum(ret) % 6
if sum_of_ret == 2:
    ret.remove(8)
    ret.append(6* (it_count))
if sum_of_ret == 3:
    ret.remove(9)
    ret.append(6* (it_count))
if sum_of_ret == 5:
    ret.remove(9)
    if not 6* (it_count - 1) + 4 in ret:
        ret.append(6* (it_count - 1) + 4)
    else:
        ret.append(6* (it_count) + 4)


print(" ".join(list(map(str,ret))))

Submission status: Accepted

Solution code:
N = int(input())
even = [2, 4, 3, 9, 8, 10, 6, 12]
odd = [6, 2, 4, 3, 9, 8, 10, 12]

if N == 3:
    print(2, 5, 63)
    exit()
    
ans = []
if N % 2 == 0:
    for i in range(N):
        ans.append(even[i%8]+12*(i//8))
else:
    for i in range(N):
        ans.append(odd[i%8]+12*(i//8))
ans = list(map(str, ans))
print(" ".join(ans))

Submission status: Accepted

Solution code:
# import math
# from functools import reduce

# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

N = int(input())
if N <= 5:
    if N == 3: print('2 5 63')
    elif N == 4: print('2 5 20 63')
    elif N == 5: print('2 5 20 30 63')
else:
    flag = 0
    S = 0
    k = 0
    retList = list()
    Q = N // 4
    R = N % 4
    for q in range(Q):
        S += 4*6*q + 15
        retList.append(str(6*q+2))
        retList.append(str(6*q+3))
        retList.append(str(6*q+4))
        retList.append(str(6*q+6))
    if R == 0:
        pass
    elif R == 1:
        S += 6*Q + 2
        retList.append(str(6*Q + 2))
    elif R == 2:
        S += 2*6*Q + 5
        retList.append(str(6*Q + 2))
        retList.append(str(6*Q + 3))
    elif R == 3:
        S += 3*6*Q + 9
        retList.append(str(6*Q + 2))
        retList.append(str(6*Q + 3))
        retList.append(str(6*Q + 4))

    if S%6 == 0:
        pass
    elif S%6 == 2:
        retList.remove('8')
        S -= 8
        S += 6*(Q+1) + 6
        retList.append(str(6*Q + 6))
    elif S%6 == 3:
        retList.remove('9')
        S -= 9
        S += 6*(Q+1) + 6
        retList.append(str(6*Q + 6))
    elif S%6 == 5:
        retList.remove('9')
        S -= 9
        S += 6*(Q+1) + 4
        retList.append(str(6*Q + 4))
    # print(S%6)
    # print(len(retList))
    # retIntList = list(map(int, retList))
    # for a in retIntList:
    #     if gcd(S, a) <= 1:
    #         print(S)
    #         print(a)
    print(' '.join(retList))
    # print(gcd(*retIntList))

Submission status: Accepted

Solution code:
n = int(input())
k = n%8
t = n//8
if n == 3:
  print(*[2,5,63])
  quit()
ans = [[2,3,4,6,8,9,10,12],[6],[3,9],[3,6,9],[2,3,9,10],[2,3,6,9,10],[2,3,4,8,9,10],[2,3,4,6,8,9,10]][k]
if k == 0:
  for i in range(1,t):
    ans.append(i * 12 + 2)
    ans.append(i * 12 + 3)
    ans.append(i * 12 + 4)
    ans.append(i * 12 + 6)
    ans.append(i * 12 + 8)
    ans.append(i * 12 + 9)
    ans.append(i * 12 + 10)
    ans.append(i * 12 + 12)
else:
  for i in range(1,t+1):
    ans.append(i * 12 + 2)
    ans.append(i * 12 + 3)
    ans.append(i * 12 + 4)
    ans.append(i * 12 + 6)
    ans.append(i * 12 + 8)
    ans.append(i * 12 + 9)
    ans.append(i * 12 + 10)
    ans.append(i * 12 + 12)
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
ret=[2,3,4] if n>=6 else [2,5,63] if n==3 else [2,5,20,63] if n==4 else [2,5,20,30,63]
if n>=6:
    def getnext(a):
        if a%6==0:
            return a+2
        elif a%6==2:
            return a+1
        elif a%6==3:
            return a+1
        elif a%6==4:
            return a+2
    while len(ret)<n:
        ret.append(getnext(ret[-1]))
    if sum(ret)%6==5:
        ret[-1]=getnext(ret[-1])
    elif sum(ret)%6!=0:
        ret.remove((sum(ret)%6)+6)
        ret.append(getnext(ret[-1]))
        while sum(ret)%6!=0:
            ret[-1]=getnext(ret[-1])
print(" ".join(map(str,ret)))

Submission status: Accepted

Solution code:
n=int(input())-3
l=[2,3,25]
i=2
while n>=2:
  if i!=2 and i!=3 and i!=25 and(i%2==0 or i%3==0 or i%25==0):
    l.append(30000-i)
    l.append(i)
    n-=2
  i+=1
if n==1:
  l.append(30000)
print(*l)

Submission status: Accepted

Solution code:
a = []
b = []
c = []
ans = []
n = (int)(input())
for i in range(10,30001):
	if i % 2 != 0 and i % 3 == 0:
		a.append(i);
for i in range(10,30001):
	if i % 2 == 0 and i % 3 != 0:
		b.append(i);
for i in range(10,30001):
	if i % 6 == 0:
		c.append(i);
b.append(8)
if n >= 5:
	n -= 5
	ans = [2,4,3,9,6]
elif n == 4:
	n = 0
	ans = [2,5,20,63]
elif n == 3:
	n = 0
	ans = [2,5,63]
k = (int)(len(b) / 2)
for i in range(0,k):
	if n >= 2:
		ans.append(b[i * 2])
		ans.append(b[i * 2 + 1])
		n -= 2
k = (int)(len(a) / 2)
for i in range(0,k):
	if n >= 2:
		ans.append(a[i * 2])
		ans.append(a[i * 2 + 1])
		n -= 2
k = len(c)
for i in range(0,k):
	if n >= 1:
		ans.append(c[i])
		n -= 1
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())

if N == 3:
    ret = [2, 5, 63]
else:
    ret = []
    
    if N <= 15000:
        if N % 3 == 0:
            b = 4
        else:
            b = 2
        a = N - b
    else:
        a = 15000 - N%2
        b = N - a
        
    for i in range(1, a+1):
        ret.append(2*i)
    for i in range(b):
        ret.append(3*(2 * i + 1))
    assert len(ret) == N
print(' '.join([str(_) for _ in ret]))

Submission status: Accepted

Solution code:
from fractions import gcd

def check(A):
    g = reduce(gcd, A)
    if g != 1:
        return False
    s = sum(A)
    for a in A:
        if gcd(a, s - a) == 1:
            print a, s - a, gcd(a, s - a)

N = input()
M = 30000

if N == 3:
    print "2 5 63"
elif N == 4:
    print "2 5 20 63"
elif N == 5:
    print "2 3 4 9 12"
else:
    ans = [2, 4, 3, 9]
    a = 8
    b = 6
    c = 15
    while len(ans) < N:
        if N - len(ans) == 1:
            ans.append(b)
        elif a + 2 <= M:
            ans.append(a)
            ans.append(a+2)
            a += 6
        elif c + 6 <= M:
            ans.append(c)
            ans.append(c+6)
            c += 12
        else:
            ans.append(b)
            b += 6
    print ' '.join(map(str, ans))

Submission status: Accepted

Solution code:
N=input()

if N==3:
	print "2 5 63"
	quit()
elif N==4:
	print "2 5 20 63"
	quit()

#N>=5
#For 2 and 3
S=[2,3,4]
N-=3


x=N/4	# N=4x+b
b=N%4

for i in range(1,x+1):
	S.append(6*i)
	S.append(6*i+2)
	S.append(6*i+3)
	S.append(6*i+4)


if x%2==0:
	if b==0:
		S.remove(6*x+3)
		S.append(6*x+6)
	elif b==1:
		S.append(6*(x+1)+3)
	elif b==2:
		S.append(6*(x+1))
		S.append(6*(x+1)+3)
	elif b==3:
		S.append(6*(x+1))
		S.append(6*(x+1)+3)
		S.append(6*(x+1)+6)
else:
	if b==0:
		pass
	elif b==1:
		S.append(6*(x+1))
	elif b==2:
		S.append(6*(x+1)+2)
		S.append(6*(x+1)+4)
	elif b==3:
		S.append(6*(x+1))
		S.append(6*(x+1)+2)
		S.append(6*(x+1)+4)	

for i in S:
	print i,

Submission status: Accepted

Solution code:
N = int(input())
if N == 3:
    print('2 5 63')
    exit()

ans = []
total = 0
for n in range(1,30001):
    if n%2 == 0 or n%3 == 0:
        ans.append(n)
        total += n
    if len(ans) == N: break

if total%6 == 1:
    i = N - 1
    while ans[i]%3 > 0:
        i -= 1
    ans[i] += 3
    i = N - 1
    while ans[i]%2 > 0:
        i -= 1
    ans[i] += 2

elif total%6 == 2:
    i = N - 1
    while ans[i]%2 > 0:
        i -= 1
    ans[i] += 4

elif total%6 == 3:
    i = N - 1
    while ans[i]%3 > 0:
        i -= 1
    ans[i] += 3

elif total%6 == 4:
    i = N - 1
    while ans[i]%2 > 0:
        i -= 1
    ans[i] += 2

elif total%6 == 5:
    i = N - 1
    while ans[i]%3 > 0:
        i -= 1
    ans[i] += 3
    i = N - 1
    while ans[i]%2 > 0:
        i -= 1
    ans[i] += 4

print(*ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
 
if N == 3:
    print('2 5 63')
    sys.exit()
if N == 4:
    print('2 5 20 63')
    sys.exit()
 
if N == 5:
    print('2 3 6 4 9')
    sys.exit()
 
 
S = '2 3 6 4 9'
 
N -= 5
 
print(S, end='')
 
if N == 1:
    print(' 12')
    sys.exit()
 
for i in range(5001):
    
    Tmp1 = 6 * i + 8
    Tmp2 = 6 * i + 10
    if Tmp2 > 30000:
        break
    
    print(' %d %d' %(Tmp1, Tmp2) , end='')
    N -= 2
    if N == 0:
        print()
        sys.exit()
    elif N == 1:
        print(' 12')
        sys.exit()
        
for i in range(5001):
    
    Tmp1 = 12 * i + 15
    Tmp2 = 12 * i + 21
    if Tmp2 > 30000:
        break
    
    print(' %d %d' %(Tmp1, Tmp2), end='')
    N -= 2
    if N == 0:
        print()
        sys.exit()
    elif N == 1:
        print(' 12')
        sys.exit()   
 
for i in range(N):
    
    Tmp1 = 6 * (i + 2)
    if Tmp1 > 30000:
        break
    
    print(' %d' %(Tmp1) , end='')
 
 
print()

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

N = int(input())

if N == 3:
    print("2 5 63")
    import sys
    sys.exit()

A = []
for i in range(3, 30001):
    if len(A) == N - 1:
        break
    if i % 2 == 0 or i % 3 == 0 or i % 5 == 0:
        A.append(i)

s = sum(A)
if s % 2 == 1:
    A[0] = 2
s = sum(A)
    
l = 30000 - s % 30
A.append(l)
print(" ".join(str(n) for n in A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N = int(input())
if N == 3:
    print("2 5 63")
    exit()
elif N == 4:
    print("2 5 20 63")
    exit()
elif N == 5:
    print("7 1580 9438 11373 22962")
    exit()

numbers = []

for k in range(0, 5000):
    numbers.extend([6*k+2, 6*k+3, 6*k+4, 6*k+6])

ans = numbers[:N]
S = sum(ans)


if S%6 == 0:
    pass
elif S%6 == 2:
    del ans[4]
    ans.append((ans[-1]//6 + 1)*6)
elif S%6 == 3:
    del ans[5]
    ans.append((ans[-1]//6 + 1)*6)
else:
    x, y = (ans[-1]//6)*6+4, (ans[-1]//6)*6+10
    ans.append(x if x > ans[-1] else y)
    del ans[5]
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
l = N // 4
ans = []

if N == 3:
	print("2 5 63")
	exit(0)
elif N == 4:
	print("2 5 20 63")
	exit(0)
elif N == 5:
	print("6 8 9 10 15")
	exit(0)
elif N == 6:
	print("6 8 9 10 12 15")
	exit(0)

for i in range(l):
	ans.extend([6*i+2,6*i+3,6*i+4,6*i+6])

add = [6*(l)+2,6*(l)+3,6*(l)+4,6*(l+1)]
ans.extend(add[:N%4])
s = sum(ans)
flg = s % 6

if flg == 1:
	cor = 2 - (ans[-1]%6)
	if cor <= 0:
		cor += 6
	ans[1] = ans[-1] + cor

elif flg == 2:
	ans[0] = ans[-1] - (ans[-1]%6) + 6
elif flg == 3:
	ans[1] = ans[-1] - (ans[-1]%6) + 6
elif flg == 4:
	ans[2] = ans[-1] - (ans[-1]%6) + 6
elif flg == 5:
	cor = 4 - (ans[-1]%6)
	if cor <= 0:
		cor += 6
	ans[1] = ans[-1] + cor

print(*ans,end=' ')

Submission status: Accepted

Solution code:
n = int(input())
cnt = 0
ans = []
if n == 3:
    print('2 5 63')
else:
    for i in range(2, 30001):
        if cnt == n - 2:
            break
        if i % 2 == 0 or i % 3 == 0 or i % 5 == 0:
            ans.append(i)
            cnt += 1

    sm = sum(ans)
    for j in range(i+1, 30001):
        for k in range(j+1, 30001):
            if (sm + j + k) % (2*3*5) == 0 and\
               (j % 2 == 0 or j % 3 == 0 or j % 5 == 0) and\
               (k % 2 == 0 or k % 3 == 0 or k % 5 == 0):
                ans.append(j)
                ans.append(k)
                break
        else:
            continue
        break
    print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
N = int(input())

if N == 3:
    print("2 5 63")
    exit()

MAX = 30000
v2, v3, v6 = [], [], []

for x in range(2, MAX+1):
    if x%6 == 0:
        v6.append(x)
    elif x%3 == 0:
        v3.append(x)
    elif x%2 == 0:
        v2.append(x)

ans = []
j = 0

while j < len(v2)//2 and N > 3:
    ans.append(v2[j*2])
    ans.append(v2[j*2+1])
    j += 1
    N -= 2

j = 0
while j < len(v3)//2 and N > 1:
    ans.append(v3[j*2])
    ans.append(v3[j*2+1])
    j += 1
    N -= 2

for j in range(N):
    ans.append(v6[j])


print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
from sys import stdin 
a = []
b = []
c = [] 
d = []
cur = 2
hi = 30000
while cur <= hi:
    a.append(cur)
    cur = cur + 2 
cur = 3
while cur <= hi:
    b.append(cur)
    cur = cur + 6 
cur = 3
ans = [2,5,63]
cur = 630
while cur <=hi:
    ans.append(cur)
    cur = cur + 630
c = [] 
d = [] 
cur = 3
while cur <= hi:
    c.append(cur)
    cur = cur + 3 
cur = 2 
while cur <= hi:
    d.append(cur)
    d.append(cur+2)
    cur += 6 
n = int(stdin.readline())
if n <= 10:
    ans = ans[:n]
else:
    if n!=19999:
        for x in xrange(1,len(a)+1):
            y = n - x 
            if x > 0 and y > 0 and x <= len(a) and y <= len(b) and x%3==0 and y%2==0:
                break 
        ans = a[:x] + b[:y]
    else:
        for x in xrange(1,len(d)+1):
            y = n - x 
            if x > 0 and y > 0 and x <= len(d) and y <= len(c) and x%3==0 and y%2==0:
                break 
        ans = c[:x] + d[:y]
for i in ans:
    print i,

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    if n == 3:
        return '2 5 63'
    if n == 4:
        return '2 5 20 63'
    a = []
    c = 1
    for i in range(n):
        while c%2 > 0 and c%3 > 0 and c%5 > 0:
            c += 1
        a.append(c)
        c += 1
    a[-3] += 30 - (a[-3] % 30)
    a[-2] += 120 - (a[-2] % 30)
    a[-1] += 180 - (a[-1] % 30)
    t = sum(a)
    while t % 2 == 1:
        a[-3] += 3
        t += 3
    while t % 3 > 0:
        a[-2] += 10
        t += 10
    while t % 5 > 0:
        a[-1] += 6
        t += 6

    return ' '.join(map(str, a))


print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    if N == 3:
        ans = [2, 5, 63]
    else:
        ans = []
        apnd = ans.append
        n = -(-N // 8)
        if N % 2:
            num = (6, 2, 10, 3, 9, 4, 8, 12)
        else:
            num = (2, 10, 3, 9, 4, 8, 6, 12)
        for i in range(n):
            for j in num:
                apnd(j + 12 * i)
                N -= 1
                if not N:
                    break

    print(*ans, sep=' ')

main()

Submission status: Accepted

Solution code:
import sys
N = int(input())

if N == 3:
    print('2 5 63')
    sys.exit()
if N == 4:
    print('2 5 20 63')
    sys.exit()

if N == 5:
    print('2 3 6 4 9')
    sys.exit()

if N == 20000:
    for i in range(5000):
        Tmp1 = 6 * i + 2
        Tmp2 = 6 * i + 3
        Tmp3 = 6 * i + 4
        Tmp4 = 6 * (i + 1)
        print('%d %d %d %d' %(Tmp1,Tmp2,Tmp3,Tmp4), end='')
        if Tmp4 == 30000:
            break
        else:
            print(' ', end='')
    
    print()
    sys.exit()


S = '2 3 6 4 9'

N -= 5

print(S, end='')

if N == 1:
    print(' 12')
    sys.exit()

for i in range(5001):
    
    Tmp1 = 6 * i + 8
    Tmp2 = 6 * i + 10
    if Tmp2 > 30000:
        break
    
    print(' %d %d' %(Tmp1, Tmp2) , end='')
    N -= 2
    if N == 0:
        print()
        sys.exit()
    elif N == 1:
        print(' 12')
        sys.exit()
        
for i in range(5001):
    
    Tmp1 = 12 * i + 15
    Tmp2 = 12 * i + 21
    if Tmp2 > 30000:
        break
    
    print(' %d %d' %(Tmp1, Tmp2), end='')
    N -= 2
    if N == 0:
        print()
        sys.exit()
    elif N == 1:
        print(' 12')
        sys.exit()   

for i in range(N):
    
    Tmp1 = 6 * (i + 3)
    if Tmp1 > 30000:
        break
    
    print(' %d' %(Tmp1) , end='')


print()

Submission status: Accepted

Solution code:
N = int(input())
if N < 5002:
    if N % 2  == 0:
        sans = [6 * i  + 3 for i in range(N-2)]
        ans = sans + [2,4]
    if N % 2 == 1:
        sans = [6 * i  + 3 for i in range(N-3)]
        ans = sans + [2,4,6]
    if N == 3:
        ans = [2,3,25]
else:
    sans = [6 * i  + 3 for i in range(5000)]
    nis = [2 * i + 2 for i in range(N - 5000 )]
    if (len(nis) * (nis[0] + nis[-1]) //2) % 3 == 1:
        nis[-1] += 2
    elif    (len(nis) * (nis[0] + nis[-1]) //2) % 3 == 2:
        nis[-1] += 2
        nis[-2] += 2
    ans = sans + nis
ans = map(str,ans)
print(" ".join(ans))

Submission status: Accepted

Solution code:
# encoding:utf-8

import fractions

def check(l):
	l = list(map(int, l.split()))
	print(len(l), len([x for x in l if x % 2 == 0]), len([x for x in l if x % 2 == 1]))
	if max(l) >= 30001:
		print("max >= 30001")
		return False

	if len(set(l)) != len(l):
		print("not unique")
		return False

	tmp = l[0]


	for i in range(len(l) - 1):
		tmp = fractions.gcd(tmp, l[i+1])
	if tmp != 1:
		print("gcd is 1")
		return False 

	for i in range(len(l)):
		if fractions.gcd(l[i], sum(l) - l[i]) == 1:
			print("not special")
			return False

	return True


def main(n):
	if n == 3:
		return "2 5 63"

	sub1 = [str(i * 3) for i in range(1, 10001) if i % 2 == 1]
	sub2 = [str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0]
	sub3 = [str(i) for i in range(1, 30001) if i % 6 == 0]
	if n <= 5003:
		if n % 2 == 0:
			s = "2 4 " + " ".join([str(x) for x in sub1[0:(n-2)]])
			return(s)
		else:
			s = "2 4 6 " + " ".join([str(x) for x in sub1[0:(n-3)]])
			return(s)
	elif n <= 15000:
		if n % 2 == 0:
			s = " ".join(sub2[0:(n-5000)]) + " " +  " ".join(sub1)
			return(s)
		else:
			s = " ".join(sub2[0:(n-5001)]) + " 6 " +  " ".join(sub1)
			return(s)
	else:
		s = " ".join(sub2) + " " +  " ".join(sub1) + " " + " ".join(sub3[0:(n-15000)]) 
		return(s)

if __name__ == '__main__':
	n = int(input())
	#print(check(main(n)))
	#print(check(main(15)))
	#print(check(main(17)))
	#print(check(main(5002)))
	#print(check(main(5003)))
	#print(check(main(15002)))
	#print(check(main(15003)))
	print(main(n))
	#print(check("2 4 3 20001"))
	#for i in range(5001, 5006):
	#	ans = main(i)
	#	print(i, check(ans))

Submission status: Accepted

Solution code:
def _agc022_b(N):
    if N >= 4:
        S = []
        a = N // 8

        l = [2, 3, 4, 6, 8, 9, 10, 12]

        for i in range(a):
            for v in l:
                S.append(i * 12 + v)

        b = N % 8
        if b == 1:
            l = [6]
        elif b == 2:
            l = [6, 12]
        elif b == 3:
            l = [3, 6, 9]
        elif b == 4:
            l = [3, 4, 8, 9]
        elif b == 5:
            l = [2, 3, 6, 9, 10]
        elif b == 6:
            l = [2, 3, 4, 8, 9, 10]
        elif b == 7:
            l = [2, 3, 4, 6, 8, 9, 10]
        elif b == 0:
            l = []

        for v in l:
            S.append(a * 12 + v)
        print(' '.join(map(str, S)))
    elif N == 3:
        print('2 5 63')

N = int(input())
_agc022_b(N)

Submission status: Accepted

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

import array
from bisect import *
from collections import *
from fractions import *
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())

def is_valid(arr):
    size = len(arr)
    sumarr = sum(arr)
    if max(arr) > 30000:
        return False

    gcd_of_all = gcd(arr[0], arr[1])
    for i in range(2, size):
        gcd_of_all = gcd(gcd_of_all, arr[i])
    if gcd_of_all != 1:
        return False

    for i in range(size):
        n1 = arr[i]
        n2 = sumarr - n1
        if gcd(n1, n2) == 1:
            return False
    return True

def brute_force(SIZE):
    MAX = 50
    for comb in combinations(list(range(1,MAX+1)), SIZE):
        if is_valid(list(comb)):
            return list(comb)

# N = 41で死ぬ
def solve(N):
    if N <= 4:
        ans = brute_force(N)
    else:
        ans = [2, 3, 4, 5]
        cand = 6
        sumans = sum(ans)
        while (len(ans) < N - 1):
            if not (cand % 2 == 0 or cand % 3 == 0 or cand % 5 == 0):
                cand += 1
                continue
            if len(ans) == N - 2:
                if (sumans + cand) % 2 == 1:
                    cand += 1
                    continue
            ans.append(cand)
            sumans += cand
            cand += 1

        ans.append(cand)
        while True:
            if is_valid(ans): break
            else: ans[-1] += 1
    # assert(is_valid(ans))
    return ans

print(*solve(N))

# # for debug
# for N in range(3, 20001):
#     ans = solve(N)
#     print("N {}: ok".format(N))
#     is_valid(ans)

# arr = list(range(1, 6000))
# while True:
#     random.shuffle(arr)
#     arr2 = arr[:3000]
#     if is_valid(arr2):
#         print("valid!", arr2)
#     else:
#         print("not valid")
    


# for a in range(1, MAX):
#     for b in range(a+1, MAX):
#         for c in range(b+1, MAX):
#             numset = [a,b,c]
#             if is_valid(numset):
#                 print(numset)

Submission status: Accepted

Solution code:
def suit(n):
    if n%2==0 or n%3==0 or n%5==0:
        return True
    else:
        return False
N=int(input())
if N==3:
    print(2,3,25)
else:
    M=N//2
    a=[]
    k=0
    for i in range(1,15000):
        if suit(i):
            a.append(i)
            a.append(30000-i)
            k+=1
            if k==M:
                break
    if N%2==1:
        a.append(30000)

    st=""
    for p in a:
        st+=str(p)+" "
    print(st)