SGU 306 Balance

タイトルリンク:http://acm.sgu.ru/problem.php?contest=0&problem=306
标题:あなたにN個の硬貨(3<=N<=100)をあげて、その中の1枚は偽の硬貨で、しかも重量は他の硬貨と異なって(少し軽くあるいは少し重いかもしれません)、今あなたに1つの天秤をあげて、最悪の情況の下で少なくとも何回偽の硬貨を探し出すことができることを聞いて、そして方案を出力します.
構想:まずnを3つの山に分けて、n=3 k、k、kに分けます;n=3 k+1、k,k,k+1に分ける.n=3 k+2、k+1、k+1、kに分けます.第1回は前の2つの山が等しいと言って、不良品は第3の山の中で、前の2つの山のいずれかが本物です.そうでなければ、不良品は前の2つの山の中の3つ目の山の中のいずれかが本物です.2つの山の中で不良品を探すには、前の2つの山をそれぞれ3つの山に分けて、a 1、a 2、a 3、b 1、b 2、b 3にしてもいいです.a 1+b 1とa 2+b 2と呼ぶ.この場合、等しい場合はa 3とb 3で不良品を探す.そうでなければ、a 2およびb 1またはb 2およびa 1で探す.山の中で不良品を探して、それを3つの山に分けて最初と同じです.

#include <iostream>

#include <cstdio>

#include <string.h>

#include <algorithm>

#include <cmath>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <string>

#include <map>

#include <sstream>





#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define abs(x) ((x)>=0?(x):-(x))

#define i64 long long

#define u32 unsigned int

#define u64 unsigned long long

#define clr(x,y) memset(x,y,sizeof(x))

#define CLR(x) x.clear()

#define ph(x) push(x)

#define pb(x) push_back(x)

#define Len(x) x.length()

#define SZ(x) x.size()

#define PI acos(-1.0)

#define sqr(x) ((x)*(x))



#define FOR0(i,x) for(i=0;i<x;i++)

#define FOR1(i,x) for(i=1;i<=x;i++)

#define FOR(i,a,b) for(i=a;i<=b;i++)

#define DOW0(i,x) for(i=x;i>=0;i--)

#define DOW1(i,x) for(i=x;i>=1;i--)

#define DOW(i,a,b) for(i=a;i>=b;i--)

using namespace std;





void RD(int &x){scanf("%d",&x);}

void RD(i64 &x){scanf("%I64d",&x);}

void RD(u32 &x){scanf("%u",&x);}

void RD(double &x){scanf("%lf",&x);}

void RD(int &x,int &y){scanf("%d%d",&x,&y);}

void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}

void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}

void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}

void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}

void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}

void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}

void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}

void RD(char &x){x=getchar();}

void RD(char *s){scanf("%s",s);}

void RD(string &s){cin>>s;}





