結果
問題 |
No.3245 Payment with 8-rep Currency
|
ユーザー |
![]() |
提出日時 | 2025-08-26 01:00:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,539 bytes |
コンパイル時間 | 569 ms |
コンパイル使用メモリ | 82,580 KB |
実行使用メモリ | 123,064 KB |
最終ジャッジ日時 | 2025-08-26 01:00:58 |
合計ジャッジ時間 | 18,983 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 WA * 3 |
ソースコード
import sys input = sys.stdin.readline L=[[] for i in range(10**6)] for A in range(50): for B in range(50): for C in range(50): for D in range(50): S=A+B+C+D if A*2<S and B*2<S and C*2<S and D*2<S: sc=1*A+11*B+111*C+1111*D if L[sc]==[]: L[sc]=(A,B,C,D) # 拡張ユークリッドの互除法.ax+by=gcd(a,b)となる(x,y)を一つ求め、(x,y)とgcd(x,y)を返す. def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1) q,r=divmod(a,b) if r==0: return bxy,b # a*bxy[0]+b*bxy[1]=b rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める. return Ext_Euc(b,r,bxy,rxy) # 中国剰余定理(拡張ユークリッドの互除法を使う) def Chirem(a,ma,b,mb): # N=a mod ma,N=b mod mbのときN=k mod(lcm(ma,mb))なるk,lcm(ma,mb)を返す. (p,q),d=Ext_Euc(ma,mb) if (a-b)%d!=0: return -1 # 解がないとき-1を出力 return (b*ma*p+a*mb*q)//d%(ma*mb//d),ma*mb//d ret=Ext_Euc(123,235) # (107-235*k,-56*123k) # (1,1,1,0),(2,1,2,0) T=int(input()) for tests in range(T): N=int(input()) if N%8!=0: print(-1) continue N//=8 if N<len(L) and L[N]!=[]: print(*L[N]) continue kk=(56*N+122)//123 a=107*N-235*kk b=-56*N+123*kk A=[a+2*b,a+b,a+2*b,0] if min(A)>=0: print(*A) else: print(-1)