Problem:

問題５

　Ｊ中学校の運動会で次のようなクラス対抗の競技を行なうことになった． 
各クラスから生徒代表の男女 n ペア

     　　 (男子生徒 b1， 女子生徒 g1)， (男子生徒 b2， 女子生徒 g2)， … ， (男子生徒 bn， 女子生徒 gn)

を選び，
0 から 9 までの数字が書かれた旗を自由に選んでもらい 
（それぞれの旗は十分な個数ある）， 
横一列に並んでもらう． 
ただし， 
ペアになっている男子生徒と女子生徒は同じ番号の旗を一人１つずつ 
選ばなければならず，
 並び順は

     　　 b1 b2 … bn c gn … g2 g1

のように，
男子生徒達 n 人の並び順 
b1 b2 … bn とは逆の順番 
gn … g2 g1 で女子生徒達は
並ばなければならない． 
中央の c には， 
クラス担任の先生があらかじめ審判長によって指定された
番号の付いた旗を持って立つ場合と， 
立たないことを審判長に指定される場合とがある．

 
　こうして並んだ生徒達（と先生）が持った旗の番号
を 2n 桁（または 2n+1 桁）の整数と考えたとき， 
それが素数である方が勝ちである． 
ただし， 
両クラスとも素数だった場合あるいは両クラスとも素数でなかった場合には， 
数が大きい方が勝ちである． また，

　　 

      0 b2 … bn c gn … g2 0
 　あるいは　 
0 b2 … bn gn … g2 0

のように先頭に 0 が来るものは， 
普通使われる数の表し方ではないので禁止されている．

　Ｊ中学校の生徒であるあなたは， 
自分のクラスが勝つためにはどのように並ぶのがよいかを 
考えなければならない．

　入力ファイルの１行目に正整数 n と
１桁の整数 c（先生が持つ旗の番号）が
１つの半角空白文字で区切られて書かれている． 
c<0 のときは，
先生が中央に立たないことを表わす．

与えられる入力は 1≦n≦10 である．

　負けない並び方の順番 

　　 

     b1 b2 … bn c gn … g2 g1 
　または　 
b1 b2 … bn gn … g2 g1

を出力せよ．

出力ファイルにおいては，
出力の最後にも改行コードを入れること．

入出力例

  
入力例１

  
1 0

  
出力例１

  
101

  
入力例２

  
1 5

  
出力例２

  
757

  
入力例３

  
3 7

  
出力例３

  
9957599

  
  
入力例４

  
1 -1

  
  
出力例４

  
11

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
1 0


Sample output:
101

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0586

"""
import sys
from sys import stdin
import random
from itertools import product
input = stdin.readline


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def solve(n, c):
    if c >= 0:
        ans = int('9'*n + str(c) + '9'*n)
    else:
        ans = int('9'*n + '9'*n)

    # https://www.ioi-jp.org/joi/2005/2006-m1-prob_and_sol/2006-m1-t5-review.html
    if n > 4:
        return ans

    for p in product('9876543210', repeat=n):
        if p[0] == '0':
            continue
        t = ''.join(p)
        if c >= 0:
            ans = int(t + str(c) + t[::-1])
        else:
            ans = int(t + t[::-1])
        if is_prime(ans):
            break
    return ans


def main(args):
    n, c = map(int, input().split())
    result = solve(n, c)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
def f():
 n,c=map(int,input().split())
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)*(c>=0)+t[::-1])
     if 2 in[a,pow(2,a,a)]:return a
  else:
   a=int(h+str(c)*(c>=0)+h)
   if 2 in[a,pow(2,a,a)]:return a
print(f())

Submission status: Wrong Answer

Solution code:
n , c = map(int, input().split())
def prime(a):
    if a == 1: return 1
    i = 3
    while i <= a / i:
        if a % i == 0:
            return 0
        i += 2
    return 1
if c < 0:
    c = []
else:
    c = [str(c)]
for i in range(10**(n-1),10**n):
    num = int("".join(list(str(i)) + c + list(str(i))[::-1]))
    if prime(num):
        print(num)
        break
else:
    print(num)

Submission status: Wrong Answer

Solution code:
def Sosu(a):
        if a != 2 and a % 2 == 0:
                return 2
        if a != 3 and a % 3 == 0:
                return 3
        y = 0
        for x in xrange(4,int(a**0.5)+1):
                if a%x == 0:
                        print(a)
                        return 1
        else:
                return 0

Inp = map(int,raw_input().split())
From = int("9"*Inp[0])
To = int("1"+"0"*(Inp[0]-1))-1
for x in xrange(From,To,-1):
        if Inp[1] < 0:
                a = int(str(x)+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
        else:
                a = int(str(x)+str(Inp[1])+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
else:
        if Inp[1] < 0:
                print("9"*Inp[0]*2)
        else:
                print("9"*Inp[0]+str(Inp[1])+"9"*Inp[0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0586

"""
import sys
from sys import stdin
from itertools import product
input = stdin.readline


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True


