Discussion @ 1152. False Mirrors @ Timus Online Judge

I made full search and got WA. Are there any cases I should check(+) ?

Posted by hajime 12 Mar 2002 04:03

#include <iostream.h>
#include <stdlib.h>
#define MAXN 20

int t[MAXN];
int sum,total;
char b[MAXN]={0};
int n,i,p,j;
int smin;

void solve(int p,int n, int sum, int total){
int i;
    if (p<=3) {
        if (total<smin) smin=total;
    }
else {
    for (i=0;i<n;++i)
    if (!b[i] && !b[(i+1)%n] && !b[(i+2)%n] ) {
       b[i]=b[(i+1)%n]=b[(i+2)%n]=1;
       sum-=t[i]+t[(i+1)%n]+t[(i+2)%n];
       total+=sum;
       solve(p-3,n,sum,total);
       total-=sum;
       sum+=t[i]+t[(i+1)%n]+t[(i+2)%n];
       b[i]=b[(i+1)%n]=b[(i+2)%n]=0;
    }
}
}

int main(){
    sum=total=0;
    cin >>n ;
    for (i=0;i<n;++i) {
        cin >> t[i];
        sum+=t[i];
    }
    smin=sum;
    solve(n,n,sum,0);
    cout << smin << "\n";
    exit(0);
}

Test your program with test data in previous messages.

Posted by MadPsyentist/Sam 12 Mar 2002 08:21

> #include <iostream.h>
> #include <stdlib.h>
> #define MAXN 20
>
> int t[MAXN];
> int sum,total;
> char b[MAXN]={0};
> int n,i,p,j;
> int smin;
>
> void solve(int p,int n, int sum, int total){
> int i;
>     if (p<=3) {
>         if (total<smin) smin=total;
>     }
> else {
>     for (i=0;i<n;++i)
>     if (!b[i] && !b[(i+1)%n] && !b[(i+2)%n] ) {
>        b[i]=b[(i+1)%n]=b[(i+2)%n]=1;
>        sum-=t[i]+t[(i+1)%n]+t[(i+2)%n];
>        total+=sum;
>        solve(p-3,n,sum,total);
>        total-=sum;
>        sum+=t[i]+t[(i+1)%n]+t[(i+2)%n];
>        b[i]=b[(i+1)%n]=b[(i+2)%n]=0;
>     }
> }
> }
>
> int main(){
>     sum=total=0;
>     cin >>n ;
>     for (i=0;i<n;++i) {
>         cin >> t[i];
>         sum+=t[i];
>     }
>     smin=sum;
>     solve(n,n,sum,0);
>     cout << smin << "\n";
>     exit(0);
> }

Thank you for quick answer, I got AC now

Posted by hajime 12 Mar 2002 16:24

> > #include <iostream.h>
> > #include <stdlib.h>
> > #define MAXN 20
> >
> > int t[MAXN];
> > int sum,total;
> > char b[MAXN]={0};
> > int n,i,p,j;
> > int smin;
> >
> > void solve(int p,int n, int sum, int total){
> > int i;
> >     if (p<=3) {
> >         if (total<smin) smin=total;
> >     }
> > else {
> >     for (i=0;i<n;++i)
> >     if (!b[i] && !b[(i+1)%n] && !b[(i+2)%n] ) {
> >        b[i]=b[(i+1)%n]=b[(i+2)%n]=1;
> >        sum-=t[i]+t[(i+1)%n]+t[(i+2)%n];
> >        total+=sum;
> >        solve(p-3,n,sum,total);
> >        total-=sum;
> >        sum+=t[i]+t[(i+1)%n]+t[(i+2)%n];
> >        b[i]=b[(i+1)%n]=b[(i+2)%n]=0;
> >     }
> > }
> > }
> >
> > int main(){
> >     sum=total=0;
> >     cin >>n ;
> >     for (i=0;i<n;++i) {
> >         cin >> t[i];
> >         sum+=t[i];
> >     }
> >     smin=sum;
> >     solve(n,n,sum,0);
> >     cout << smin << "\n";
> >     exit(0);
> > }

I saw you got ac with only 0.17s time. Mine is about 1.8s (10x slower!). Could you send me your ac code? (piyawut@se-ed.net)

Posted by MadPsyentist/Sam 12 Mar 2002 16:35

> > > #include <iostream.h>
> > > #include <stdlib.h>
> > > #define MAXN 20
> > >
> > > int t[MAXN];
> > > int sum,total;
> > > char b[MAXN]={0};
> > > int n,i,p,j;
> > > int smin;
> > >
> > > void solve(int p,int n, int sum, int total){
> > > int i;
> > >     if (p<=3) {
> > >         if (total<smin) smin=total;
> > >     }
> > > else {
> > >     for (i=0;i<n;++i)
> > >     if (!b[i] && !b[(i+1)%n] && !b[(i+2)%n] ) {
> > >        b[i]=b[(i+1)%n]=b[(i+2)%n]=1;
> > >        sum-=t[i]+t[(i+1)%n]+t[(i+2)%n];
> > >        total+=sum;
> > >        solve(p-3,n,sum,total);
> > >        total-=sum;
> > >        sum+=t[i]+t[(i+1)%n]+t[(i+2)%n];
> > >        b[i]=b[(i+1)%n]=b[(i+2)%n]=0;
> > >     }
> > > }
> > > }
> > >
> > > int main(){
> > >     sum=total=0;
> > >     cin >>n ;
> > >     for (i=0;i<n;++i) {
> > >         cin >> t[i];
> > >         sum+=t[i];
> > >     }
> > >     smin=sum;
> > >     solve(n,n,sum,0);
> > >     cout << smin << "\n";
> > >     exit(0);
> > > }

Discussion of Problem 1152. False Mirrors