結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2023-08-15 16:21:20 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 30,720 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-24 00:18:02 |
合計ジャッジ時間 | 1,325 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<stdio.h> int func(int x){ int cnt=0; while(x){ cnt+=x%2; x/=2; } return cnt; } int main(){ int n; scanf("%d",&n); int dp[10002]={}; dp[1]=1; int q[10002]={}; int ql=0,qr=1; q[0]=1; while(qr!=ql){ int p=q[ql]; ql++; int t=func(p); //printf("[%d %d]",p,t); for(int i=-t;i<=t;i++){ for(int j=-t;j<=t;j++){ if(i+j!=t && i+j!=-t)continue; if(p+i+j<=n && (dp[p+i+j]==0 || dp[p+i+j] > dp[p]+1)){ // printf("[%d %d]",p,p+i+j); dp[p+i+j]=dp[p]+1; q[qr]=p+i+j; qr++; } } } } if(dp[n]!=0)printf("%d",dp[n]); else printf("-1"); return 0; }