結果

問題 No.861 ケーキカット
ユーザー testestesttestestest
提出日時 2018-10-21 03:58:49
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 23 ms / 1,000 ms
コード長 1,203 bytes
コンパイル時間 637 ms
コンパイル使用メモリ 30,384 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 02:13:19
合計ジャッジ時間 2,309 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
4,380 KB
testcase_01 AC 23 ms
4,376 KB
testcase_02 AC 22 ms
4,380 KB
testcase_03 AC 22 ms
4,376 KB
testcase_04 AC 22 ms
4,380 KB
testcase_05 AC 23 ms
4,376 KB
testcase_06 AC 23 ms
4,380 KB
testcase_07 AC 23 ms
4,376 KB
testcase_08 AC 22 ms
4,380 KB
testcase_09 AC 22 ms
4,380 KB
testcase_10 AC 23 ms
4,376 KB
testcase_11 AC 23 ms
4,376 KB
testcase_12 AC 22 ms
4,380 KB
testcase_13 AC 23 ms
4,380 KB
testcase_14 AC 22 ms
4,380 KB
testcase_15 AC 23 ms
4,376 KB
testcase_16 AC 23 ms
4,380 KB
testcase_17 AC 22 ms
4,380 KB
testcase_18 AC 23 ms
4,376 KB
testcase_19 AC 22 ms
4,376 KB
testcase_20 AC 23 ms
4,376 KB
testcase_21 AC 22 ms
4,376 KB
testcase_22 AC 23 ms
4,376 KB
testcase_23 AC 22 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘main’ 内:
main.c:34:17: 警告: 関数 ‘scanf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   34 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:1:1: 備考: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
  +++ |+#include <stdio.h>
    1 | /*
main.c:34:17: 警告: 組み込み関数 ‘scanf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
   34 |                 scanf("%ld",&s[i]);
      |                 ^~~~~
main.c:34:17: 備考: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
main.c:47:35: 警告: 関数 ‘labs’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   47 |                                 t=labs(t);
      |                                   ^~~~
main.c:1:1: 備考: include ‘<stdlib.h>’ or provide a declaration of ‘labs’
  +++ |+#include <stdlib.h>
    1 | /*
main.c:47:35: 警告: 組み込み関数 ‘labs’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
   47 |                                 t=labs(t);
      |                                   ^~~~
main.c:47:35: 備考: include ‘<stdlib.h>’ or provide a declaration of ‘labs’
main.c:52:9: 警告: 関数 ‘printf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   52 |         printf("%ld",ans);
      |         ^~~~~~
main.c:52:9: 備考: include ‘<stdio.h>’ or provide a declaration of ‘printf’
main.c:52:9: 警告: 組み込み関数 ‘printf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
main.c:52:9: 備考: 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