結果

問題 No.775 tatyamと素数大富豪(hard)
コンテスト
ユーザー 👑 tatyam
提出日時 2018-10-20 11:08:55
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,725 bytes
コンパイル時間 75 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 44,580 KB
最終ジャッジ日時 2024-10-14 01:23:40
合計ジャッジ時間 3,751 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 3 TLE * 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, 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))
0