Codeforces Beta Round #17

はい。

A. Noldbach problem

brute force,math,number theory

ざっくりと大意

・nまでの数の中に2つ並びの素数と1の和が素数になるケースがあるかどうか？
・そのあてはまるケースがk個以上あるかどうか？

方針のようなもの

・素数の計算の仕方が知らない面倒だし、1000までなら素数全部をあらかじめリストに入れておけばいいでしょ。。。。

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys,io
import re,math
start = time.clock()
p=['ここで1000までの素数を全部列挙']
(n,k)=map(int, raw_input().split())
chk=0
for i in range(n):
    if p[i]+p[i+1]+1>n: break
    elif p[i]+p[i+1]+1 in p:
        chk+=1
print 'YES' if chk>=k else 'NO'

kusanoさんの素数のとり方が短い式ですごかったのでその部分だけ抜き出して実際に試してみた。

>>> prime=[]
>>> for i in xrange(2,50):
...   if all((i%p!=0 for p in prime)):
...     prime+=[i]
... 
>>> prime
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

100000とかまで探しに行くと時間掛かるようになるみたいだけど1000までとかならほぼ即終わる。しかしコレprimeが空のリストから始めてるのにどう動いてるんだろ。。。。

B. Hierarchy

ざっくりと大意

・Nickの会社はn人を雇ってる。 ・階級分けをして雇用者たちに一人のsupervisorを付ける？ 最小コストを〜っぽいけど解読できず。。。