結果

問題 No.775 tatyamと素数大富豪(hard)
ユーザー 👑 tatyam
提出日時 2018-10-20 08:22:24
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,638 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 18,176 KB
最終ジャッジ日時 2024-10-14 01:23:31
合計ジャッジ時間 4,099 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 RE * 1 TLE * 1 -- * 1
other -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
import heapq
import copy
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):
        self.num = num
        self.n = n
        self.cards = cards
    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)

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 = {}
heapq.heappush(q, number('', n, a))
while k > 0:
    top = heapq.heappop(q)
    if top.n == 0:
        if top.num not in s:
            s[top.num] = True
            if is_prime(int(top.num)):
                print(top.num)
                k -= 1
        continue
    b = True
    for i in range(1, 100, 2):
        if(top.cards[i] != 0):
            b = False
            break
    if b:
        continue
    for i in range(1, 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))
0