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: Wrong Answer

Solution code:
import fractions

def verify(seq):
    sm = sum(seq)
    print(all([fractions.gcd(2, sm-2) != 1 for s in seq]))

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

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

Submission status: Wrong Answer

Solution code:
import functools
import math
from itertools import combinations
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    ham = combinations(range(1, 30001), N)
    # for x in ham:
    #     if functools.reduce(math.gcd, x) == 1:
    #         for y in x:
    #             xx = list(x)
    #             xx.remove(y)
    #             if functools.reduce(math.gcd, [y, sum(xx)]) != 1:
    #                 break
    #         else:
    #             print(' '.join([str(i) for i in x]))
    #             return
    print(N)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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()

Submission status: Wrong Answer

Solution code:
import functools
import math
from itertools import combinations
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    print(N)
    # ham = combinations(range(1, 30001), N)
    # count = 0
    # for x in ham:
    #     if functools.reduce(math.gcd, x) == 1:
    #         for y in x:
    #             xx = list(x)
    #             xx.remove(y)
    #             if functools.reduce(math.gcd, [y, sum(xx)]) != 1:
    #                 break
    #         else:
    #             print(' '.join([str(i) for i in x]))
    #             return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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())
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)

Submission status: Wrong Answer

Solution code:
def ans(N):
    if N % 2 == 0:
        if N == 4:
            return "2 4 3 9"
        ret = [2, 4, 3, 9]
        cnt = 4
        summand = 6
        while summand <= 30000 - 6:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            if summand > 30000:
                return "over 30000"
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 15
        while summand <= 30000 - 6:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            if summand > 30000:
                return "over 30000"
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 8
        while summand <= 30000 - 2:
            ret.append(summand)
            cnt += 1
            summand += 2
            ret.append(summand)
            if summand > 30000:
                return "over 30000"
            cnt += 1
            summand += 4
            if cnt == N:
                return " ".join(list(map(str, ret)))
    else:
        if N == 3:
            return "2 5 63"
        ret = [2, 8, 14]
        cnt = 3
        summand = 3
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            # if summand > 30000:
            #     return "over 30000"
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 6
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            # if summand > 30000:
            #     return "over 30000"
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        # ret.append(4)
        # cnt += 1
        # if cnt == N:
        #     return " ".join(list(map(str, ret)))
        # ret.append(10)
        # cnt += 1
        # if cnt == N:
        #     return " ".join(list(map(str, ret)))
        # ret.append(16)
        # cnt += 1
        # if cnt == N:
        #     return " ".join(list(map(str, ret)))
        summand = 20
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 2
            ret.append(summand)
            # if summand > 30000:
            #     return "over 30000"
            cnt += 1
            summand += 4
            if cnt == N:
                return " ".join(list(map(str, ret)))


N = int(input())
print(ans(N))

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = [1]
total = 1
for n in range(30001):
    if (n%2 == 0) ^ (n%3 == 0):
        ans.append(n)
        total += n
    if len(ans) == N: break

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

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

