結果
問題 | No.3024 等式 |
ユーザー | testestest |
提出日時 | 2016-06-08 14:58:59 |
言語 | C90 (gcc 11.4.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,948 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 0 ms
6,940 KB |
testcase_04 | AC | 0 ms
6,940 KB |
testcase_05 | AC | 0 ms
6,944 KB |
testcase_06 | AC | 0 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,948 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 13 ms
6,940 KB |
testcase_13 | AC | 14 ms
6,944 KB |
testcase_14 | AC | 16 ms
6,944 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 14 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 69 ms
6,940 KB |
testcase_21 | AC | 0 ms
6,940 KB |
testcase_22 | AC | 1,280 ms
6,944 KB |
コンパイルメッセージ
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’
ソースコード
#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; }