結果

問題 No.3024 等式
ユーザー testestest
提出日時 2016-06-08 14:58:59
言語 C90
(gcc 4.8.5)
結果
AC  
実行時間 1,215 ms
コード長 2,220 Byte
コンパイル時間 96 ms
使用メモリ 968 KB
最終ジャッジ日時 2018-12-04 21:21:35

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
3_NO1.txt AC 1 ms
964 KB
3_YES1.txt AC 1 ms
964 KB
4_NO1.txt AC 1 ms
968 KB
4_NO2.txt AC 1 ms
968 KB
4_YES1.txt AC 0 ms
968 KB
4_YES2.txt AC 0 ms
964 KB
5_NO1.txt AC 1 ms
968 KB
5_NO2.txt AC 1 ms
968 KB
5_NO3.txt AC 1 ms
964 KB
5_YES1.txt AC 1 ms
968 KB
5_YES2.txt AC 0 ms
968 KB
5_YES3.txt AC 1 ms
964 KB
6_NO1.txt AC 14 ms
968 KB
6_NO2.txt AC 12 ms
968 KB
6_NO3.txt AC 16 ms
968 KB
6_YES1.txt AC 2 ms
968 KB
6_YES2.txt AC 2 ms
968 KB
6_YES3.txt AC 15 ms
968 KB
7_1.txt AC 1 ms
964 KB
7_2.txt AC 1 ms
968 KB
7_3.txt AC 65 ms
968 KB
challenge01.txt AC 1,215 ms
964 KB
テストケース一括ダウンロード
コンパイルメッセージ
main.c: In function ‘main’:
main.c:84:2: warning: incompatible implicit declaration of built-in function ‘scanf’ [enabled by default]
  scanf("%d",&n);
  ^

ソースコード

diff #
#include <stdlib.h>
#include <assert.h>
typedef struct {
	long long nume;
	long long deno;
} frac;
long long a[10],target;
int n;
frac num[10];

long long gcd(long long p,long long q){return q?gcd(q,p%q):p;}

void fr_op(frac t0,frac t1,frac* ans,int op){
	long long deno,nume,d;
	switch(op){
	case 0://足し算
		deno=t0.deno*t1.deno;
		nume=t0.nume*t1.deno+t1.nume*t0.deno;
		break;
	case 1://掛け算
		deno=t0.deno*t1.deno;
		nume=t0.nume*t1.nume;
		break;
	case 2://割り算1
		deno=t0.deno*t1.nume;
		nume=t0.nume*t1.deno;
		break;
	case 3://割り算2
		deno=t0.nume*t1.deno;
		nume=t0.deno*t1.nume;
		break;
	case 4://引き算
		if(t0.deno*t1.nume<t0.nume*t1.deno){
			deno=t0.deno*t1.deno;
			nume=t0.nume*t1.deno-t1.nume*t0.deno;
		}else{
			deno=t0.deno*t1.deno;
			nume=t1.nume*t0.deno-t0.nume*t1.deno;
		}
		break;
		//0が発生するのは引き算の結果のみ
		//その直前には等式ができているのでその場合を分けてもいい
	}
	//約分
	d=gcd(deno,nume);
	if(d==0)d=1;
	//t0,t1がともに0だと割り算1,2の結果deno,numeがどちらも0になる
	(*ans).nume=nume/d;
	(*ans).deno=deno/d;
	return;
}


int check(frac*num,int count){
	int i,j,k,op;
	frac next[10],temp0,temp1;

	if(num[0].nume==target&&num[0].deno==1)return 1;
	//num[0]が求める値になっていればOK
	if(count==1)return 0;
	//そうでなく要素数が1ならダメ

	for(i=0;i<count-1;i++)for(j=i+1;j<count;j++){
		//1.numから2数を取る
		//2.選んだ2数に四則のいずれかを施す
		//3.その結果をnum[0]に戻して再帰

		for(k=0;k<count;k++)next[k]=num[k];
		temp0=next[i];
		temp1=next[j];
		next[i]=next[0];
		next[j]=next[count-1];

		for(op=0;op<5;op++){
			fr_op(temp0,temp1,&next[0],op);
			if(check(next,count-1))return 1;
		}
	}
	return 0;
}

int main(){
	int i,j;
	scanf("%d",&n);
	assert(3<=n&&n<=7);
	for(i=0;i<n;i++){
		scanf("%lld",a+i);
		assert(1<=a[i]&&a[i]<=100);
		num[i].nume=a[i];
		num[i].deno=1;
		//numには有理数を格納する
		for(j=0;j<i;j++)assert(a[i]!=a[j]);
	}
	for(i=n-1;i>1;i--){
		target=a[i];
		if(check(num,i)){puts("YES");return 0;}
		//{a[k]|1<=k<=i-1}からa[i]が作れるか調べる
	}
	puts("NO");
	return 0;
}
0