def solve(n, c):
    if c >= 0:
        dummy = int('9'*n + str(c) + '9'*n)
    else:
        dummy = int('9'*n + '9'*n)

    # https://www.ioi-jp.org/joi/2005/2006-m1-prob_and_sol/2006-m1-t5-review.html
    if n > 4:
        return dummy

    found = False
    ans = -1
    for p in product('9876543210', repeat=n):
        if p[0] == '0':
            continue
        t = ''.join(p)
        if c >= 0:
            ans = int(t + str(c) + t[::-1])
        else:
            ans = int(t + t[::-1])
        if is_prime(ans):
            found = True
            break

    if found:
        return ans
    else:
        return dummy


def main(args):
    n, c = map(int, input().split())
    result = solve(n, c)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def p(x):
 if 2 in[x,pow(2,x,x)]:
  for i in range(7,int(x**.5+1),2):
   if x%i==0:return 0
  else:return 1
def f():
 n,c=map(int,input().split())
 if c<0:return(11,'9'*n*2)[n>1]
 for h in'9731':
  if n-1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)+t[::-1])
     if p(a):return a
  else:
   a=int(h+str(c)+h)
   if p(a):return a
 return'9'*n+b+'9'*n
print(f())

Submission status: Accepted

Solution code:
def p(x):
 for i in range(7,int(x**.5+1),2):
  if x%i==0:return 0
 else:return 1
def f():
 n,c=map(int,input().split())
 s='9'*n
 if c<0:return(11,s+s)[n>1]
 for h in'9731':
  if n-1:
   for m in range(int(10**~-n),0,-1):
    if((int(h)+m-1)*2+c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)+t[::-1])
     if p(a):return a
  else:
   a=int(h+str(c)+h)
   if p(a):return a
 return s+b+s
print(f())

Submission status: Accepted

Solution code:
def p(x):
 for i in range(7,int(x**.5+1),2):
  if x%i==0:return 0
 else:return 1
def f():
 n,c=map(int,input().split());s='9'*n
 if c<0:return(11,s+s)[n>1]
 for h in'9731':
  if n-1:
   for m in range(int(10**~-n),0,-1):
    if((int(h)+sum(int(k)for k in str(m-1)))*2+c)%3:
     t=h+str(m-1).zfill(n-1);a=int(t+str(c)+t[::-1])
     if p(a):return a
  else:
   a=int(h+str(c)+h)
   if p(a):return a
 return s+b+s
print(f())

Submission status: Accepted

Solution code:
def p(x):
 for i in range(7,int(x**.5+1),2):
  if x%i==0:return 0
 else:return 1
def f():
 n,c=map(int,input().split());s='9'*n
 if c<0:return(11,s+s)[n>1]
 for h in'9731':
  if n-1:
   for m in range(int(10**~-n),0,-1):
    m=str(m-1)
    if(sum(int(k)for k in h+m)*2+c)%3:
     t=h+m.zfill(n-1);a=int(t+str(c)+t[::-1])
     if p(a):return a
  else:
   a=int(h+str(c)+h)
   if p(a):return a
 return s+b+s
print(f())

Submission status: Accepted