void PR(int x) {printf("%d
",x);}

void PR(i64 x) {printf("%lld
",x);}

void PR(u32 x) {printf("%u
",x);}

void PR(u64 x) {printf("%llu
",x);}

void PR(double x) {printf("%.4lf
",x);}

void PR(char x) {printf("%c
",x);}

void PR(char *x) {printf("%s
",x);}

void PR(string x) {cout<<x<<endl;}



#define type vector<int>



void solve1(type,int);

void solve2(type,type,int);



int n,id;



void printSet(type p)

{

    printf("%d",p[0]);

    int i;

    FOR1(i,SZ(p)-1) printf("+%d",p[i]);

}



void print(int cnt)

{

    while(cnt--) putchar(' ');

}



void divide(type a,type b[3])

{

    int n=SZ(a),k=n/3,i,j;

    FOR0(i,3) FOR0(j,k) b[i].pb(a[i*k+j]);

    if(n%3==1) b[2].pb(a[n-1]);

    else if(n%3==2) b[0].pb(a[n-2]),b[1].pb(a[n-1]);

}



void solve1(type a,int dep)

{

    if(SZ(a)==1)

    {

        print(dep); printf("fake %d
",a[0]);

        return;

    }

    if(SZ(a)==2)

    {

        print(dep); printf("weigh %d vs %d
",id,a[0]);

        print(dep); printf("case <:
");

        print(dep); printf("  fake %d
",a[0]);

        print(dep); printf("case =:
");

        print(dep); printf("  fake %d
",a[1]);

        print(dep); printf("case >:
");

        print(dep); printf("  fake %d
",a[0]);

        print(dep); printf("end
");

        return;

    }

    type son[3];

    int n=SZ(a),k=n/3,i,j;

    FOR0(i,3) FOR0(j,k) son[i].pb(a[i*k+j]);

    if(n%3) son[0].pb(id),son[1].pb(a[n-1]);

    if(n%3==2) son[2].pb(a[n-2]);

    print(dep); printf("weigh ");printSet(son[0]);printf(" vs ");printSet(son[1]);printf("
");

    if(n%3) son[0].pop_back();

    print(dep); printf("case <:
"); solve2(son[1],son[0],dep+1);

    print(dep); printf("case =:
"); solve1(son[2],dep+1);

    print(dep); printf("case >:
"); solve2(son[0],son[1],dep+1);

    print(dep); printf("end
");

}



void solve2(type a,type b,int dep)

{

    if(SZ(a)==1&&SZ(b)==1)

    {

        print(dep); printf("weigh %d vs %d
",a[0],id);

        print(dep); printf("case >:
");

        print(dep); printf("  fake %d
",a[0]);

        print(dep); printf("case =:
");

        print(dep); printf("  fake %d
",b[0]);

        print(dep); printf("end
");

        return;

    }

    if(SZ(a)==2&&!SZ(b))

    {

        print(dep); printf("weigh %d vs %d
",a[0],a[1]);

        print(dep); printf("case >:
");

        print(dep); printf("  fake %d
",a[0]);

        print(dep); printf("case <:
");

        print(dep); printf("  fake %d
",a[1]);

        print(dep); printf("end
");

        return;

    }

    if(!SZ(a)&&SZ(b)==2)

    {

        print(dep); printf("weigh %d vs %d
",b[0],b[1]);

        print(dep); printf("case >:
");

        print(dep); printf("  fake %d
",b[1]);

        print(dep); printf("case <:
");

        print(dep); printf("  fake %d
",b[0]);

        print(dep); printf("end
");

        return;

    }

    if(!SZ(a))

    {

        solve1(b,dep);

        return ;

    }

    if(!SZ(b))

    {

        solve1(a,dep);

        return;

    }

    type sonA[3],sonB[3];

    divide(a,sonA);

    divide(b,sonB);

    if(SZ(a)%3==1&&SZ(b)%3==1)

    {

        sonB[0].pb(*(sonB[2].end()-1));

        sonB[2].pop_back();

        sonB[1].pb(*(sonB[2].end()-1));

        sonB[2].pop_back();

    }

    print(dep); printf("weigh ");

    if(SZ(sonA[0]))

    {

        printSet(sonA[0]);

        if(SZ(sonB[0])) printf("+");

    }

    if(SZ(sonB[0])) printSet(sonB[0]);

    printf(" vs ");

    if(SZ(sonA[1]))

    {

        printSet(sonA[1]);

        if(SZ(sonB[1])) printf("+");

    }

    if(SZ(sonB[1])) printSet(sonB[1]);

    printf("
");



    print(dep); printf("case <:
"); solve2(sonA[1],sonB[0],dep+1);

    if(SZ(sonA[2])||SZ(sonB[2]))

    {

        print(dep);

        printf("case =:
");

        solve2(sonA[2],sonB[2],dep+1);

    }

    print(dep); printf("case >:
"); solve2(sonA[0],sonB[1],dep+1);

    print(dep); printf("end
");

}



int main()

{

    RD(n);

    int ans=0,i,j,k=n/3;

    for(i=1;i<n*2;i*=3,ans++);

    printf("need %d weighings
",ans);

    type s[3];

    FOR0(i,3) FOR1(j,k) s[i].pb(i*k+j);

    if(n%3==1) s[2].pb(n);

    else if(n%3==2) s[0].pb(n-1),s[1].pb(n);

    printf("weigh ");   printSet(s[0]); printf(" vs ");printSet(s[1]); printf("
");

    printf("case <:
");id=s[2][0]; solve2(s[1],s[0],1);

    printf("case =:
");id=s[0][0]; solve1(s[2],1);

    printf("case >:
");id=s[2][0]; solve2(s[0],s[1],1);

    printf("end
");

    return 0;

}