10911 - Forming Quiz Teams

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10911 - Forming Quiz Teams

Post by brianfry713 » Tue Feb 18, 2014 10:02 pm

Check input and AC output for thousands of problems on uDebug!

vhua_no_name
New poster
Posts: 8
Joined: Sat Dec 21, 2013 8:48 pm

Re: 10911 - Forming Quiz Teams

Post by vhua_no_name » Wed Feb 19, 2014 4:32 pm

thanks brianfry713 for your reply.
here is my code.
its gives the same output for the test cases you have supplied.

Code: Select all

#include <iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
int flag[20];
double t[150000];
class pr{
public:
    int x;
    int y;
};
pr a[20];

double quiz()
{
    double v=100000000,v2,dis;
    int in,k,hsh=0;
    for( k=1;k<=n;k++)
    {
        if(flag[k]==0){
            hsh+=(int)pow(2,k); //calculate hash value for table t
            ///cout<<"inside"<<endl;
            in=k;
        }
    }
    //cout<<"hash:in::"<<hsh<<" "<<in<<endl;
    if(t[hsh]!=-1)
        return t[hsh];

    flag[in]=1;
    for( k=1;k<=n;k++)
    {
        if(flag[k]==0)
        {
            flag[k]=1;
            //dis=sqrt(pow(a[in].x-a[k].x,2)+pow(a[in].y-a[k].y,2));
			dis=hypot(a[in].x-a[k].x, a[in].y-a[k].y);
            v2=quiz();
            flag[k]=0;
            if(dis+v2<v)
                v=dis+v2;
        }
    }
    flag[in]=0;
    t[hsh]=v;
    return v;

}
int main()
{

    char s[25];
    int i,caseno=1;

    while(scanf("%d",&n) && n)
    {
        n=2*n;
        for(i=1;i<=n;i++)
        {
            scanf("%s%d%d",s,&a[i].x,&a[i].y);
            flag[i]=0;
        }

        //sort(a,a+i,fun);
		for(i=1;i<=150000;i++)
            t[i]=-1;
        t[0]=0;
        //cout<<"t:"<<t[10]<<endl;

        double v=quiz();


        printf("Case %d: %.2lf\n",caseno++,v);
    }


    return 0;
}

again thanks for your kind reply.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10911 - Forming Quiz Teams

Post by brianfry713 » Thu Feb 20, 2014 12:08 am

Change line 67 to:
for(i=1;i<150000;i++)
Check input and AC output for thousands of problems on uDebug!

vhua_no_name
New poster
Posts: 8
Joined: Sat Dec 21, 2013 8:48 pm

Re: 10911 - Forming Quiz Teams

Post by vhua_no_name » Thu Feb 20, 2014 3:58 pm

hello brianfry713,
just got AC :D .
I don't know how to thank you.
You are just awesome!
can i have your email address? i am new to uva and i need some suggestion from you.

Post Reply

Return to “Volume 109 (10900-10999)”