Solution code:
def p(x):
 for i in range(7,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
def f():
 n,c=map(int,input().split());s='9'*n
 if c<0:return(11,s+s)[n>1]
 for h in'9731':
  if n-1:
   for m in range(int(10**~-n),0,-1):
    m=str(m-1)
    if(sum(int(k)for k in h+m)*2+c)%3:
     t=h+m.zfill(n-1);a=int(t+str(c)+t[::-1])
     if p(a):return a
  else:
   a=int(h+str(c)+h)
   if p(a):return a
print(f())

Submission status: Accepted

Solution code:
def p(x):
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
def f():
 n,c=map(int,input().split())
 s='9'*n
 if c<0:return(11,s+s)[n>1]
 for h in'9731':
  if n-1:
   for m in range(int(10**~-n),0,-1):
    t=h+str(m-1).zfill(n-1)
    a=int(t+str(c)+t[::-1])
    if p(a):return a
  else:
   a=int(h+str(c)+h)
   if p(a):return a
 return s+str(c)+s
print(f())

Submission status: Accepted

Solution code:
# AOJ 0586: Palindrome
# Python3 2018.6.30 bal4u

def palindrome(k, c):
	a = 10*k + c;
	while k:
		a = 10*a + (k%10)
		k //= 10
	return a

def isPrime(p):
	if (p & 1) == 0: return False
	for i in range(3, int(p**0.5), 2):
		if (p % i) == 0: return False
	return True

n, c = map(int, input().split())
if c < 0:
	if n == 1: print(11)
	else: print('9'*(2*n))
else:
	k = int('9'*n)+1
	while True:
		k -= 1
		x = palindrome(k, c)
		if isPrime(x):
			print(x)
			break

Submission status: Accepted

Solution code:
# AOJ 0586: Palindrome
# Python3 2018.6.30 bal4u

def palindrome(k, c):
	a = 10*k + c;
	while k:
		a = 10*a + (k % 10)
		k //= 10
	return a

def isPrime(p):
	if (p & 1) == 0: return False
	for i in range(3, 1+int(p**0.5), 2):
		if (p % i) == 0: return False
	return True

n, c = map(int, input().split())
if c < 0: print('9'*(2*n) if n > 1 else '11')
else:
	k = int('9'*n)+1
	while True:
		k -= 1
		x = palindrome(k, c)
		if isPrime(x):
			print(x)
			break

Submission status: Accepted

Solution code:
import math
import random
import sys

def gcd(a,b):
    if a==b:
        return a
    if a>b:
        return gcd(b,a)
    if b%a==0:
        return a
    return gcd(b%a,a)

def rabin(n):
##    print(n)
    for t in range(100):
        x=random.randint(2,n-1)
       ## print(x)
        if gcd(n,x)!=1:
            return False
        if pow(x,n-1,n)!=1:
            return False
            
    return True



def main():

    x,y = map(int,input().split())
    if y<0:
        if x==1:
            print(11)
        else:
            for _ in range(2*x):
                print(9,end='')
            print()
        return
    
    r=10**x
    r-=1
    rr=10**(x-1)-1
    while r!=rr:
        s=str(r)
        c=str(y)
        t=s[::-1]
        
        w=int(s+c+t)
        
        if rabin(w):
            print(w)
            return
        r=r-1
##    print("nasi")
    for _ in range(x):
        print(9,end='')
    print(y,end='')
    
    for _ in range(x):
        print(9,end='')
    print()
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def f():
 n,c=map(int,input().split())
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)*(c>=0)+t[::-1])
     for i in range(3,int(x**.5+1),2):
      if x%i==0:break
     else:return a
  else:
   a=int(h+str(c)*(c>=0)+h)
   for i in range(3,int(x**.5+1),2):
    if x%i==0:break
   else:return a
 return'9'*n+str(c)*(c>=0)+'9'*n
print(f())

Submission status: Runtime Error

Solution code:
def f():
 n,c=map(int,input().split())
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)*(c>=0)+t[::-1])
     for i in range(3,int(a**.5+1),2):
      if a%i==0:break
     else:return a
  else:
   a=int(h+str(c)*(c>=0)+h)
   for i in range(3,int(a**.5+1),2):
    if a%i==0:break
   else:return a
 return'9'*n+str(c)*(c>=0)+'9'*n
print(f())

Submission status: Runtime Error

Solution code:
def f():
 n,c=map(int,input().split())
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)*(c>=0)+t[::-1])
     if 2 in[x,pow(2,x,x)]:
      for i in range(3,int(a**.5+1),2):
       if a%i==0:break
      else:return a
  else:
   a=int(h+str(c)*(c>=0)+h)
   if 2 in[x,pow(2,x,x)]:
    for i in range(3,int(a**.5+1),2):
     if a%i==0:break
    else:return a
 return'9'*n+str(c)*(c>=0)+'9'*n
print(f())

Submission status: Runtime Error

Solution code:
def f():
 n,c=map(int,input().split())
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+str(c)*(c>=0)+t[::-1])
     if 2 in[a,pow(2,a,a)]:
      for i in range(3,int(a**.5+1),2):
       if a%i==0:break
      else:return a
  else:
   a=int(h+str(c)*(c>=0)+h)
   if 2 in[a,pow(2,a,a)]:
    for i in range(3,int(a**.5+1),2):
     if a%i==0:break
    else:return a
 return'9'*n+str(c)*(c>=0)+'9'*n
print(f())

Submission status: Runtime Error

Solution code:
def p(x):
 if 2 in[a,pow(2,a,a)]:
  for i in range(3,int(a**.5+1),2):
   if a%i==0:return 0
  else:return 1
def f():
 n,c=map(int,input().split())
 b=str(c)*(c>=0)
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+b+t[::-1])
     if p(a):return a
  else:
   a=int(h+b+h)
   if p(a):return a
 return'9'*n+b+'9'*n
print(f())

Submission status: Runtime Error

Solution code:
def p(x):
 if 2 in[x,pow(2,x,x)]:
  for i in range(3,int(x**.5+1),2):
   if x%i==0:return 0
  else:return 1
