結果

問題 No.775 tatyamと素数大富豪(hard)
ユーザー tatyamtatyam
提出日時 2018-12-02 16:15:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,747 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 206,080 KB
最終ジャッジ日時 2024-10-14 01:24:48
合計ジャッジ時間 4,264 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import random
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 = False):
        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:
    print(input())
    sys.exit()
a = [0] * 100
l = list(map(int, input().split()))
for i in l:
    a[i] += 1
q = []
s = set()
heapq.heappush(q, number('', n, a))
while k > 0:
    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):
        if(i % 2 == 1 and 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
    if top.oned:
        for i in range(1, 10):
            if top.cards[int(top.num[-1]) * 10 + i] == 0 and top.cards[i] > 0:
                cards = copy.copy(top.cards)
                cards[i] -= 1
                heapq.heappush(q, number(top.num + str(i), top.n - 1, cards, True))
    else:
        for i in range(1, 10):
            if top.cards[i] > 0:
                cards = copy.copy(top.cards)
                cards[i] -= 1
                heapq.heappush(q, number(top.num + str(i), top.n - 1, cards, True))
    for i in range(10, 100):
        if 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