結果

問題 No.775 tatyamと素数大富豪(hard)
ユーザー tatyamtatyam
提出日時 2018-12-10 23:00:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,131 bytes
コンパイル時間 902 ms
コンパイル使用メモリ 81,996 KB
実行使用メモリ 142,384 KB
最終ジャッジ日時 2024-10-14 01:25:14
合計ジャッジ時間 6,767 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
import math
import heapq
import copy
import sys
def is_prime(n, k=50):
    assert n > 0
    if n == 2:
        return True
    elif n == 1 or n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for i in range(k):
        a = random.randint(1, n - 1)
        if pow(a, d, n) != 1:
            for r in range(0, s):
                if pow(a, d * 2 ** r, n) == n - 1:
                    break
            else:
                return False
    return True

class number(object):
    def __init__(self, num, n, cards, oned = 0):
        self.num = num
        self.n = n
        self.cards = cards
        self.oned = oned
    def __lt__(self, other):
        for i in range(min(len(self.num),len(other.num))):
            if self.num[i] != other.num[i]:
                return self.num[i] > other.num[i]
        return len(self.num) < len(other.num)
    def __eq__(self, other):
        if not isinstance(other, number):
            return False
        return self.num == other.num and self.cards == other.cards
    def __hash__(self):
        return hash(str(self.cards) + self.num)

n, k = map(int, input().split())
if n == 1:
    a = int(input())
    if is_prime(a):
        print(a)
    print(-1)
    sys.exit()
a = [0] * 100
l = list(map(int, input().split()))
if sum(l) % 3 == 0:
    print(-1)
    sys.exit()
g = l[0]
for i in l[1:]:
    g = math.gcd(g, i)
if g != 1:
    print(-1)
    sys.exit()
for i in l:
    a[i] += 1
q = []
s = set()
heapq.heappush(q, number('', n, a))
while k > 0 and q:
    top = heapq.heappop(q)
    if top in s:
       continue
    s.add(top)
    if top.n == 0:
        if is_prime(int(top.num)):
            print(top.num)
            k -= 1
        continue
    b = True
    for i in range(1, 100, 2):
        if(i % 5 != 0 and top.cards[i] != 0):
            b = False
            break
    if b:
        continue
    b = True
    for i in range(1, 10):
        if(top.cards[i] != 0):
            b = False
            break
    if b:
        c = 0 if top.num == '' else int(top.num) % 11
        for i in range(10, 100):
            c += i * top.cards[i]
        if c % 11 == 0:
            continue
    for i in range(10, 100):
        if i % 11 == 0 and top.cards[i // 11] > 0:
            j = i // 11
            if top.oned == j:
                continue
            card1 = top.cards[j]
            card11 = top.cards[i]
            n = top.n
            num = top.num
            while top.cards[i] > 0 or top.cards[j] > 0:
                num = num + chr(j + 48)
                if card1 > top.cards[j] and top.cards[i] > 0:
                    top.cards[j] += 1
                    top.cards[i] -= 1
                else:
                    top.cards[j] -= 1
                    n -= 1
                heapq.heappush(q, number(num ,n , copy.copy(top.cards), j))
            top.cards[j] = card1
            top.cards[i] = card11
        elif top.cards[i] > 0:
            cards = copy.copy(top.cards)
            cards[i] -= 1
            heapq.heappush(q, number(top.num + str(i), top.n - 1, cards))
print(-1)
0