题解 - Vijos

1

Sky1231 (sky1231) LV 10 @ 2021-01-23 15:54:08

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    const ll size=4;
    ll flag,sz;
    double key,md=100;
    vector<double> a;
    
    int check(double val)
    {
        char s[32];
        memset(s,0,sizeof(s));
        sprintf(s,"%.12lf",val);
        return strlen(s)-13;
    }
    int eq(double a,double b)
    {
        return abs(a-b)<1e-6;
    }
    void dfs(vector<double> rec)
    {
        if (rec.size()>1)
        {
            vector<double> num;
            num.resize(rec.size()-1);
            for (ll i=0;i<rec.size();i++)
                for (ll j=i+1;j<rec.size();j++)
                {
                    for (ll k=0,l=0;k<rec.size();k++)
                        if (k!=i&&k!=j)
                            num[l++]=rec[k];
                    num[num.size()-1]=rec[i]+rec[j];
                    dfs(num);
                    num[num.size()-1]=rec[i]*rec[j];
                    dfs(num);
                    num[num.size()-1]=rec[i]-rec[j];
                    dfs(num);
                    num[num.size()-1]=rec[j]-rec[i];
                    dfs(num);
                    if (rec[j]!=0)
                    {
                        num[num.size()-1]=rec[i]/rec[j];
                        dfs(num);
                    }
                    if (rec[i]!=0)
                    {
                        num[num.size()-1]=rec[j]/rec[i];
                        dfs(num);
                    }
                }
        }
        else if (eq(fmod(rec[0],md),key)&&check(rec[0])==sz)
            flag=1;
    }
    
    void main()
    {
        a.resize(size);
        for (ll i=0;i<size;i++)
            scanf("%lf",&a[i]);
        while (~scanf("%lld",&sz))
            if (sz>1)
            {
                scanf("%lf",&key);
                flag=0;
                dfs(a);
                printf("%lld\n",flag);
            }
            else
                break;
    }
};

int main()
{
    dts::main();
}

0

涅槃、卿莫 (龙阿紫) LV 10 @ 2021-09-30 18:15:12

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    const ll size=4;
    ll flag,sz;
    double key,md=100;
    vector<double> a;
    
    int check(double val)
    {
        char s[32];
        memset(s,0,sizeof(s));
        sprintf(s,"%.12lf",val);
        return strlen(s)-13;
    }
    int eq(double a,double b)
    {
        return abs(a-b)<1e-6;
    }
    void dfs(vector<double> rec)
    {
        if (rec.size()>1)
        {
            vector<double> num;
            num.resize(rec.size()-1);
            for (ll i=0;i<rec.size();i++)
                for (ll j=i+1;j<rec.size();j++)
                {
                    for (ll k=0,l=0;k<rec.size();k++)
                        if (k!=i&&k!=j)
                            num[l++]=rec[k];
                    num[num.size()-1]=rec[i]+rec[j];
                    dfs(num);
                    num[num.size()-1]=rec[i]*rec[j];
                    dfs(num);
                    num[num.size()-1]=rec[i]-rec[j];
                    dfs(num);
                    num[num.size()-1]=rec[j]-rec[i];
                    dfs(num);
                    if (rec[j]!=0)
                    {
                        num[num.size()-1]=rec[i]/rec[j];
                        dfs(num);
                    }
                    if (rec[i]!=0)
                    {
                        num[num.size()-1]=rec[j]/rec[i];
                        dfs(num);
                    }
                }
        }
        else if (eq(fmod(rec[0],md),key)&&check(rec[0])==sz)
            flag=1;
    }
    
    void main()
    {
        a.resize(size);
        for (ll i=0;i<size;i++)
            scanf("%lf",&a[i]);
        while (~scanf("%lld",&sz))
            if (sz>1)
            {
                scanf("%lf",&key);
                flag=0;
                dfs(a);
                printf("%lld\n",flag);
            }
            else
                break;
    }
};

int main()
{
    dts::main();
}

额按美的

0

Goodhao LV 10 @ 2018-08-09 08:08:29

1A了~
和之前的24点不一样，这里中间结果可以不是整数。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

