結果

問題 No.775 tatyamと素数大富豪(hard)
ユーザー tatyamtatyam
提出日時 2018-10-20 08:22:24
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,638 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 18,176 KB
最終ジャッジ日時 2024-10-14 01:23:31
合計ジャッジ時間 4,099 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 WA -
testcase_02 WA -
testcase_03 TLE -
testcase_04 -- -
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
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