print(*ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

import fractions

def check(l):
	l = list(map(int, l.split()))

	if max(l) >= 30001:
		return False
	tmp = l[0]

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

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

	return True


def main(n):
	if n == 3:
		return "2 5 63"
	if n <= 5003:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = "2 4 " + " ".join([str(x) for x in sub[0:(n-2)]])
			return(s)
		else:
			s = "2 4 6 " + " ".join([str(x) for x in sub[0:(n-3)]])
			return(s)
	else:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = " ".join([str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0][0:(n-5000)]) + " " +  " ".join([str(x) for x in sub])
			return(s)
		else:
			s = " ".join([str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0][0:(n-5001)]) + " 6 " +  " ".join([str(x) for x in sub])
			return(s)
if __name__ == '__main__':
	n = int(input())
	#print(check(main(n)))
	print(main(n))
	#print(check(main("2, 40001")))
	#for i in range(5001, 30000):
	#	print(i, check(main(i)))

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

import fractions

def check(l):
	l = list(map(int, l.split()))

	if max(l) >= 30001:
		return False
	tmp = l[0]

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

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

	return True


def main(n):
	if n == 3:
		return "2 5 63"
	if n <= 5003:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = "2 4 " + " ".join([str(x) for x in sub[0:(n-2)]])
			return(s)
		else:
			s = "2 4 6 " + " ".join([str(x) for x in sub[0:(n-3)]])
			return(s)
	else:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = " ".join([str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0][0:(n-5000)]) + " " +  " ".join([str(x) for x in sub])
			return(s)
		else:
			s = " ".join([str(i) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0][0:(n-5001)]) + " 6 " +  " ".join([str(x) for x in sub])
			return(s)
if __name__ == '__main__':
	n = int(input())
	print(check(main(n)))
	#for i in range(5001, 30000):
	#	print(i, check(main(i)))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n = int(raw_input())
a = []
x = 2
s = 0
for i in xrange(n - 1):
    for j in xrange(x, 30001):
        if j % 2 == 0 or j % 3 == 0 or j % 5 == 0 or j % 7 == 0:
            a.append(j)
            x = j + 1
            s += j
            break
for j in xrange(x, 30001):
    if (s + j) % 210 == 0 and gcd(s, j) != 1:
        a.append(j)
        break
for x in a:
    print x,

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n = int(raw_input())
a = []
x = 2
s = 0
for i in xrange(n - 1):
    for j in xrange(x, 30001):
        if j % 2 == 0 or j % 3 == 0:
            a.append(j)
            x = j + 1
            s += j
            break
for j in xrange(x, 30001):
    if (s + j) % 6 == 0 and gcd(s, j) != 1:
        a.append(j)
        break
for x in a:
    print x,

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n = int(raw_input())
a = []
x = 2
s = 0
for i in xrange(n - 1):
    for j in xrange(x, 30001):
        if j % 2 == 0 or j % 3 == 0 or j % 5 == 0:
            a.append(j)
            x = j + 1
            s += j
            break
for j in xrange(x, 30001):
    if (s + j) % 30 == 0 and gcd(s, j) != 1:
        a.append(j)
        break
for x in a:
    print x,

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

import fractions

def check(l):
	l = list(map(int, l.split()))
	tmp = l[0]
	for i in range(len(l) - 1):
		tmp = fractions.gcd(tmp, l[i+1])
	if tmp != 1:
		return(False)

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

	return(True)


def main(n):
	if n == 3:
		return "2 5 63"
	if n <= 5003:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = "2 4 " + " ".join([str(x) for x in sub[0:(n-2)]])
			return(s)
		else:
			s = "2 4 6 " + " ".join([str(x) for x in sub[0:(n-3)]])
			return(s)
	else:
		sub = [i * 3 for i in range(1, 10001) if i % 2 == 1]
		if n % 2 == 0:
			s = " ".join([str(i * 2) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0][0:(n-5000)]) + " " +  " ".join([str(x) for x in sub])
			return(s)
		else:
			s = " ".join([str(i * 2) for i in range(1, 30000) if i % 2 == 0 and i % 3 != 0][0:(n-5001)]) + " 6 " +  " ".join([str(x) for x in sub])
			return(s)
if __name__ == '__main__':
	n = int(input())
	print(main(n))

Submission status: Wrong Answer

Solution code:
N = int(input())
print(' '.join(['2','3','25'] + ['30']*(N-3)))

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = []
x = 2
s = 0
for i in xrange(n - 1):
    for j in xrange(x, 30001):
        if j % 2 == 0 or j % 3 == 0 or j % 5 == 0:
            a.append(j)
            x = j + 1
            s += j
            break
for j in xrange(x, 30001):
    if (s + j) % 30 == 0:
        a.append(j)
        break
for x in a:
    print x,

Submission status: Wrong Answer

Solution code:
def ans(N):
    if N % 2 == 0:
        if N == 4:
            return "2 4 3 9"
        ret = [2, 4, 3, 9]
        cnt = 4
        summand = 6
        while summand <= 30000 - 6:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 15
        while summand <= 30000 - 6:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 8
        while summand <= 30000 - 2:
            ret.append(summand)
            cnt += 1
            summand += 2
            ret.append(summand)
            cnt += 1
            summand += 4
            if cnt == N:
                return " ".join(list(map(str, ret)))
    else:
        if N == 3:
            return "2 5 63"
        ret = [2, 8, 14]
        cnt = 3
        summand = 3
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 6
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        ret.append(4)
        cnt += 1
        if cnt == N:
            return " ".join(list(map(str, ret)))
        ret.append(10)
        cnt += 1
        if cnt == N:
            return " ".join(list(map(str, ret)))
        ret.append(16)
        cnt += 1
        if cnt == N:
            return " ".join(list(map(str, ret)))
        summand = 20
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 2
            ret.append(summand)
            cnt += 1
            summand += 4
            if cnt == N:
                return " ".join(list(map(str, ret)))


N = int(input())
print(ans(N))

Submission status: Wrong Answer

Solution code:
def ans(N):
    ret = []
    cnt = 0
    if N % 2 == 0:
        summand = 6
        while summand <= 30000 - 6:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 3
        while summand <= 30000 - 6:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 2
        while summand <= 30000 - 2:
            ret.append(summand)
            cnt += 1
            summand += 2
            ret.append(summand)
            cnt += 1
            summand += 4
            if cnt == N:
                return " ".join(list(map(str, ret)))
    else:
        ret = [2, 4, 8]
        cnt = 3
        if N == 3:
            return " ".join(list(map(str, ret)))

        summand = 6
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 3
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 6
            ret.append(summand)
            cnt += 1
            summand += 6
            if cnt == N:
                return " ".join(list(map(str, ret)))
        summand = 10
        while summand < 30000:
            ret.append(summand)
            cnt += 1
            summand += 4
            ret.append(summand)
            cnt += 1
            summand += 2
            if cnt == N:
                return " ".join(list(map(str, ret)))


N = int(input())
print(ans(N))