double a[5];
int nn,m;
double b[5][5];
int ans;
void dfs(int n,double a[]) {
    if (n==1) {
        double tt=fabs(a[1]-floor(a[1]));
        if (!(-eps<tt&&tt<eps)) return;
        string s=to_string((int)a[1]);
        if (s.size()!=nn) return;
        if ((int)a[1]%100==m) ans=1;
        return;
    }
    FOR(i,n) FOR(j,n) if (i!=j) {
        int cnt;
        cnt=0;
        FOR(k,n) if (k!=i&&k!=j) b[n-1][++cnt]=a[k];
        b[n-1][++cnt]=a[i]+a[j];
        dfs(n-1,b[n-1]);
        if (ans) return;
        cnt=0;
        FOR(k,n) if (k!=i&&k!=j) b[n-1][++cnt]=a[k];
        b[n-1][++cnt]=a[i]-a[j];
        dfs(n-1,b[n-1]);
        if (ans) return;
        cnt=0;
        FOR(k,n) if (k!=i&&k!=j) b[n-1][++cnt]=a[k];
        b[n-1][++cnt]=a[i]*a[j];
        dfs(n-1,b[n-1]);
        if (ans) return;
        if (-eps<a[j]&&a[j]<eps) continue;
        cnt=0;
        FOR(k,n) if (k!=i&&k!=j) b[n-1][++cnt]=a[k];
        b[n-1][++cnt]=a[i]/a[j];
        dfs(n-1,b[n-1]);
        if (ans) return;
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    FOR(i,4) cin>>a[i];
    while (cin>>nn>>m) {
        ans=0;
        if (nn==1) ;
        else {
            dfs(4,a);
            cout<<ans<<endl;
        }
    }
    return 0;
}

0

hahayang LV 10 @ 2017-08-07 12:50:48

交了9次(TAT).
orz各位大牛!

0

Type59D LV 10 @ 2016-12-11 19:29:57

测试数据 #0: Accepted, time = 0 ms, mem = 808 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 808 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 804 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 812 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 808 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 808 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 812 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 808 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 808 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 804 KiB, score = 10

0

ILIKE LV 10 @ 2012-09-22 16:23:11

第6组数据死活过不了啊，求第六组数据

~~

原来是判断精度的时候忘了加abs

0

mike_nzk LV 10 @ 2009-11-19 22:04:07

就是1134改输入和判定就行了

0

K-Boy LV 10 @ 2009-10-28 18:08:21

同chiccs:

"用递归形式，每次只合并两个数，这样等价于加括号，但要特判双括号的形式:(a·b)·(c·d)，"·"表示加减乘除运算中的一种，为了这个细节交了N次，第3组和第10组数据不过的同学可能是这里出了问题"

---|---|---|---|其实我不只是错了这里---|---|---|---|---|---|---|---|---|

大家注意一下那个什么break与exit的区别.............在一个过程中是有2个操作的..............

还有，用trunc+frac会非常简单的说

0

broken-boat LV 7 @ 2009-10-06 13:23:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

又栽了又杯具了俺泪流满面了哎= =

一开始直接用1134的程序随便加了个判断结果WA了8个 ...

优化了判断发现死活只过6个...没什么好改的把判断小数的删除没想到过了9个点..中间过程居然可以出现小数，真是狂想曲了T T.

接下来才是最郁闷的...看来看去发现全排列打错一个= =改回来之后居然8个点...

最后一怒之下撤掉了全排列...又一看...才发现少一种括号

终于过了T T

program s1140;

var i,j,l,k,m,n:longint;

wei:qword;

w:array[0..4] of real;

flag,mss:boolean;

function check(x:real):boolean;

var a,b:longint;

begin

b:=0;a:=0;

if abs(x-round(x))>0.001 then exit(false);

if x=10*wei then exit(false);

b:=round(x) mod 100;

if bm then exit(false);

exit(true);

end;

function ww(o:integer;x,y:real):real;

begin

if (o=4) and (y=0) then begin flag:=true; exit(0); end;

if (o=6) and (x=0) then begin flag:=true; exit(0); end;

case o of

1: exit(x+y);

2: exit(x-y);

3: exit(x*y);

4: exit(x/y);

5: exit(y-x);

6: exit(y/x);

end;

end;

procedure search(x,y,z,v:longint);

var i,j,l,k:longint;

a,b,c,d,ans:real;

begin

ans:=0;

a:=w[x]; b:=w[y]; c:=w[z]; d:=w[v];

for i:=1 to 6 do

for j:=1 to 6 do

for k:=1 to 6 do

begin

ans:=ww(k,ww(j,ww(i,a,b),c),d);

if check(ans) then begin writeln(1); mss:=true; exit; end;

ans:=ww(k,ww(i,a,b),ww(j,c,d));

if check(ans) then begin writeln(1); mss:=true; exit; end;

end;

end;

begin

for i:=1 to 4 do

read(w[i]);

w[0]:=w[4];

repeat

readln(n);

if n=1 then halt;

readln(m);

wei:=1;

for i:=1 to n-1 do wei:=wei*10;

mss:=false;

for i:=1 to 4 do

begin

if mss then break;

for j:=i+1 to i+3 do

begin

if mss then break;

for k:=j+1 to j+3 do

begin

if mss then break;

if (k mod 4)(i mod 4) then

for l:=k+1 to k+3 do

if ((l mod 4)(i mod 4)) and ((l mod 4)(j mod 4)) then

begin

if mss then break;

search((i mod 4),(j mod 4),(k mod 4),(l mod 4));

end;

end;

end;

end;

if (not mss) and (n>1) then writeln(0);

until n=1;

end.

0

zhh1993 LV 10 @ 2009-10-05 17:05:26

还是暴力枚举....

可是居然又死在了实数精度上（T^T）....

郁闷！！

0

hw LV 7 @ 2009-09-24 10:12:49

第三和第十组死都过不了= =

求解

0

雨中的风筝 LV 10 @ 2009-08-25 17:19:21

暴力枚举。。。同p1134，可以用记事本里的替换指令

0

chiccs LV 9 @ 2009-08-24 23:26:25

用递归形式，每次只合并两个数，这样等价于加括号，但要特判双括号的形式:(a·b)·(c·d)，"·"表示加减乘除运算中的一种，为了这个细节交了8次，第3组和第10组数据不过的同学可能是这里出了问题

如果输入是n个数的话这个递归模拟的方法就十分麻烦了......因为要特判多括号的情况太多了，时间复杂度至少是O(n^2*n!)＝θ(n^(n+2))

0

Kissy LV 8 @ 2009-08-06 12:34:16

谁有第三和第十组的数据?给我个谢谢

0

EZ_ray040123 LV 10 @ 2009-05-08 19:41:56

4个数，3个符号

7个元素，全排一次，然后用后缀式运算（不用括号的式子）.....很方便

0

yayaha LV 10 @ 2009-04-13 16:53:59

交了21次，终于AC了。。。

0

cgy4ever LV 10 @ 2009-01-26 16:15:59

"第九个数据的第一个错了，数据为937 684 686 1 n=6 m=91 最后还是靠人生第一次cheat过的"

其实没有错的

937 / ( 1 - ( 684 / 686 ) ) = 321391

可以的.

0

DFS LV 8 @ 2008-10-23 13:52:07

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

卡精度时卡紧一点……我开始用0.01，结果WA一个。

0

skyinde2 LV 4 @ 2008-08-08 22:56:34

虽然慢了一点,但随机化操作方便.

编译通过...

├ 测试数据 01：答案正确... 150ms

├ 测试数据 02：答案正确... 478ms

├ 测试数据 03：答案正确... 244ms

├ 测试数据 04：答案正确... 244ms

├ 测试数据 05：答案正确... 166ms

├ 测试数据 06：答案正确... 369ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1676ms

0

pzy3303 LV 10 @ 2007-08-03 21:45:10

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案正确... 0ms

第九个数据的第一个错了，数据为937 684 686 1 n=6 m=91 最后还是靠人生第一次cheat过的

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

题解

26 条题解

24点游戏狂想曲

信息

状态

开发

支持

题解

26 条题解

24点游戏狂想曲

信息

状态

开发

支持

还没有账户？

登录