#877379 (PyPy3) No.2339 Factorial Paths

• 問題: No.2339 Factorial Paths
• ユーザー: とりゐ
• 提出日時: 2023-06-02 22:54:43
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 226 ms / 2,000 ms
• コード長: 9,434 bytes
• コンパイル時間: 301 ms
• コンパイル使用メモリ: 82,248 KB
• 実行使用メモリ: 112,256 KB
• 最終ジャッジ日時: 2024-06-09 00:45:09
• 合計ジャッジ時間: 11,120 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	94 ms; 87,964 KB
testcase_01	AC	92 ms; 88,192 KB
testcase_02	AC	92 ms; 88,064 KB
testcase_03	AC	88 ms; 88,244 KB
testcase_04	AC	89 ms; 88,132 KB
testcase_05	AC	91 ms; 87,936 KB
testcase_06	AC	91 ms; 87,808 KB
testcase_07	AC	92 ms; 88,064 KB
testcase_08	AC	94 ms; 88,012 KB
testcase_09	AC	99 ms; 88,280 KB
testcase_10	AC	108 ms; 88,816 KB
testcase_11	AC	129 ms; 107,416 KB
testcase_12	AC	137 ms; 107,420 KB
testcase_13	AC	140 ms; 107,852 KB
testcase_14	AC	147 ms; 107,776 KB
testcase_15	AC	175 ms; 110,080 KB
testcase_16	AC	199 ms; 110,092 KB
testcase_17	AC	217 ms; 111,864 KB
testcase_18	AC	225 ms; 112,168 KB
testcase_19	AC	221 ms; 112,256 KB
testcase_20	AC	223 ms; 111,744 KB
testcase_21	AC	226 ms; 111,744 KB
testcase_22	AC	222 ms; 111,872 KB

ソースコード

def calc(h,w,a):
  dp=[[0]*w for i in range(h)]
  if a[0][0]==1 or a[0][0]=='.':
    dp[0][0]=1
  for i in range(h):
    for j in range(w):
      if a[i][j]==1 or a[i][j]=='.':
        if i>0:
          dp[i][j]+=dp[i-1][j]
        if j>0:
          dp[i][j]+=dp[i][j-1]
  return dp[h-1][w-1]

"""
import sys
sys.setrecursionlimit(3*10**5)

ok=[-1]*401
for w in range(7,1,-1):
  for h in range(w,1,-1):
    kouho=[]
    def choose(res,tmp):
      if len(res)==5 or tmp==h*w:
        kouho.append(res)
        return
      choose(res+[tmp],tmp+1)
      choose(res[::],tmp+1)

    choose([],0)
    print(len(kouho))

    for res in kouho:
      a=[[1]*w for i in range(h)]
      for i in res:
        if not (0<=i//w<h and 0<=i%w<w):
          print(i,h,w)
        a[i//w][i%w]=0
      c=calc(h,w,a)
      if c<=400:
        ok[c]=[res,h,w]

"""
def tenchi(h,w,mat):
  new=[[0]*h for i in range(w)]
  for i in range(h):
    for j in range(w):
      new[j][i]=mat[i][j]
  return new

