結果

問題 No.861 ケーキカット
ユーザー 👑 testestest
提出日時 2018-10-21 03:58:49
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 20 ms / 1,000 ms
コード長 1,203 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 30,976 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 19:02:04
合計ジャッジ時間 1,454 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'main':
main.c:34:17: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   34 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
  +++ |+#include <stdio.h>
    1 | /*
main.c:34:17: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
   34 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:34:17: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:47:35: warning: implicit declaration of function 'labs' [-Wimplicit-function-declaration]
   47 |                                 t=labs(t);
      |                                   ^~~~
main.c:1:1: note: include '<stdlib.h>' or provide a declaration of 'labs'
  +++ |+#include <stdlib.h>
    1 | /*
main.c:47:35: warning: incompatible implicit declaration of built-in function 'labs' [-Wbuiltin-declaration-mismatch]
   47 |                                 t=labs(t);
      |                                   ^~~~
main.c:47:35: note: include '<stdlib.h>' or provide a declaration of 'labs'
main.c:52:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   52 |         printf("%ld",ans);
      |         ^~~~~~
main.c:52:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:52:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:52:9: note: include '<stdio.h>' or provide a declaration of 'printf'

ソースコード

diff # 

/*
外周のはどこで切るかで16*15/2通り＋切らない1通り。残りは全探索
ペンシルパズルの「しろまるくろまる」を知っていると思いつきやすい？
*/

int a[]={0,1,2,3,4,9,14,19,24,23,22,21,20,15,10,5};
int b[]={6,7,8,11,12,13,16,17,18};
long s[25];
int board[25];

void dfs(int n){
	board[n]+=10;
	if(n%5!=0&&board[n-1]<2&&board[n]%10==board[n-1]%10)dfs(n-1);//左
	if(n%5!=4&&board[n+1]<2&&board[n]%10==board[n+1]%10)dfs(n+1);//右
	if(n>=5&&board[n-5]<2&&board[n]%10==board[n-5]%10)dfs(n-5);//上
	if(n<20&&board[n+5]<2&&board[n]%10==board[n+5]%10)dfs(n+5);//下
}

int f(){
	dfs(0);
	int n=0;
	while(n<25&&board[n]>=10)n++;
	if(n==25)return 1;
	dfs(n);
	while(n<25&&board[n]>=10)n++;
	if(n==25)return 1;
	return 0;	
}


int main(){
	long ans=0;
	for(int i=0;i<25;i++){
		scanf("%ld",&s[i]);
		ans+=s[i];
	}
	
	for(int i=0;i<16;i++)for(int j=i;j<16-!!i;j++){
		for(int n=0;n<512;n++){
			//外周
			for(int k=0;k<16;k++)board[a[k]]=(i<=k)&&(k<=j);		
			//内部
			for(int k=0;k<9;k++)board[b[k]]=(n>>k)&1;
			if(f()){
				long t=0;
				for(int k=0;k<25;k++)t+=board[k]%10?s[k]:-s[k];
				t=labs(t);
				if(t<ans)ans=t;
			}
		}
	}
	printf("%ld",ans);
}
0