結果

問題 No.3024 等式
ユーザー akakimidoriakakimidori
提出日時 2018-08-02 01:02:34
言語 C90
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,247 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 24,960 KB
実行使用メモリ 8,348 KB
最終ジャッジ日時 2024-09-19 16:59:09
合計ジャッジ時間 7,930 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 0 ms
6,944 KB
testcase_03 AC 0 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 0 ms
6,944 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 5 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 0 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 266 ms
6,940 KB
testcase_13 AC 261 ms
6,944 KB
testcase_14 AC 286 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 15 ms
6,940 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 9 ms
6,944 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘run’:
main.c:118:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |   scanf("%d",&n);
      |   ^~~~~~~~~~~~~~
main.c:121:20: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  121 |   for(i=0;i<n;i++) scanf("%d",a+i);
      |                    ^~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

typedef struct fraction{
  int64 nu;
  int64 de;
} frac;

int64 gcd(int64 a,int64 b){
  int64 r=a%b;
  while(r>0){
    a=b;b=r;r=a%b;
  }
  return b;
}

void add(frac *c,frac *a,frac *b){
  int64 x=a->nu*b->de+a->de*b->nu;
  if(x==0){
    c->nu=0;
    c->de=1;
    return;
  }
  int64 y=a->de*b->de;
  int64 g=gcd(ABS(x),y);
  c->nu=x/g;
  c->de=y/g;
  return;
}

void sub(frac *c,frac *a,frac *b){
  int64 x=a->nu*b->de-a->de*b->nu;
  if(x==0){
    c->nu=0;
    c->de=1;
    return;
  }
  int64 y=a->de*b->de;
  int64 g=gcd(ABS(x),y);
  c->nu=x/g;
  c->de=y/g;
  return;
}

void mul(frac *c,frac *a,frac *b){
  int64 x=a->nu*b->nu;
  if(x==0){
    c->nu=0;
    c->de=1;
    return;
  }
  int64 y=a->de*b->de;
  int64 g=gcd(ABS(x),y);
  c->nu=x/g;
  c->de=y/g;
  return;
}

void division(frac *c,frac *a,frac *b){
  int64 x=a->nu*b->de;
  if(x==0){
    c->nu=0;
    c->de=1;
    return;
  }
  int64 y=a->de*b->nu;
  int64 g=gcd(ABS(x),ABS(y));
  if(y<0){
    y=-y;
    x=-x;
  }
  c->nu=x/g;
  c->de=y/g;
  return;
}

frac stack[7];
int test;
int b[6];
int num;

int calc(int top){
  if(top==1 && stack[0].nu==test && stack[0].de==1) return 1;
  //operator
  if(top>=2){
    frac a=stack[top-2];
    frac b=stack[top-1];
    add(stack+top-2,&a,&b);if(calc(top-1)) return 1;
    sub(stack+top-2,&a,&b);if(calc(top-1)) return 1;
    mul(stack+top-2,&a,&b);if(calc(top-1)) return 1;
    if(b.nu!=0) division(stack+top-2,&a,&b);if(calc(top-1)) return 1;
    stack[top-2]=a;
    stack[top-1]=b;
  }
  //push
  int i;
  for(i=0;i<num;i++){
    if(b[i]==0) continue;
    int m=b[i];
    b[i]=0;
    stack[top].nu=m;
    stack[top].de=1;
    if(calc(top+1)) return 1;
    b[i]=m;
  }
  return 0;
}

void run(void){
  int n;
  scanf("%d",&n);
  int a[7];
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  num=n-1;
  for(i=0;i<n;i++){
    int j;
    int k=0;
    for(j=0;j<n;j++){
      if(i==j) continue;
      b[k++]=a[j];
    }
    test=a[i];
    if(calc(0)){
      printf("YES\n");
      return;
    }
  }
  printf("NO\n");
}

int main(void){
  run();
  return 0;
}
0