하스켈, 312318 자

import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
main=do
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr.r$foldr((=<<).y)[[([9,0],[0..])]]p
r[]="NO"
r _="YES"

내가 현재 완전히 이해하지 못하는 이유 때문에 테스트 # 9와 # 16을 적당한 시간 안에 끝내지 못합니다. 그러나 성능에 대해 아무 말도하지 않았습니다.

373 383 자

이 버전은 예제에서 훨씬 빠르게 실행됩니다 . 영역이 너무 작아서 불가능하지 않은지 먼저 확인한 다음 가장 큰 소포로 시작한 다음 지정된 순서대로 삽입합니다. 영역 감지가 완벽하지는 않습니다. 회전을 고려하지 않으므로 일부 입력에서 잘못된 결과가 발생할 수 있습니다. 그러나 테스트 스크립트에서는 작동합니다.

import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
π=product
main=do
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr$if sum(map(π.init)p)>72||null(foldr((=<<).y)[[([9,0],[0..])]].sortBy((.π).compare.π)$p)then"NO"else"YES"

답변

import sys
def L(P,z):
 if not P:return 1
 for w,h in[P[0],P[0][::-1]]:
  m=sum((2**w-1)<<i*6for i in range(h))
  for x in range(7-w):
   for y in range(13-h):
    n=m<<y*6+x
    if z&n==0and L(P[1:],z|n):return 1
 return 0
for G in sys.stdin.read().split('\n\n'):
 S=[(x,y)if z<6 else(x,z)if y<6 else(y,z)if x<6 else(9,9)for x,y,z in[sorted(eval(g.replace(' ',',')))for g in G.split('\n')[1:]if g]]
 print'YES\n'if sum(x*y for x,y in S)<73and L(S,0)else'NO\n'

"NO":g;~](;3/127{128*64+}12*\{.,0>.!{"YES":g;}*{([{[~@]..[~\]\}3*;]{)6<{~[2\?(]*128base 83,{2\?1$*.4$&0={3$|2$f}*}%;}*}%;}*;;}:f~g