Submission #9014965


Source Code Expand

Copy
import itertools
import random
import numpy as np

# 有限体上の射影平面
# p = 13として、150本の直線と150個の点を選ぶ
# だいたい 1/13 が条件を満たすので、1700個くらいある

p = 13
N = 150

def projective_coordinate(p):
    for a,b in itertools.product(range(p),range(p)):
        yield (a,b,1)
    for a in range(p):
        yield (a,1,0)
    yield (1,0,0)

P2 = np.array(list(projective_coordinate(p)))

a,b,c = P2.T
f = a[:,None] * a[None,:] + b[:,None] * b[None,:] + c[:,None] * c[None,:]
A = np.where(f % p == 0, 1, 0)

while True:
    I = np.random.choice(np.arange(p*p + p + 1), N, replace = False)
    B = A[I]
    col_cnt = B.sum(axis = 0)
    J = col_cnt.argsort()[::-1]
    B = B[:,J[:N]]
    x = B.sum()
    if x >= 1700:
        break

answer = np.where(B,'O','.')
print(N)
print('\n'.join(''.join(row) for row in answer))

Submission Info

Submission Time
Task D - ほんとうのたたかい
User maspy
Language Python (3.4.3)
Score 100
Code Size 912 Byte
Status AC
Exec Time 164 ms
Memory 13864 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 1
Set Name Test Cases
All test.txt
Case Name Status Exec Time Memory
test.txt AC 164 ms 13864 KB