memo=[[[3], 2, 2], [[2], 2, 2], [[], 2, 2], [[], 2, 3], [[2, 6], 3, 3], [[6], 3, 3], [[], 3, 3], [[9], 3, 4], [[3, 8], 3, 4], [[8], 3, 4], [[], 3, 4], [[9], 4, 4], [[7, 13], 4, 4], [[3, 8, 13], 4, 4], [[8, 13], 4, 4], [[7, 12], 4, 4], [[13], 4, 4], [[12], 4, 5], [[3, 12], 4, 4], [[12], 4, 4], [[], 4, 4], [[8, 9, 15], 4, 5], [[11, 16], 4, 5], [[11], 4, 5], [[4, 17], 4, 5], [[17], 4, 5], [[9, 16], 4, 5], [[4, 10, 16], 4, 5], [[10, 16], 4, 5], [[9, 15], 4, 5], [[10], 4, 5], [[16], 4, 5], [[14, 16, 22], 5, 5], [[4, 15], 4, 5], [[15], 4, 5], [[], 4, 5], [[16, 17], 5, 5], [[9, 10, 16, 22], 5, 5], [[15, 17], 5, 5], [[17, 20], 5, 5], [[17], 5, 5], [[10, 14], 5, 5], [[10, 16, 22], 5, 5], [[12, 20], 4, 6], [[11, 12], 4, 6], [[8, 9, 15, 21], 5, 5], [[10, 22], 5, 5], [[16, 22], 5, 5], [[9, 16, 21], 5, 5], [[9, 16], 5, 5], [[14, 21], 5, 5], [[5, 19], 4, 6], [[8, 9, 20], 5, 5], [[16, 21], 5, 5], [[16], 5, 5], [[22], 5, 5], [[], 4, 6], [[9, 15, 21], 5, 5], [[19, 21], 5, 6], [[11, 21, 24], 5, 6], [[9, 21], 5, 5], [[4, 15, 21], 5, 5], [[15, 21], 5, 5], [[18, 21], 5, 6], [[9, 20], 5, 5], [[21], 5, 5], [[21], 5, 6], [[10, 16, 18, 25], 5, 6], [[4, 20], 5, 5], [[20], 5, 5], [[], 5, 5], [[20, 27], 5, 6], [[16, 18, 25], 5, 6], [[11, 13, 25], 5, 6], [[16, 17, 24], 5, 6], [[16, 18], 5, 6], [[16, 25], 5, 6], [[12, 20], 5, 6], [[17, 19, 26], 5, 6], [[13, 25], 5, 6], [[16, 24], 5, 6], [[20, 26], 5, 6], [[19, 20], 5, 6], [[19, 27], 5, 6], [[18, 20], 5, 6], [[20, 24], 5, 6], [[20], 5, 6], [[17, 18, 26], 5, 6], [[10, 18, 26], 5, 6], [[18, 27], 5, 6], [[17, 26], 5, 6], [[27], 5, 6], [[20, 23, 24, 32], 6, 6], [[11, 19, 26], 5, 6], [[10, 17, 24], 5, 6], [[12, 19], 5, 6], [[17, 18, 25], 5, 6], [[11, 12, 25], 5, 6], [[5, 19, 26], 5, 6], [[19, 26], 5, 6], [[17, 25], 5, 6], [[10, 25], 5, 6], [[11, 18, 26], 5, 6], [[12, 25], 5, 6], [[17, 24], 5, 6], [[19, 25], 5, 6], [[19], 5, 6], [[5, 18, 26], 5, 6], [[18, 26], 5, 6], [[17, 24, 26, 27], 6, 6], [[5, 26], 5, 6], [[26], 5, 6], [[4, 18, 25], 5, 6], [[16, 17, 18, 25, 33], 6, 6], [[11, 18], 5, 6], [[11, 25], 5, 6], [[5, 18, 25], 5, 6], [[18, 25], 5, 6], [[19, 20, 33], 6, 6], [[11, 24], 5, 6], [[18], 5, 6], [[25], 5, 6], [[22, 25], 6, 6], [[22, 24, 32], 6, 6], [[5, 24], 5, 6], [[24], 5, 6], [[], 5, 6], [[25, 26, 27], 6, 6], [[19, 23, 25, 32], 6, 6], [[19, 20, 32], 6, 6], [[24, 26, 27], 6, 6], [[26, 27, 30], 6, 6], [[26, 27], 6, 6], [[10, 19, 25, 33], 6, 6], [[23, 24, 26], 6, 6], [[23, 26, 30], 6, 6], [[25, 27, 31], 6, 6], [[25, 27], 6, 6], [[23, 24, 33], 6, 6], [[19, 23, 30], 6, 6], [[24, 27, 31], 6, 6], [[27, 31], 6, 6], [[20, 24, 31], 6, 6], [[17, 19, 26], 6, 6], [[24, 27], 6, 6], [[17, 26, 33], 6, 6], [[27, 30], 6, 6], [[27], 6, 6], [[9, 10, 23, 24, 31], 6, 6], [[10, 17, 18, 33], 6, 6], [[16, 17, 25, 32], 6, 6], [[20, 30], 6, 6], [[20], 6, 6], [[10, 11, 18, 25, 33], 6, 6], [[11, 19, 33], 6, 6], [[11, 18, 26, 33], 6, 6], [[16, 25, 32], 6, 6], [[11, 19, 26, 30], 6, 6], [[19, 25, 33], 6, 6], [[17, 19, 25, 32], 6, 6], [[23, 25, 32], 6, 6], [[18, 26, 33], 6, 6], [[19, 26, 32], 6, 6], [[19, 26, 30], 6, 6], [[19, 26], 6, 6], [[17, 26, 32], 6, 6], [[26, 33], 6, 6], [[16, 25], 6, 6], [[16, 24, 32], 6, 6], [[17, 24, 26], 6, 6], [[23, 25, 31], 6, 6], [[23, 25], 6, 6], [[23, 24, 32], 6, 6], [[18, 23, 31], 6, 6], [[12, 17, 31], 6, 6], [[23, 32], 6, 6], [[18, 23], 6, 6], [[11, 19, 32], 6, 6], [[5, 18, 25, 33], 6, 6], [[18, 25, 33], 6, 6], [[19, 25, 32], 6, 6], [[11, 25, 26], 6, 6], [[16, 24, 31], 6, 6], [[19, 32], 6, 6], [[11, 24, 26], 6, 6], [[18, 33], 6, 6], [[26, 32], 6, 6], [[25, 26], 6, 6], [[11, 24, 33], 6, 6], [[9, 11, 30], 6, 6], [[24, 26], 6, 6], [[26, 30], 6, 6], [[26], 6, 6], [[5, 24, 33], 6, 6], [[24, 33], 6, 6], [[23, 30], 6, 6], [[33], 6, 6], [[4, 11, 18, 25, 32], 6, 6], [[13, 29], 5, 7], [[6, 21, 29], 5, 7], [[10, 11, 25, 31], 6, 6], [[11, 18, 25, 32], 6, 6], [[10, 25], 6, 6], [[10, 24, 32], 6, 6], [[4, 17, 24, 32], 6, 6], [[17, 25, 31], 6, 6], [[17, 25], 6, 6], [[18, 25, 32], 6, 6], [[6, 28], 5, 7], [[28], 5, 7], [[17, 32], 6, 6], [[31, 32, 36], 6, 7], [[23, 27, 38], 6, 7], [[26, 30, 37], 6, 7], [[28, 31, 32], 6, 7], [[10, 17, 30], 6, 6], [[25, 32], 6, 6], [[10, 24, 31], 6, 6], [[4, 17, 24, 31], 6, 6], [[26, 30], 6, 7], [[11, 25, 31], 6, 6], [[17, 24, 31], 6, 6], [[11, 24, 32], 6, 6], [[27, 30, 31], 6, 7], [[21, 32, 37], 6, 7], [[17, 31], 6, 6], [[25, 31], 6, 6], [[25], 6, 6], [[24, 32], 6, 6], [[21, 24, 37], 6, 7], [[17, 30], 6, 6], [[32], 6, 6], [[4, 11, 24, 31], 6, 6], [[20, 24, 35], 6, 7], [[21, 27, 29, 39], 6, 7], [[27, 28, 31], 6, 7], [[11, 24, 31], 6, 6], [[29, 32], 6, 7], [[27, 31], 6, 7], [[21, 32], 6, 7], [[11, 31], 6, 6], [[5, 24, 31], 6, 6], [[24, 31], 6, 6], [[22, 23, 31, 35], 6, 7], [[28, 32, 36], 6, 7], [[11, 30], 6, 6], [[31], 6, 6], [[23, 30, 31], 6, 7], [[28, 32], 6, 7], [[23, 28, 31], 6, 7], [[5, 30], 6, 6], [[30], 6, 6], [[], 6, 6], [[26, 29, 37], 6, 7], [[21, 26, 37], 6, 7], [[26, 27, 28, 36], 6, 7], [[24, 36], 6, 7], [[20, 23, 28, 30], 6, 7], [[20, 23, 38], 6, 7], [[26, 27, 28], 6, 7], [[26, 27, 36], 6, 7], [[24, 35], 6, 7], [[24], 6, 7], [[26, 29, 36], 6, 7], [[26, 29], 6, 7], [[26, 27, 35], 6, 7], [[31, 39], 6, 7], [[20, 21, 31, 38], 6, 7], [[20, 21, 23, 36], 6, 7], [[26, 28, 37], 6, 7], [[20, 21, 30, 31], 6, 7], [[23, 30, 38], 6, 7], [[19, 26, 35], 6, 7], [[26, 37], 6, 7], [[22, 23, 38], 6, 7], [[18, 19, 20, 36], 6, 7], [[20, 21, 29, 31], 6, 7], [[27, 30, 38], 6, 7], [[22, 30, 39], 6, 7], [[22, 30, 31], 6, 7], [[21, 23, 38], 6, 7], [[23, 30, 37], 6, 7], [[23, 29], 6, 7], [[26, 28, 36], 6, 7], [[22, 31, 36], 6, 7], [[23, 28, 30], 6, 7], [[23, 38], 6, 7], [[26, 28], 6, 7], [[26, 36], 6, 7], [[22, 27, 37], 6, 7], [[22, 29, 39], 6, 7], [[22, 27, 29, 36], 6, 7], [[22, 39], 6, 7], [[26, 35], 6, 7], [[26], 6, 7], [[21, 31, 38], 6, 7], [[22, 27, 36], 6, 7], [[27, 30, 37], 6, 7], [[27, 29, 30], 6, 7], [[21, 30, 39], 6, 7], [[19, 20, 29, 38], 6, 7], [[31, 38], 6, 7], [[29, 30, 31], 6, 7], [[27, 30], 6, 7], [[21, 29, 31], 6, 7], [[28, 30, 31], 6, 7], [[30, 39], 6, 7], [[30, 31], 6, 7], [[20, 39], 6, 7], [[19, 21, 27], 6, 7], [[21, 31], 6, 7], [[29, 31, 36], 6, 7], [[29, 31], 6, 7], [[20, 22, 30, 37], 6, 7], [[20, 22, 30, 35], 6, 7], [[28, 31, 36], 6, 7], [[31, 36], 6, 7], [[21, 29, 39], 6, 7], [[20, 22, 38], 6, 7], [[28, 31], 6, 7], [[11, 19, 20, 37], 6, 7], [[31, 35], 6, 7], [[31], 6, 7], [[21, 39], 6, 7], [[21, 27, 29, 37], 6, 7], [[22, 30, 38], 6, 7], [[29, 39], 6, 7], [[13, 28, 39], 6, 7], [[19, 20, 21, 37], 6, 7], [[19, 27, 28], 6, 7], [[19, 27, 36], 6, 7], [[14, 30, 37], 6, 7], [[19, 21, 29], 6, 7], [[21, 27, 29], 6, 7], [[28, 39], 6, 7], [[19, 27, 35], 6, 7], [[39], 6, 7], [[27, 29, 37], 6, 7], [[12, 13, 22, 37], 6, 7], [[14, 20, 29], 6, 7], [[19, 20, 29, 36], 6, 7], [[22, 30, 37], 6, 7], [[22, 30, 35], 6, 7], [[22, 30], 6, 7], [[20, 22, 29], 6, 7], [[13, 21, 30, 38], 6, 7], [[22, 38], 6, 7], [[27, 29, 36], 6, 7], [[27, 29], 6, 7], [[20, 22, 35], 6, 7], [[20, 22], 6, 7], [[21, 27], 6, 7], [[21, 30, 38], 6, 7], [[27, 28, 37], 6, 7], [[20, 29, 30], 6, 7], [[12, 28, 30], 6, 7], [[12, 30, 35], 6, 7], [[27, 37], 6, 7], [[20, 30, 35], 6, 7], [[20, 30], 6, 7], [[20, 21, 38], 6, 7], [[30, 38], 6, 7], [[13, 22, 37], 6, 7], [[20, 29, 38], 6, 7], [[19, 20, 28], 6, 7], [[22, 29, 37], 6, 7], [[14, 29], 6, 7], [[27, 28, 36], 6, 7], [[11, 20, 36], 6, 7], [[22, 37], 6, 7], [[19, 20, 35], 6, 7], [[27, 28], 6, 7], [[27, 36], 6, 7], [[12, 28, 38], 6, 7], [[21, 30], 6, 7], [[20, 28, 38], 6, 7], [[22, 36], 6, 7], [[27, 35], 6, 7], [[27], 6, 7], [[21, 29, 38], 6, 7], [[13, 30], 6, 7], [[30, 37], 6, 7], [[29, 30], 6, 7], [[27, 35, 37, 38, 39], 7, 7], [[13, 29, 38], 6, 7], [[28, 30], 6, 7], [[30, 35], 6, 7], [[30], 6, 7], [[21, 38], 6, 7], [[12, 21, 37], 6, 7], [[12, 13, 29, 37], 6, 7], [[29, 38], 6, 7], [[5, 13, 28, 38], 6, 7], [[20, 29, 37], 6, 7], [[4, 20, 28, 37], 6, 7], [[12, 20, 37], 6, 7], [[13, 28, 38], 6, 7], [[5, 28, 38], 6, 7], [[4, 21, 37], 6, 7], [[13, 38], 6, 7], [[13, 21, 29, 37], 6, 7]]

n=int(input())
H,W=2000,2000
ans=[['#']*W for i in range(H)]
ans[0][0]='.'
tmpH,tmpW=0,0
for ii in range(1,n+1):
  res,h,w=memo[ii]
  a=[[1]*w for i in range(h)]
  for j in res:
    a[j//w][j%w]=0
  if tmpH<tmpW:
    a=tenchi(h,w,a)
    h,w=w,h
  for i in range(h):
    for j in range(w):
      if a[i][j]:
        ans[i+tmpH][j+tmpW]='.'
  tmpH+=h-1
  tmpW+=w-1
  
ANS=[]
for i in range(tmpH+1):
  ANS.append(''.join(ans[i][:tmpW+1]))

H=tmpH+1
W=tmpW+1
print(H,W)
for i in ANS:
  print(i)