結果

問題 No.8024 等式
コンテスト
ユーザー 👑 testestest
提出日時 2016-06-08 14:58:59
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 1,280 ms / 5,000 ms
コード長 2,220 bytes
コンパイル時間 599 ms
コンパイル使用メモリ 23,168 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-30 04:12:54
合計ジャッジ時間 2,568 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:84:9: warning: implicit declaration of function ‘scanf’ [-Wimplicit-function-declaration]
   84 |         scanf("%d",&n);
      |         ^~~~~
main.c:3:1: note: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
    2 | #include <assert.h>
  +++ |+#include <stdio.h>
    3 | typedef struct {
main.c:84:9: warning: incompatible implicit declaration of built-in function ‘scanf’ [-Wbuiltin-declaration-mismatch]
   84 |         scanf("%d",&n);
      |         ^~~~~
main.c:84:9: note: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
main.c:96:34: warning: implicit declaration of function ‘puts’ [-Wimplicit-function-declaration]
   96 |                 if(check(num,i)){puts("YES");return 0;}
      |                                  ^~~~
main.c:96:34: note: include ‘<stdio.h>’ or provide a declaration of ‘puts’

ソースコード

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++){
		//１．numから2数を取る
		//２．選んだ2数に四則のいずれかを施す
		//３．その結果を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