def f():
 n,c=map(int,input().split())
 b=str(c)*(c>=0)
 for h in'9731':
  if n>1:
   for m in range(int(10**(n-1)),0,-1):
    if((int(h)+m-1)*2+(c>=0)*c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+b+t[::-1])
     if p(a):return a
  else:
   a=int(h+b+h)
   if p(a):return a
 return'9'*n+b+'9'*n
print(f())

Submission status: Runtime Error

Solution code:
def p(x):
 for i in range(7,int(x**.5+1),2):
  if x%i==0:return 0
 else:return 1
def f():
 n,c=map(int,input().split())
 s='9'*n
 if c<0:return(11,s+s)[n>1]
 c=str(c)
 for h in'9731':
  if n-1:
   for m in range(int(10**~-n),0,-1):
    if((int(h)+m-1)*2+c)%3:
     t=h+str(m-1).zfill(n-1)
     a=int(t+c+t[::-1])
     if p(a):return a
  else:
   a=int(h+c+h)
   if p(a):return a
 return s+b+s
print(f())

Submission status: Runtime Error

Solution code:
n , c = map(int, input().split())
def prime(a):
    if a == 1: return 1
    i = 3
    while i <= a / i:
        if a % i == 0:
            return 0
        i += 2
    return 1
if c < 0:
    c = []
else:
    c = [str(c)]
for i in range(10**(n-1),10**n)[::-1]:
    num = int("".join(list(str(i)) + c + list(str(i))[::-1]))
    if prime(num):
        print(num)
        break
else:
    print("".join(["9"] * n + c + ["9"] * n))

Submission status: Runtime Error

Solution code:
def Sosu(a):
        if a != 2 and a % 2 == 0:
                return 2
        y = 0
        for x in range(int(a**0.5)+1):
                if (a/(x+1.0))%1 == 0:
                        y += 1
        if y == 1:
                return 0
        else:
                return 1

Inp = list(map(int,input().split()))
From = int("9"*Inp[0])
To = int("1"+"0"*(Inp[0]-1))-1
for x in range(From,To,-1):
        if Inp[1] < 0:
                a = int(str(x)+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
        else:
                a = int(str(x)+str(Inp[1])+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
else:
        if Inp[1] < 0:
                print("9"*Inp[0]*2)
        else:
                print("9"*Inp[0]+str(Inp[1])+"9"*Inp[0])

Submission status: Runtime Error

Solution code:
def Sosu(a):
        if a != 2 and a % 2 == 0:
                return 2
        y = 0
        for x in range(int(a**0.5)+1):
                if (a/(x+1.0))%1 == 0:
                        y += 1
        if y == 1:
                return 0
        else:
                return 1
 
Inp = map(int,raw_input().split())
From = int("9"*Inp[0])
To = int("1"+"0"*(Inp[0]-1))-1
for x in range(From,To,-1):
        if Inp[1] < 0:
                a = int(str(x)+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
        else:
                a = int(str(x)+str(Inp[1])+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
else:
        if Inp[1] < 0:
                print("9"*Inp[0]*2)
        else:
                print("9"*Inp[0]+str(Inp[1])+"9"*Inp[0])

Submission status: Runtime Error

Solution code:
def Sosu(a):
        if a != 2 and a % 2 == 0:
                return 2
        y = 0
        for x in xrange(int(a**0.5)+1):
                if (a/(x+1.0))%1 == 0:
                        y += 1
        if y == 1:
                return 0
        else:
                return 1
  
Inp = map(int,raw_input().split())
From = int("9"*Inp[0])
To = int("1"+"0"*(Inp[0]-1))-1
for x in xrange(From,To,-1):
        if Inp[1] < 0:
                a = int(str(x)+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
        else:
                a = int(str(x)+str(Inp[1])+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
else:
        if Inp[1] < 0:
                print("9"*Inp[0]*2)
        else:
                print("9"*Inp[0]+str(Inp[1])+"9"*Inp[0])

Submission status: Runtime Error

Solution code:
def Sosu(a):
        if a != 2 and a % 2 == 0:
                return 2
        if a != 3 and a % 3 == 0:
                return 3
        y = 0
        for x in xrange(4,int(a**0.5)+1):
                if a%x == 0:
                        return 1
        else:
                return 0

Inp = map(int,raw_input().split())
From = int("9"*Inp[0])
To = int("1"+"0"*(Inp[0]-1))-1
for x in xrange(From,To,-1):
        if Inp[1] < 0:
                a = int(str(x)+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
        else:
                a = int(str(x)+str(Inp[1])+str(x)[::-1])
                if Sosu(a) == 0:
                        print(a)
                        break
else:
        if Inp[1] < 0:
                print("9"*Inp[0]*2)
        else:
                print("9"*Inp[0]+str(Inp[1])+"9"*Inp[0])