結果
問題 | No.2247 01 ZigZag |
ユーザー |
![]() |
提出日時 | 2023-03-17 22:00:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,801 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 81,728 KB |
実行使用メモリ | 74,032 KB |
最終ジャッジ日時 | 2024-09-18 16:09:27 |
合計ジャッジ時間 | 4,355 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 50 |
ソースコード
import itertools'''K+1個のブロックa_0,...,a_Ka_i>=1a_{2i}個の0a_{2i+1}個の1辞書順最小にするためにはa_0を極力大きくa_2,a_4,...,a_{2i}を1'''n,m,k=map(int,input().split())def solve(N,M,K):if K==0:if N*M>0:return(-1)else:return("0"*N+"1"*M)Ncash=NMcash=MA=[0 for i in range(K+1)]for i in range(1,K+1,2):A[i]+=1M-=1if M<0:return -1A[K-(K+1)%2]+=Mfor i in range(0,K+1,2):A[i]+=1N-=1if N<0:N=NcashM=McashB=[0 for i in range(K+1)]for i in range(0,K+1,2):B[i]+=1M-=1if M<0:return -1B[K-K%2]+=Mfor i in range(1,K+1,2):B[i]+=1N-=1if N<0:return -1B[1]+=Nres=[]for i in range(K+1):res.append(str((i+1)%2)*B[i])return "".join(res)else:A[0]+=Nres=[]for i in range(K+1):res.append(str(i%2)*A[i])return "".join(res)def solve_naive(N,M,K):ans=[]for seq in itertools.combinations(range(N+M),M):res=[0 for i in range(N+M)]for i in seq:res[i]=1cnt=0for i in range(N+M-1):if res[i]!=res[i+1]:cnt+=1if cnt==K:ans.append(res)if len(ans)==0:return -1else:return "".join([str(x) for x in min(ans)])import randomprint(solve(n,m,k))#print(solve_naive(n,m,k))exit()while(True):n=random.randrange(5)m=random.randrange(5)k=random.randrange(10)ans1=solve(n,m,k)ans2=solve_naive(n,m,k)if ans1!=ans2:print(ans1,ans2,n,m,k)break