11284 - Shopping Trip

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

Moderator: Board moderators

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11284 - Shopping Trip

Post by tryit1 » Tue Nov 18, 2008 11:13 am

My algo is
run floyd to find shortest path.
Run TSP on graph with vertices as opera store1,opera store2 ... with starting as vertex 0.

What is wrong in my code ? I tried all the inputs in the forum and on uvatoolkit . All of them given correct answers from uvatoolkit. Can you please suggest what is wrong in this code ? Any inputs that gets it wrong ?

Code: Select all

Removed after  getting AC thanks darko 
 2 things learnt
1) multiple edges between 2 vertices , so store the smallest cost 
ie 1 3 5 , 1 3 4  , 1 3 6 input , store 1->3 (cost 4)
2) precision precision add EPS, do conversions in integers until end.

Last edited by tryit1 on Tue Nov 18, 2008 7:52 pm, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Re: 11284 - Shopping Trip

Post by Darko » Tue Nov 18, 2008 5:40 pm

There might be more than one road connecting two places. And there is a precision issue there, too.

This is too close to AC, please remove the code after you get it :)

FelixP
New poster
Posts: 3
Joined: Sat Aug 20, 2011 5:48 pm

Re: 11284 - Shopping Trip

Post by FelixP » Sun Aug 21, 2011 7:53 am

Hello, I have tried anything suggested before and still got WA
Here is my code

Code: Select all

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long LL;

#define INF 1000000000
#define PI 3.14159265

#define FOR(i,a,n) for(int i=a,_n=n; i<_n; i++)
#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

#define DEBUG(x) cout << '>' << #x << ':' << x << '\n';

int arr[55][55];
int n_store;
int price[15];  
int memo[1<<12][15];
map <int, int> store;

int f(int aa, int last){
    if ( memo[aa][last] != -1 ) return memo[aa][last];
    
    int ret = 0;
    FOR (i, 0, n_store){
        if ( ( (1<<i) | aa )  == aa ) continue;
        int next = store[i]; int prev = store[last];
        int benefit = f(( 1<<i) | aa, i) + price[i] - arr[prev][next];
        if ( benefit > ret ) ret = benefit;    
    }  
    
    if ( ret == 0 ) ret -= arr[store[last]][0];
    
    return memo[aa][last] = ret;     
}

int main(){
    int t; scanf("%d", &t);
    
    while (t--){
          memset(memo, -1, sizeof memo);
          store.clear();
          FOR (i, 0, 55) FOR (j, 0, 55) arr[i][j] = INF;
          FOR (i, 0, 55) arr[i][i] = 0;
          
          int n, m; scanf("%d %d", &n, &m);
          
          FOR (i, 0, m){
              int a, b, xx, yy;
              scanf("%d %d %d.%d", &a, &b, &xx, &yy);
              int temp = (xx*100) + yy;
              arr[a][b] = min(arr[a][b], temp);
              arr[b][a] = min(arr[b][a], temp);   
          }      
          
          FOR (k, 0, n+1){
              FOR (i, 0, n+1){
                  FOR (j, 0, n+1){
                      arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);    
                  }    
              }    
          }
          
          scanf("%d", &n_store);
          FOR (i, 0, n_store){
              int xx, yy, a;
              scanf("%d %d.%d",&a, &xx, &yy);
              store[i] = a;
              price[i] = (xx*100) + yy;    
          }
          
          int ret = 0; 
          FOR (i, 0, n_store){
              int next = store[i];
              int benefit = f(1<<i, i) + price[i] - arr[0][next];
              if ( benefit > ret )ret = benefit;    
          }
          
          if ( ret <= 0 ) puts("Don't leave the house");
          else{
               int xx = ret/100; int yy = ret%100;
               printf("Daniel can save $%d.%02d\n", xx, yy);     
          }
    }
    
    return 0;
}

Is there any critical input that i might miss? thx before :)

razor
New poster
Posts: 3
Joined: Wed Oct 19, 2011 6:48 pm

Re: 11284 - Shopping Trip

Post by razor » Wed Oct 19, 2011 7:01 pm

@FelixP
For any particular opera, he can opt not to drive to the store to buy it, since he can just order it from Amazon.
May your algorithm didn't cover it.

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 11284 - Shopping Trip

Post by AKJ88 » Wed Feb 13, 2013 11:12 am

I used Floyd then ran tsp on this problem.
I didn't use floats and only worked with integer numbers but still no luck in getting AC. :(
My program outputs the correct answer for sample inputs in the forum and question.
Can anyone give me some input that on which it fails or some hints on the glitch it has???
Thanks in advance.

Code: Select all

#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>

#define INF 100000000

using namespace std;

int N/*stores*/, M/*roads*/, P/*number of DVDs*/, finalMask;
int minDistances[52][52]; //after floyd is done
int memo[14][5000]; //for tsp
int dvdsInfo[15][2]; /* dvd place/amount we can save */

void floyd(){
	int I, J, K;
	for(K=1; K<=N; K++)
		for(I=0; I<=N; I++)
			for(J=0; J<=N; J++)
				minDistances[I][J] = min(minDistances[I][J], minDistances[I][K]+minDistances[K][J]);
}

int tsp(int di, int collDVDs){ //DVD index & collected DVDs
	if(collDVDs == finalMask)
		return minDistances[ dvdsInfo[di][0] ][0]; //returing from last DVDs store to the home
	if(memo[di][collDVDs]!=-1)
		return memo[di][collDVDs];

	int diS=dvdsInfo[di][0], ndS;
	int minDst = INF, dst;
	for(int nd=1; nd<=P; nd++){
		if(nd!=di && !( (1<<nd) & collDVDs )){
			ndS = dvdsInfo[nd][0];
			dst = minDistances[diS][ndS] + tsp(nd, (1<<nd) | collDVDs);
			if(dst<minDst)
				minDst = dst;
		}
	}

	return memo[di][collDVDs] = minDst;
}


int main(){
#ifndef ONLINE_JUDGE
	freopen("J:\\acm\\shoptrip.in", "r", stdin);
	//freopen("J:\\acm\\pricetown.out", "w", stdout);
#endif // !ONLINE_JUDGE
	int TC, f, t, I, J, selDVDs;
	int tmp1, tmp2;
	int maxMoney, dst, diffPrices;
	char fpart[3]={0};

	scanf("%d", &TC);
	dvdsInfo[0][0] = 0;
	while( TC-- ){
		scanf("\n");
		scanf("%d %d", &N, &M);
		//memset(minDistances, 1, sizeof(minDistances));
		memset(memo, -1, sizeof(memo));
		for(I=0; I<=N; I++){
			for(J=0; J<=N; J++)
				minDistances[I][J] = INF;
			minDistances[I][I] = 0;
		}

		for(I=0; I<M; I++){
			scanf("%d %d", &f, &t);
			scanf("%d.%d", &tmp1, &tmp2);
			tmp1 = 100*tmp1 + tmp2;
			if(minDistances[f][t] > tmp1)
				minDistances[t][f] = minDistances[f][t] = tmp1;
		}

		scanf("%d", &P);
		for(I=1; I<=P; I++){
			scanf("%d %d.%d", &dvdsInfo[I][0], &tmp1, &tmp2);
			dvdsInfo[I][1] = 100*tmp1 + tmp2;
		}
		floyd();

		maxMoney = 0;
		finalMask = (1<<(P+1))-1;
		for(I=1; I<finalMask-1; I++){
			dst = tsp(0, (I | 1));
			diffPrices = 0;

			for(J=1; J<=P; J++)
				if( !(I & (1<<J)) )
					diffPrices += dvdsInfo[J][1];

			diffPrices -= dst;
			if(diffPrices>maxMoney)
				maxMoney = diffPrices;
		}

		if(maxMoney > 0 && maxMoney<INF){
			tmp1 = maxMoney/100;
			maxMoney%=100;
			fpart[0] = (maxMoney/10)+'0';
			fpart[1] = (maxMoney%10)+'0';
			printf("Daniel can save $%d.%s\n", tmp1, fpart );
		}else
			printf("Don't leave the house\n");
	}

	return 0;
}


User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Re: 11284 - Shopping Trip

Post by fh » Wed Feb 13, 2013 6:25 pm

@AKJ88: try this input:

Code: Select all

1
2 3
0 1 1.00
0 2 1.00
2 3 10.00
2
1 2.01
2 2.01
The output should be:

Code: Select all

Daniel can save $0.02
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 11284 - Shopping Trip

Post by AKJ88 » Thu Feb 14, 2013 10:35 am

@felix_halim
Thanks for your reply, I didn't take into account situations that he could buy sth, come back home and go for another shop!!!:)
Now I handle these cases correctly but still no luck! Sorry to bother you but would you please give me another test case for which my program fails???
Thanks in advance.
My new code is here:

Code: Select all

#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>

#define INF 10000000

using namespace std;

int N/*stores*/, M/*roads*/, P/*number of DVDs*/, finalMask;
int minDistances[52][52]; //after floyd is done
int memo[14][5000]; //for tsp
int dvdsInfo[15][2]; /* dvd place/amount we can save */

void floyd(){
	int I, J, K;
	for(K=1; K<=N; K++)
		for(I=0; I<=N; I++)
			for(J=0; J<=N; J++)
				minDistances[I][J] = min(minDistances[I][J], minDistances[I][K]+minDistances[K][J]);
}

int tsp(int di, int collDVDs){ //DVD index & collected DVDs
	if(collDVDs == finalMask)
		return minDistances[ dvdsInfo[di][0] ][0]; //returing from last DVDs store to the home
	if(memo[di][collDVDs]!=-1)
		return memo[di][collDVDs];

	int diS=dvdsInfo[di][0], ndS;
	int minDst = INF, dst;
	for(int nd=1; nd<=P; nd++){
		if(nd!=di && !( (1<<nd) & collDVDs )){
			ndS = dvdsInfo[nd][0];
			dst = minDistances[diS][ndS] + tsp(nd, (1<<nd) | collDVDs);
			if(dst<minDst)
				minDst = dst;
		}
	}

	return memo[di][collDVDs] = minDst;
}


int main(){
#ifndef ONLINE_JUDGE
	freopen("J:\\acm\\shoptrip.in", "r", stdin);
	//freopen("J:\\acm\\pricetown.out", "w", stdout);
#endif // !ONLINE_JUDGE
	int TC, f, t, I, nI, J, selDVDs;
	int tmp1, tmp2;
	int maxMoney, dst1, dst2, diffPrices1, diffPrices2, diffPrices;
	char fpart[3]={0};

	scanf("%d", &TC);
	dvdsInfo[0][0] = 0;
	while( TC-- ){
		scanf("\n");
		scanf("%d %d", &N, &M);
		memset(memo, -1, sizeof(memo));
		for(I=0; I<=N; I++){
			for(J=0; J<=N; J++)
				minDistances[I][J] = INF;
			minDistances[I][I] = 0;
		}

		for(I=0; I<M; I++){
			scanf("%d %d", &f, &t);
			scanf("%d.%d", &tmp1, &tmp2);
			tmp1 = 100*tmp1 + tmp2;
			if(minDistances[f][t] > tmp1)
				minDistances[t][f] = minDistances[f][t] = tmp1;
		}

		scanf("%d", &P);
		for(I=1; I<=P; I++){
			scanf("%d %d.%d", &dvdsInfo[I][0], &tmp1, &tmp2);
			dvdsInfo[I][1] = 100*tmp1 + tmp2;
		}
		floyd();

		maxMoney = 0;
		finalMask = (1<<(P+1))-1;
		for(I=1; I<finalMask-1; I++){
			dst1 = tsp(0, I|1);
			nI = ~I & finalMask;
			dst2 = tsp(0, nI|1);

			diffPrices1 = 0;
			diffPrices2 = 0;
			for(J=1; J<=P; J++)
				if( !(I & (1<<J)) )
					diffPrices1 += dvdsInfo[J][1];
				else if( !(nI & (1<<J)) )
					diffPrices2 += dvdsInfo[J][1];

			if(dst1 > 0)
				diffPrices1 -= dst1;
			if(dst2 > 0)
				diffPrices2 -= dst2;
			diffPrices = 0;
			if(diffPrices1 > 0)
				diffPrices += diffPrices1;
			if(diffPrices2 > 0)
				diffPrices += diffPrices2;
			if(diffPrices>maxMoney)
				maxMoney = diffPrices;
		}

		if(maxMoney > 0 && maxMoney<INF){
			tmp1 = maxMoney/100;
			maxMoney%=100;
			fpart[0] = (maxMoney/10)+'0';
			fpart[1] = (maxMoney%10)+'0';
			printf("Daniel can save $%d.%s\n", tmp1, fpart );
		}else
			printf("Don't leave the house\n");
	}

	return 0;
}


User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Re: 11284 - Shopping Trip

Post by fh » Thu Feb 14, 2013 4:26 pm

You haven't solved the coming home problem:

Code: Select all

1
3 3
0 1 1.00
0 2 1.00
0 3 1.00
3
1 2.01
2 2.01
3 2.01

Code: Select all

Daniel can save $0.03
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 11284 - Shopping Trip

Post by a.elbashandy » Wed Jul 31, 2013 4:36 am

I keep getting WA, help please !!

Code: Select all


#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

using namespace std;


int n, m, p, storeIndex[15];
double dist[55][55], memo[55][1 << 13], storesDVD[15];

double tsp(int pos, int bitmask) {
    if (bitmask == (1 << (p + 1)) - 1)
        return dist[pos][0] * -1.0;
    if (memo[pos][bitmask] != -1) return memo[pos][bitmask];


    double ans = INF_MIN, temp, temp1, temp2;

    for (int i = 0; i <= p; i++) {
        if (!isOn(bitmask, i)) {
            int dIn = storeIndex[i];
            double d = dist[pos][storeIndex[i]];
            double storePrice = storesDVD[storeIndex[i]];
            temp = storesDVD[storeIndex[i]] - dist[pos][storeIndex[i]];
            temp1 = temp + tsp(storeIndex[i], bitmask | (1 << i));
            ans = max(ans, temp1);

        }
    }

    temp2 = tsp(pos, (1 << (p + 1)) - 1);
    ans = max(ans, temp2);

    return memo[pos][bitmask] = ans;
}

int main(int argc, char** argv) {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                dist[i][j] = INF_MAX;

        Set(storesDVD, 0);
        Set(storeIndex, 0);

        for (int i = 0; i < 55; i++)
            for (int j = 0; j < (1 << 13); j++)
                memo[i][j] = -1;

        int a, b;
        double cost;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %lf", &a, &b, &cost);
            dist[a][b] = min(dist[a][b], cost);
            dist[b][a] = min(dist[b][a], cost);
        }

        for (int k = 0; k <= n; k++)
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= n; j++)
                    if (dist[i][k] != INF_MAX && dist[k][j] != INF_MAX) {
                        if (i == j)
                            dist[i][j] = 0;
                        else
                            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }


        double totalSaved = 0;
        scanf("%d", &p);
        int countRep = 0;
        for (int i = 1; i <= p; i++) {
            scanf("%d %lf", &a, &cost);
            if (storesDVD[a]) {
                countRep++;
            }else
                storeIndex[i - countRep] = a;
            storesDVD[a] += cost;
            totalSaved += cost;
        }
        
        p -= countRep;

        double ans = tsp(0, 1);

        if (ans <= 0)
            printf("Don't leave the house\n");
        else
            printf("Daniel can save $%.2lf\n", ans);
    }
    return 0;
}


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

Re: 11284 - Shopping Trip

Post by brianfry713 » Wed Jul 31, 2013 8:32 am

try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 11284 - Shopping Trip

Post by a.elbashandy » Wed Jul 31, 2013 4:18 pm

@brianfry Still WA :(

Code: Select all

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

using namespace std;

/*
 * 
 */

int n, m, p, storeIndex[15];
long long dist[55][55], memo[55][1 << 13], storesDVD[15];

long long tsp(int pos, int bitmask) {
    if (bitmask == (1 << (p + 1)) - 1)
        return dist[pos][0] * -1;
    if (memo[pos][bitmask] != -1) return memo[pos][bitmask];


    long long ans = INF_MIN, temp, temp1, temp2;

    for (int i = 0; i <= p; i++) {
        if (!isOn(bitmask, i)) {
            int dIn = storeIndex[i];
            long long d = dist[pos][storeIndex[i]];
            long long storePrice = storesDVD[storeIndex[i]];
            temp = storesDVD[storeIndex[i]] - dist[pos][storeIndex[i]];
            temp1 = temp + tsp(storeIndex[i], bitmask | (1 << i));
            ans = max(ans, temp1);

        }
    }

    temp2 = tsp(pos, (1 << (p + 1)) - 1);
    ans = max(ans, temp2);

    return memo[pos][bitmask] = ans;
}

int main(int argc, char** argv) {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                dist[i][j] = INF_MAX;

        Set(storesDVD, 0);
        Set(storeIndex, 0);

        for (int i = 0; i < 55; i++)
            for (int j = 0; j < (1 << 13); j++)
                memo[i][j] = -1;




        int a, b, c, d;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d.%d", &a, &b, &c, &d);
            long long x = 100 * c + d;
            dist[a][b] = min(dist[a][b], x);
            dist[b][a] = min(dist[b][a], x);
        }

        for (int k = 0; k <= n; k++)
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= n; j++)
                    if (dist[i][k] != INF_MAX && dist[k][j] != INF_MAX) {
                        if (i == j)
                            dist[i][j] = 0;
                        else
                            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }


        double totalSaved = 0;
        scanf("%d", &p);
        int countRep = 0;
        for (int i = 1; i <= p; i++) {
            scanf("%d %d.%d", &a, &c, &d);
            if (storesDVD[a]) {
                countRep++;
            }else
                storeIndex[i - countRep] = a;
            long long x = 100 * c + d;
            storesDVD[a] += x;
            totalSaved += x;
        }
        
        p -= countRep;

        long long ans = tsp(0, 1);
        
        if (ans <= 0)
            printf("Don't leave the house\n");
        else{
            int ansMod = ans % 100;
            int div = ans/100;
            printf("Daniel can save $%d.%02d\n", div, ansMod);
        }
    }
    return 0;
}

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

Re: 11284 - Shopping Trip

Post by brianfry713 » Wed Jul 31, 2013 8:14 pm

From uhunt:
AKJ88> a.elbashandy, I thinks I realized the reason you get WA. Store numbers and those which have dvds are somehow mixed in your code. In your tsp function you use both pos and storesindex for getting dist. pos is not always a dvd store
AKJ88> unless you make an extra matrix for saving minimum distance between dvd stores and don't use dist matrix.
Check input and AC output for thousands of problems on uDebug!

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 11284 - Shopping Trip

Post by a.elbashandy » Thu Aug 01, 2013 5:13 am

AKJ88 Yes i use extra matrix for saving minimum distance between dvd stores and the initial position only

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

Re: 11284 - Shopping Trip

Post by brianfry713 » Fri Aug 02, 2013 12:14 am

Input:

Code: Select all

10

34 300
0 1 2.57
0 2 1.93
1 2 8.70
0 3 5.17
2 3 8.69
0 4 2.22
1 4 5.73
2 4 2.31
1 5 9.82
2 5 8.92
3 5 7.57
0 6 3.21
4 6 9.74
0 7 8.47
4 7 2.31
5 7 9.37
6 7 9.54
0 8 9.98
4 8 8.81
5 8 8.16
6 8 1.31
7 8 5.96
0 9 5.38
2 9 1.18
3 9 1.70
4 9 4.12
5 9 2.77
7 9 4.36
8 9 4.76
1 10 8.07
3 10 8.57
5 10 4.99
8 10 5.27
9 10 8.36
2 11 3.18
3 11 4.63
4 11 4.44
6 11 3.05
7 11 7.91
9 11 1.55
0 12 2.89
1 12 9.93
3 12 8.05
5 12 2.22
7 12 3.17
9 12 3.93
11 12 5.26
0 13 4.86
1 13 7.43
7 13 7.14
8 13 9.79
10 13 9.62
1 14 4.88
6 14 9.10
7 14 3.94
11 14 3.46
12 14 1.37
13 14 3.53
1 15 3.73
2 15 8.25
6 15 1.10
9 15 1.17
10 15 3.63
11 15 9.90
13 15 7.30
0 16 7.71
1 16 4.33
2 16 4.89
3 16 5.04
4 16 5.05
5 16 9.68
6 16 9.85
7 16 9.95
8 16 6.49
9 16 3.67
11 16 4.63
12 16 1.96
14 16 4.65
0 17 6.36
3 17 1.70
5 17 7.11
6 17 2.32
7 17 1.79
11 17 6.70
12 17 6.72
14 17 2.34
16 17 6.83
0 18 2.98
2 18 9.63
3 18 4.50
4 18 9.73
5 18 1.59
9 18 6.47
11 18 7.82
14 18 2.32
1 19 1.54
2 19 4.98
3 19 5.40
4 19 6.59
5 19 4.62
8 19 8.41
9 19 3.23
11 19 4.72
12 19 4.54
14 19 9.21
15 19 1.65
17 19 9.71
18 19 5.69
0 20 2.01
1 20 6.53
4 20 7.07
5 20 9.28
7 20 4.97
10 20 7.84
11 20 2.34
12 20 7.91
17 20 6.98
0 21 9.52
1 21 9.89
2 21 7.06
5 21 8.16
7 21 4.09
9 21 5.00
11 21 1.09
14 21 5.81
15 21 9.38
18 21 8.26
19 21 8.47
1 22 9.87
2 22 9.32
3 22 4.81
6 22 5.50
9 22 8.90
10 22 4.50
11 22 7.13
16 22 3.94
18 22 4.81
19 22 9.20
20 22 9.82
0 23 3.87
6 23 4.96
10 23 5.04
13 23 7.92
19 23 2.97
20 23 4.34
0 24 2.06
1 24 9.57
2 24 5.95
4 24 8.62
7 24 5.83
8 24 6.54
9 24 7.09
10 24 9.32
12 24 4.21
13 24 5.63
14 24 1.82
17 24 8.85
23 24 8.85
3 25 4.90
4 25 5.14
6 25 5.16
8 25 1.92
9 25 2.28
13 25 1.25
14 25 1.36
18 25 3.18
20 25 8.37
21 25 1.82
23 25 2.10
24 25 3.88
0 26 2.15
1 26 3.37
3 26 6.08
4 26 8.83
6 26 7.57
7 26 1.27
9 26 8.69
16 26 1.51
17 26 4.10
19 26 6.39
0 27 2.88
2 27 7.93
6 27 4.90
11 27 2.99
12 27 3.31
13 27 9.77
14 27 5.57
17 27 8.52
20 27 2.41
21 27 6.68
22 27 1.84
25 27 3.76
0 28 5.66
2 28 5.54
3 28 3.08
4 28 1.78
5 28 5.55
7 28 8.74
8 28 3.00
11 28 8.97
17 28 2.12
21 28 6.82
26 28 8.93
0 29 5.39
2 29 9.21
3 29 1.85
4 29 3.54
8 29 5.62
11 29 5.41
12 29 2.52
16 29 3.62
17 29 7.99
19 29 6.54
20 29 1.15
21 29 1.51
22 29 2.90
23 29 6.91
26 29 6.37
1 30 8.59
2 30 9.71
6 30 9.87
10 30 6.90
16 30 1.70
17 30 5.65
18 30 5.69
19 30 9.61
22 30 3.51
24 30 3.00
25 30 7.38
26 30 4.64
28 30 9.32
29 30 7.04
1 31 8.79
3 31 6.12
4 31 2.69
6 31 3.70
7 31 1.44
9 31 8.49
10 31 4.65
11 31 3.26
12 31 7.83
13 31 2.69
16 31 5.52
17 31 7.93
18 31 9.89
19 31 8.31
22 31 1.64
23 31 1.48
24 31 6.77
26 31 3.33
30 31 6.49
2 32 5.55
5 32 9.68
6 32 4.60
7 32 5.23
8 32 5.71
9 32 5.77
11 32 7.45
13 32 3.61
14 32 2.23
19 32 9.00
22 32 2.75
25 32 3.42
1 33 7.59
4 33 5.89
6 33 3.69
8 33 1.51
9 33 3.83
10 33 6.33
11 33 2.04
14 33 7.81
16 33 6.66
20 33 8.67
22 33 9.92
23 33 3.02
25 33 3.31
26 33 6.74
28 33 7.18
29 33 3.83
2 34 2.87
5 34 9.73
6 34 4.62
7 34 4.33
8 34 7.96
9 34 6.41
11 34 6.26
12 34 1.80
13 34 1.85
15 34 3.05
16 34 6.29
17 34 5.98
18 34 2.62
19 34 1.19
20 34 4.41
22 34 8.10
24 34 6.26
25 34 2.89
27 34 5.08
30 34 2.38
33 34 4.93
7
20 6.39
33 5.42
7 5.86
19 2.49
4 1.86
23 6.11
15 6.33

23 156
0 1 6.54
0 2 4.06
1 2 1.03
0 3 1.84
0 4 8.97
2 4 2.33
3 4 1.60
1 5 3.14
3 5 6.97
4 5 8.97
1 6 6.29
2 6 2.13
4 6 2.34
5 6 6.14
0 7 6.75
1 7 3.86
2 7 4.26
3 7 2.16
4 7 4.69
6 7 2.09
0 8 1.15
2 8 5.33
3 8 4.76
5 8 9.13
0 9 4.00
1 9 1.86
2 9 5.63
3 9 4.08
6 9 6.16
8 9 2.82
0 10 6.40
1 10 1.26
3 10 3.65
5 10 9.99
7 10 8.46
9 10 8.53
0 11 9.03
1 11 7.42
3 11 5.34
7 11 2.10
10 11 8.69
0 12 3.15
2 12 2.96
8 12 7.82
9 12 4.51
10 12 4.61
11 12 7.37
0 13 8.61
2 13 3.81
3 13 3.88
4 13 4.20
5 13 7.93
6 13 8.28
9 13 7.08
10 13 3.42
11 13 8.96
0 14 7.66
1 14 2.00
2 14 4.87
3 14 8.32
6 14 2.50
8 14 5.33
9 14 5.80
10 14 5.93
12 14 6.54
13 14 6.44
6 15 4.23
7 15 3.51
9 15 9.73
12 15 3.65
14 15 3.81
1 16 9.83
2 16 5.77
3 16 4.14
6 16 6.69
8 16 4.07
9 16 2.91
11 16 1.11
13 16 7.87
14 16 9.36
1 17 1.39
2 17 9.20
4 17 3.71
5 17 1.18
10 17 7.34
13 17 8.64
16 17 9.97
0 18 8.67
1 18 6.35
2 18 1.90
3 18 7.32
6 18 5.29
11 18 9.90
12 18 2.47
14 18 8.49
15 18 6.22
16 18 4.68
3 19 7.55
5 19 4.66
6 19 2.36
7 19 8.60
9 19 8.20
10 19 7.04
11 19 9.83
14 19 2.21
17 19 2.97
18 19 1.27
0 20 3.28
2 20 9.70
5 20 6.98
6 20 5.63
7 20 2.60
9 20 5.16
12 20 9.23
13 20 5.92
14 20 7.35
15 20 8.63
17 20 8.62
19 20 5.95
1 21 6.60
2 21 2.76
3 21 9.73
4 21 2.87
5 21 1.73
7 21 4.81
8 21 6.29
9 21 4.44
10 21 2.80
11 21 5.09
13 21 5.47
15 21 7.66
16 21 9.59
17 21 9.42
18 21 1.01
20 21 7.71
0 22 5.58
1 22 9.22
5 22 7.55
12 22 3.90
14 22 6.71
16 22 9.03
17 22 3.20
21 22 8.42
1 23 9.12
3 23 3.07
5 23 9.58
10 23 3.94
11 23 5.58
13 23 2.90
14 23 4.26
16 23 5.73
17 23 5.65
18 23 8.21
19 23 9.09
20 23 5.00
22 23 7.86
2
19 1.99
7 2.00

8 22
0 1 4.30
0 2 3.63
1 2 9.20
0 3 8.38
1 3 6.92
2 3 8.22
0 4 2.85
1 4 3.94
2 5 5.08
4 5 6.02
0 6 8.84
3 6 1.87
4 6 2.57
5 6 8.02
1 7 1.48
2 7 7.86
3 7 1.40
1 8 5.51
2 8 4.56
3 8 9.54
4 8 8.72
5 8 1.82
1
7 4.14

33 286
0 1 3.91
1 2 8.74
0 3 9.56
1 3 1.61
0 4 2.38
1 4 1.02
0 5 1.48
1 6 4.66
2 6 8.42
3 6 8.42
4 6 4.59
5 6 4.61
4 7 7.96
5 7 1.06
6 7 1.56
0 8 8.35
1 8 8.54
2 8 5.44
4 8 6.02
5 8 4.32
7 8 2.51
0 9 8.71
1 9 3.04
4 9 5.89
5 9 1.39
8 9 6.82
1 10 8.72
2 10 9.86
4 10 9.19
6 10 5.18
7 10 2.57
1 11 5.75
5 11 5.15
6 11 2.25
9 11 7.77
10 11 5.09
0 12 4.95
2 12 1.31
3 12 9.22
5 12 5.46
9 12 6.56
10 12 1.64
0 13 2.24
4 13 5.48
5 13 2.94
8 13 4.72
9 13 7.72
10 13 1.67
0 14 6.19
1 14 9.09
2 14 5.54
3 14 9.28
4 14 4.55
5 14 2.50
8 14 2.31
11 14 8.42
1 15 7.77
2 15 7.68
7 15 2.08
9 15 5.98
11 15 8.87
12 15 4.07
13 15 4.69
0 16 1.03
3 16 3.71
4 16 8.88
5 16 3.86
7 16 2.76
9 16 4.27
10 16 5.22
12 16 7.26
13 16 3.99
15 16 6.23
3 17 8.58
5 17 8.88
8 17 8.87
9 17 8.30
13 17 4.39
15 17 2.72
16 17 7.92
0 18 4.06
2 18 9.22
8 18 9.49
10 18 6.86
13 18 9.76
14 18 7.87
15 18 8.26
16 18 5.58
17 18 4.58
3 19 7.81
4 19 1.28
6 19 3.74
7 19 3.14
9 19 6.62
10 19 9.56
11 19 6.35
14 19 3.34
17 19 5.60
0 20 1.07
3 20 2.64
7 20 9.55
8 20 1.37
9 20 2.42
10 20 1.83
11 20 6.68
12 20 1.46
13 20 1.37
14 20 3.59
17 20 5.87
18 20 4.42
19 20 8.75
0 21 5.10
1 21 9.86
3 21 7.97
4 21 1.17
5 21 7.28
7 21 3.17
10 21 6.58
13 21 2.66
14 21 2.59
15 21 1.09
16 21 4.35
17 21 3.30
18 21 8.02
20 21 1.16
0 22 2.13
6 22 7.74
7 22 7.06
9 22 3.94
11 22 5.06
12 22 8.17
14 22 9.39
18 22 5.52
19 22 9.93
0 23 8.42
1 23 2.05
2 23 1.13
6 23 5.02
8 23 7.87
9 23 8.61
12 23 1.01
16 23 5.48
17 23 3.50
19 23 3.39
21 23 2.09
0 24 4.11
1 24 2.80
7 24 8.12
8 24 3.52
9 24 1.03
10 24 5.61
11 24 5.50
12 24 5.52
14 24 8.71
16 24 9.57
17 24 7.48
19 24 1.11
20 24 6.37
22 24 2.54
23 24 3.61
1 25 8.74
2 25 1.42
5 25 5.26
6 25 6.39
8 25 3.64
11 25 4.25
13 25 6.02
14 25 2.04
15 25 7.80
20 25 1.46
0 26 1.60
1 26 5.00
6 26 7.42
7 26 1.88
8 26 4.19
9 26 6.12
10 26 6.25
11 26 8.48
14 26 4.60
16 26 4.82
17 26 7.29
19 26 1.02
21 26 6.86
5 27 4.37
6 27 7.34
9 27 6.09
10 27 8.30
11 27 6.69
15 27 8.51
16 27 8.73
18 27 5.58
19 27 8.64
20 27 9.39
21 27 7.86
23 27 6.03
4 28 6.76
5 28 6.27
8 28 4.67
10 28 5.37
11 28 4.33
12 28 6.92
13 28 5.17
17 28 7.55
19 28 5.00
22 28 4.47
24 28 9.77
0 29 5.59
2 29 7.92
3 29 8.57
4 29 4.02
6 29 3.47
9 29 5.44
10 29 1.61
11 29 1.92
12 29 3.68
13 29 3.21
17 29 8.71
19 29 8.87
25 29 5.80
27 29 3.86
0 30 5.13
1 30 4.36
5 30 6.09
6 30 2.74
8 30 3.59
9 30 5.27
10 30 3.60
14 30 1.84
15 30 6.35
20 30 5.24
23 30 1.58
25 30 3.15
26 30 1.88
28 30 9.61
2 31 3.42
6 31 9.00
7 31 2.62
10 31 3.31
12 31 9.17
13 31 8.38
15 31 8.87
17 31 4.34
18 31 9.40
20 31 7.72
21 31 3.51
22 31 9.82
23 31 5.94
27 31 8.92
28 31 2.53
29 31 3.02
30 31 3.52
0 32 6.55
1 32 1.91
2 32 8.38
3 32 9.44
4 32 8.88
5 32 6.45
6 32 3.34
9 32 4.44
10 32 6.65
12 32 9.55
14 32 5.06
19 32 4.97
21 32 2.83
23 32 4.03
24 32 6.50
25 32 5.92
26 32 8.21
31 32 4.91
0 33 3.95
3 33 9.39
4 33 7.23
5 33 8.57
6 33 6.26
7 33 8.65
10 33 5.50
13 33 2.90
16 33 7.22
18 33 6.58
19 33 9.90
22 33 3.95
23 33 4.68
24 33 9.97
27 33 8.75
28 33 6.53
32 33 4.29
3
10 2.95
24 8.50
32 6.66

7 22
0 1 1.99
1 2 9.79
0 3 8.18
1 3 7.07
2 3 3.56
0 4 1.12
1 4 8.74
3 4 8.76
0 5 9.19
2 5 2.46
3 5 4.39
0 6 4.12
2 6 7.28
4 6 2.65
5 6 9.30
0 7 8.72
1 7 9.61
2 7 8.18
3 7 6.83
4 7 3.56
5 7 3.44
6 7 5.52
3
2 6.75
1 7.94
3 5.59

50 677
0 1 7.33
1 2 8.27
1 3 9.05
2 3 2.49
1 4 2.78
1 5 7.57
2 5 9.36
3 5 7.85
4 5 6.03
0 6 7.47
1 6 4.41
2 6 3.94
3 6 7.54
5 6 2.94
0 7 4.76
2 7 6.45
3 7 8.18
6 7 8.92
0 8 6.21
1 8 2.39
2 8 5.03
3 8 1.09
5 8 9.23
0 9 8.49
1 9 7.11
4 9 4.59
5 9 2.90
7 9 8.42
1 10 1.05
2 10 2.72
3 10 9.07
6 10 1.94
8 10 6.43
9 10 2.53
1 11 5.79
2 11 4.67
6 11 8.40
8 11 6.74
9 11 9.23
10 11 1.45
0 12 5.72
1 12 4.39
3 12 4.10
5 12 1.10
6 12 7.23
7 12 5.00
8 12 4.53
9 12 3.60
10 12 3.32
1 13 6.12
4 13 4.57
6 13 9.94
8 13 3.59
9 13 7.16
10 13 4.95
12 13 6.21
2 14 5.66
3 14 3.86
5 14 7.46
7 14 9.44
8 14 1.84
9 14 9.56
10 14 8.91
11 14 9.85
13 14 1.81
0 15 1.87
2 15 3.80
3 15 3.91
4 15 9.53
5 15 3.26
6 15 6.68
8 15 9.73
9 15 3.11
10 15 5.64
14 15 9.08
2 16 1.31
4 16 6.57
5 16 9.33
7 16 6.55
8 16 7.25
9 16 8.67
11 16 7.78
12 16 4.46
13 16 9.91
14 16 8.28
2 17 4.04
4 17 5.68
6 17 9.84
8 17 2.89
10 17 3.89
11 17 6.60
12 17 8.94
13 17 1.12
14 17 9.19
16 17 8.46
1 18 1.08
2 18 2.60
3 18 3.17
7 18 6.60
9 18 4.10
11 18 9.29
12 18 3.38
13 18 5.92
17 18 1.28
0 19 4.74
1 19 4.30
2 19 4.43
3 19 6.56
8 19 2.04
12 19 9.27
13 19 9.75
15 19 2.19
17 19 3.27
18 19 1.94
1 20 2.44
2 20 9.76
3 20 6.19
4 20 4.22
6 20 9.40
7 20 4.96
10 20 2.21
11 20 7.05
14 20 5.55
17 20 8.71
0 21 4.41
3 21 2.13
10 21 4.87
12 21 8.04
14 21 3.21
19 21 3.01
20 21 1.55
1 22 1.91
2 22 7.96
4 22 7.89
5 22 3.16
8 22 4.03
12 22 6.16
14 22 8.05
15 22 9.22
18 22 2.86
0 23 8.28
3 23 1.83
4 23 2.83
9 23 4.29
11 23 4.39
13 23 3.22
14 23 5.12
16 23 1.21
19 23 5.82
20 23 4.46
21 23 5.00
22 23 1.40
6 24 6.62
8 24 6.43
9 24 9.75
10 24 3.03
11 24 5.80
12 24 6.18
14 24 8.26
15 24 5.72
17 24 5.81
18 24 6.60
19 24 2.63
20 24 6.55
23 24 8.43
0 25 2.96
2 25 5.54
4 25 9.63
9 25 5.35
11 25 3.56
12 25 7.87
15 25 1.65
16 25 5.46
17 25 6.83
19 25 5.34
21 25 2.38
22 25 7.53
23 25 6.09
0 26 1.83
1 26 9.61
2 26 9.69
4 26 9.74
5 26 1.99
6 26 4.44
8 26 9.48
12 26 9.96
13 26 6.60
15 26 6.55
19 26 3.96
20 26 8.31
24 26 2.97
1 27 6.97
2 27 3.23
4 27 2.18
6 27 8.75
7 27 7.84
10 27 9.41
12 27 1.69
13 27 9.00
14 27 4.26
21 27 3.66
23 27 5.35
25 27 8.87
26 27 4.37
8 28 1.32
11 28 7.65
15 28 7.41
17 28 5.31
20 28 9.22
26 28 7.70
0 29 5.81
1 29 5.94
2 29 7.17
10 29 4.15
11 29 3.81
12 29 5.17
13 29 8.68
15 29 2.26
16 29 6.47
19 29 5.91
22 29 3.84
23 29 2.61
2 30 1.71
4 30 4.42
5 30 1.94
7 30 5.95
8 30 5.72
10 30 8.02
12 30 2.05
13 30 9.59
14 30 5.10
15 30 7.85
17 30 7.85
21 30 5.86
22 30 3.80
24 30 4.17
25 30 8.85
28 30 8.42
3 31 9.75
8 31 6.54
10 31 1.02
11 31 2.49
15 31 8.91
16 31 6.67
17 31 7.20
18 31 9.86
19 31 4.07
20 31 1.13
21 31 3.87
24 31 8.29
26 31 2.80
27 31 6.32
30 31 5.77
0 32 6.27
2 32 3.63
5 32 1.26
6 32 1.35
7 32 5.43
9 32 9.31
11 32 2.26
12 32 3.89
14 32 4.87
16 32 4.35
17 32 1.41
18 32 5.04
19 32 9.42
23 32 1.17
27 32 5.02
29 32 4.53
30 32 7.50
0 33 1.63
1 33 6.86
3 33 7.57
5 33 6.76
7 33 8.40
11 33 1.92
12 33 5.18
14 33 9.78
16 33 4.84
17 33 4.80
18 33 8.42
19 33 4.76
20 33 2.49
22 33 9.57
23 33 4.60
25 33 7.71
26 33 1.88
27 33 4.73
29 33 1.38
30 33 9.86
31 33 3.55
32 33 6.13
2 34 8.62
3 34 5.79
4 34 5.63
7 34 7.90
8 34 6.82
9 34 7.16
11 34 4.97
12 34 1.86
13 34 8.84
15 34 9.85
18 34 8.18
19 34 2.70
21 34 6.12
25 34 7.88
29 34 7.39
30 34 5.93
31 34 4.44
32 34 1.51
33 34 3.84
0 35 9.64
2 35 3.59
3 35 4.02
8 35 1.57
9 35 9.19
10 35 8.02
11 35 3.15
12 35 6.67
13 35 3.30
14 35 2.46
16 35 2.52
20 35 7.71
22 35 6.90
26 35 3.70
27 35 8.27
28 35 2.86
29 35 1.76
33 35 2.76
0 36 6.06
2 36 3.72
3 36 5.27
5 36 1.86
6 36 5.47
7 36 6.32
11 36 7.37
14 36 2.47
17 36 8.15
20 36 2.87
21 36 6.38
22 36 9.98
26 36 4.15
27 36 8.12
29 36 1.81
30 36 2.22
31 36 4.26
33 36 9.17
34 36 1.21
35 36 4.00
2 37 5.09
4 37 8.98
5 37 3.14
6 37 7.88
7 37 5.16
9 37 4.38
10 37 5.36
13 37 2.75
14 37 8.24
15 37 5.46
16 37 5.28
19 37 6.97
20 37 8.67
23 37 5.11
24 37 3.22
25 37 2.09
26 37 5.47
27 37 4.82
28 37 8.04
30 37 6.94
33 37 4.01
34 37 1.78
1 38 7.72
2 38 4.92
3 38 6.41
5 38 3.54
6 38 5.59
7 38 5.27
11 38 8.70
12 38 9.67
13 38 2.02
14 38 4.28
17 38 8.35
18 38 9.15
19 38 6.84
21 38 4.64
23 38 1.46
24 38 6.74
25 38 1.48
26 38 8.15
27 38 7.57
30 38 1.62
31 38 4.24
33 38 1.95
35 38 1.80
36 38 2.40
0 39 5.43
3 39 6.83
4 39 8.31
5 39 3.23
6 39 5.60
8 39 1.53
9 39 8.82
12 39 1.24
15 39 4.46
16 39 2.24
19 39 7.64
20 39 8.23
21 39 3.28
22 39 1.36
25 39 3.86
26 39 2.42
27 39 3.96
29 39 4.64
30 39 7.76
33 39 3.47
35 39 2.79
36 39 7.94
37 39 7.31
38 39 4.44
0 40 2.62
1 40 7.32
4 40 3.08
6 40 4.68
7 40 8.27
11 40 5.49
12 40 4.32
13 40 1.46
15 40 2.73
17 40 5.60
21 40 9.50
24 40 1.38
26 40 6.11
28 40 5.43
29 40 8.04
36 40 6.24
3 41 9.60
4 41 3.97
7 41 3.64
9 41 2.09
10 41 9.69
13 41 8.60
14 41 8.53
15 41 5.34
16 41 9.22
18 41 3.29
19 41 9.05
20 41 6.54
21 41 7.04
22 41 1.62
23 41 7.40
24 41 1.79
29 41 7.95
30 41 2.69
32 41 5.42
33 41 8.07
34 41 5.40
35 41 3.17
37 41 2.78
38 41 7.73
2 42 2.97
3 42 8.25
4 42 2.73
6 42 2.22
10 42 9.80
11 42 1.38
12 42 8.23
14 42 9.21
15 42 2.46
16 42 2.33
18 42 9.25
19 42 6.03
20 42 4.60
22 42 3.12
23 42 1.23
24 42 3.39
27 42 8.39
30 42 7.74
34 42 9.47
36 42 7.90
38 42 8.85
39 42 2.99
41 42 4.50
0 43 7.30
1 43 6.68
6 43 6.36
7 43 6.56
8 43 6.11
10 43 5.64
11 43 1.58
12 43 4.08
13 43 2.08
14 43 9.65
15 43 1.64
17 43 5.83
23 43 3.91
25 43 8.87
26 43 5.28
27 43 2.16
28 43 2.34
29 43 8.26
31 43 2.81
32 43 5.15
33 43 1.02
35 43 3.16
36 43 3.67
37 43 2.62
38 43 6.76
40 43 1.63
42 43 4.40
0 44 2.47
1 44 4.67
8 44 1.74
11 44 8.24
12 44 8.58
13 44 8.30
14 44 3.34
16 44 7.18
17 44 4.57
22 44 4.80
23 44 4.84
24 44 8.02
28 44 6.80
29 44 1.74
30 44 9.23
35 44 5.93
38 44 1.97
39 44 8.57
41 44 5.08
42 44 9.18
43 44 2.92
0 45 4.02
4 45 2.13
9 45 6.27
10 45 2.44
11 45 8.95
13 45 9.60
15 45 7.27
16 45 7.81
17 45 8.87
18 45 8.19
19 45 4.27
20 45 1.93
26 45 4.44
27 45 4.69
28 45 2.71
30 45 5.64
33 45 2.92
35 45 2.45
42 45 8.51
1 46 9.80
3 46 5.21
5 46 8.48
6 46 3.84
9 46 4.01
10 46 8.86
14 46 1.03
15 46 6.41
16 46 2.53
17 46 8.49
19 46 7.00
22 46 5.88
24 46 3.45
25 46 5.93
26 46 8.53
27 46 2.83
28 46 5.95
29 46 6.77
30 46 5.05
32 46 6.25
37 46 4.84
38 46 5.31
39 46 4.28
40 46 9.36
43 46 6.10
44 46 8.07
1 47 7.10
2 47 3.27
3 47 5.29
4 47 6.02
5 47 6.69
6 47 2.19
10 47 1.94
11 47 2.07
12 47 4.61
15 47 8.11
16 47 8.95
18 47 8.84
19 47 9.19
20 47 8.08
21 47 3.58
22 47 7.91
25 47 5.64
30 47 4.27
32 47 5.91
36 47 2.79
37 47 4.67
40 47 2.76
41 47 9.98
42 47 6.65
43 47 7.68
44 47 6.04
45 47 2.23
4 48 6.43
5 48 7.61
6 48 7.23
7 48 3.71
8 48 6.39
10 48 1.85
11 48 6.32
12 48 6.48
13 48 5.40
15 48 7.13
18 48 1.80
19 48 5.03
22 48 5.22
25 48 7.74
26 48 3.39
27 48 2.19
29 48 8.39
30 48 7.37
31 48 6.51
33 48 6.81
34 48 6.96
35 48 9.12
38 48 7.98
39 48 4.44
43 48 3.79
44 48 4.58
47 48 2.25
2 49 7.10
4 49 5.85
5 49 4.78
7 49 8.82
12 49 4.10
13 49 8.81
14 49 8.40
15 49 7.56
16 49 6.78
18 49 6.91
19 49 9.86
22 49 5.03
23 49 3.31
25 49 1.44
28 49 6.47
29 49 2.54
30 49 6.70
31 49 2.93
32 49 2.19
36 49 9.98
37 49 6.01
40 49 1.77
45 49 9.16
46 49 4.66
47 49 9.90
4 50 5.85
5 50 3.50
6 50 6.59
9 50 5.76
10 50 8.26
11 50 3.73
12 50 1.32
14 50 1.24
15 50 6.44
16 50 8.53
17 50 2.25
20 50 9.25
28 50 4.99
29 50 8.39
31 50 2.36
37 50 7.74
38 50 1.58
40 50 2.62
41 50 9.09
43 50 7.73
44 50 5.13
45 50 2.67
49 50 6.94
4
42 4.50
21 7.93
39 1.95
43 2.90

10 35
0 1 5.93
1 2 7.34
2 3 4.86
0 4 3.43
2 4 2.27
3 4 2.00
1 5 6.60
3 5 2.52
4 5 7.59
0 6 8.71
2 6 7.90
3 6 9.21
5 6 4.44
2 7 3.82
4 7 6.94
5 7 8.10
0 8 2.46
1 8 5.80
2 8 7.35
3 8 3.73
5 8 5.42
1 9 8.91
2 9 7.27
3 9 7.89
4 9 8.23
6 9 9.53
7 9 3.27
8 9 8.64
1 10 3.80
2 10 5.62
3 10 1.41
4 10 3.67
5 10 5.68
6 10 4.25
9 10 2.22
10
2 2.25
10 2.96
9 8.72
1 1.23
7 7.07
6 5.80
3 3.61
5 4.41
8 4.46
4 4.84

17 81
0 1 2.83
0 2 9.67
1 2 3.58
0 3 9.36
1 3 4.08
2 3 5.45
0 4 8.42
2 4 9.29
3 4 1.58
0 5 3.77
1 5 9.65
4 5 2.07
1 6 6.13
2 6 5.13
3 6 2.82
4 6 7.66
5 6 5.51
0 7 8.12
2 7 3.49
5 7 9.04
6 7 9.69
1 8 4.62
2 8 6.30
7 8 2.19
3 9 2.10
4 9 1.77
0 10 3.44
3 10 5.29
4 10 5.35
7 10 2.99
8 10 1.33
0 11 4.87
2 11 2.54
6 11 8.46
9 11 6.51
10 11 8.13
0 12 7.51
1 12 8.37
3 12 2.18
4 12 4.75
6 12 1.05
7 12 2.03
8 12 4.41
10 12 8.12
11 12 5.27
2 13 1.98
4 13 6.80
7 13 3.97
8 13 2.89
9 13 9.90
1 14 4.45
2 14 1.13
3 14 6.83
6 14 9.31
7 14 5.59
8 14 8.82
9 14 3.62
10 14 8.18
12 14 5.23
0 15 2.32
3 15 9.93
4 15 7.15
8 15 4.68
9 15 2.64
11 15 6.60
12 15 3.49
13 15 4.62
0 16 8.55
1 16 6.17
3 16 7.00
11 16 5.96
12 16 3.45
14 16 1.20
15 16 3.66
0 17 1.98
1 17 8.46
7 17 6.33
8 17 5.21
9 17 2.78
13 17 3.10
16 17 1.91
6
15 5.83
7 9.96
17 8.51
12 7.00
1 4.88
11 5.67

27 188
0 1 3.33
0 2 2.74
2 3 2.87
3 4 2.44
0 5 8.80
2 5 1.94
3 5 7.79
2 6 5.14
3 6 4.28
5 6 4.23
0 7 8.24
1 7 5.89
4 7 9.76
5 7 5.17
6 7 8.57
0 8 3.76
1 8 6.52
2 8 8.90
3 8 1.00
4 8 4.77
0 9 2.06
2 9 7.66
3 9 7.56
4 9 6.67
6 9 1.56
7 9 6.68
0 10 6.94
4 10 3.19
6 10 6.94
7 10 7.47
8 10 4.95
4 11 1.97
5 11 9.78
7 11 4.92
10 11 5.23
0 12 5.63
3 12 7.92
4 12 8.19
5 12 1.10
7 12 4.89
10 12 9.28
11 12 7.98
3 13 5.15
5 13 5.97
7 13 3.05
8 13 3.64
10 13 9.72
12 13 4.05
1 14 6.50
2 14 5.85
7 14 2.18
8 14 9.06
11 14 9.77
12 14 1.63
13 14 1.16
0 15 6.57
1 15 8.61
2 15 3.20
4 15 7.24
5 15 9.90
7 15 7.14
0 16 5.87
1 16 9.17
4 16 2.92
6 16 2.41
7 16 1.96
13 16 3.25
14 16 9.73
1 17 5.32
2 17 7.94
3 17 9.40
9 17 1.94
11 17 3.59
14 17 6.31
4 18 5.83
5 18 7.70
6 18 2.28
7 18 3.87
8 18 6.01
9 18 8.68
10 18 5.57
13 18 8.53
14 18 5.19
17 18 5.90
1 19 4.15
2 19 8.52
3 19 2.40
4 19 8.61
5 19 4.12
9 19 9.88
13 19 4.18
16 19 6.45
17 19 4.19
1 20 1.96
4 20 8.65
6 20 4.66
7 20 4.29
11 20 9.09
13 20 4.97
14 20 2.51
16 20 2.88
19 20 1.72
1 21 4.02
2 21 3.32
4 21 7.30
7 21 5.63
9 21 1.82
11 21 3.46
16 21 5.45
18 21 8.73
20 21 6.07
3 22 7.85
4 22 9.10
5 22 2.36
7 22 3.46
8 22 9.24
9 22 1.43
11 22 3.66
13 22 4.34
14 22 1.13
15 22 2.71
16 22 9.64
17 22 3.88
18 22 4.07
19 22 1.05
21 22 9.44
1 23 9.72
2 23 2.00
3 23 5.76
4 23 1.95
10 23 3.27
12 23 9.60
15 23 6.20
17 23 6.73
1 24 4.25
3 24 8.22
7 24 8.66
9 24 2.55
12 24 6.00
13 24 4.92
15 24 3.47
16 24 1.69
19 24 2.70
21 24 1.07
0 25 2.09
1 25 2.20
2 25 7.25
3 25 5.64
4 25 7.59
5 25 3.55
6 25 2.75
8 25 8.33
10 25 5.67
11 25 6.99
12 25 3.55
13 25 7.25
14 25 8.33
17 25 4.26
18 25 6.68
23 25 4.02
24 25 1.39
2 26 7.19
4 26 1.07
6 26 2.14
8 26 8.72
10 26 3.02
11 26 1.51
12 26 7.92
16 26 9.28
17 26 4.91
18 26 9.35
20 26 2.38
21 26 6.15
2 27 5.72
3 27 6.50
4 27 3.66
5 27 1.00
6 27 4.58
8 27 9.72
11 27 7.25
13 27 5.47
15 27 4.43
17 27 9.16
18 27 7.21
19 27 3.78
20 27 6.32
24 27 1.81
25 27 7.34
7
20 5.86
13 5.68
24 8.59
25 8.23
10 2.63
7 9.33
11 5.65

44 500
0 1 9.35
0 2 2.89
1 2 5.62
1 3 6.87
2 3 4.69
0 4 8.92
1 4 4.33
2 4 6.10
0 5 7.94
1 5 3.00
3 6 6.17
4 6 7.28
5 6 3.33
1 7 9.34
2 7 3.41
3 7 9.69
4 7 3.32
6 7 9.65
2 8 6.01
3 8 8.31
5 8 7.34
6 8 7.74
0 9 4.47
1 9 7.34
2 9 1.82
3 9 8.76
4 9 3.27
6 9 8.18
7 9 4.30
8 9 7.00
0 10 3.92
1 10 5.52
2 10 5.31
5 10 8.22
6 10 6.21
7 10 7.55
4 11 8.81
6 11 2.26
7 11 4.67
8 11 7.74
4 12 8.99
5 12 9.00
7 12 7.07
8 12 2.42
9 12 9.74
0 13 5.62
2 13 9.64
3 13 3.43
10 13 4.84
0 14 1.80
2 14 3.23
3 14 1.65
4 14 9.18
7 14 7.85
10 14 8.56
2 15 6.86
3 15 4.14
5 15 3.37
11 15 7.56
0 16 6.12
3 16 7.21
4 16 4.49
5 16 8.40
6 16 6.85
7 16 3.11
10 16 4.82
11 16 3.53
14 16 1.91
0 17 5.42
1 17 5.08
4 17 4.39
6 17 7.57
7 17 1.84
9 17 1.28
10 17 8.73
12 17 2.23
16 17 3.66
0 18 6.36
3 18 7.17
4 18 7.31
5 18 7.39
7 18 1.67
8 18 4.64
9 18 1.16
10 18 2.90
11 18 8.57
12 18 9.75
16 18 8.35
17 18 7.61
1 19 5.52
3 19 4.55
5 19 5.85
7 19 7.51
8 19 5.80
9 19 2.43
11 19 9.53
13 19 8.28
14 19 7.79
0 20 7.34
1 20 5.50
3 20 6.23
4 20 9.06
5 20 4.26
6 20 6.10
7 20 3.57
11 20 4.25
13 20 3.41
15 20 9.38
16 20 1.33
19 20 1.65
1 21 2.33
5 21 7.63
6 21 6.43
7 21 9.05
8 21 4.89
9 21 6.02
10 21 3.67
14 21 4.15
15 21 7.02
16 21 6.84
19 21 5.91
0 22 3.75
1 22 6.72
3 22 4.28
6 22 4.35
7 22 3.86
8 22 1.17
10 22 2.29
11 22 8.95
12 22 6.42
14 22 1.94
16 22 1.52
20 22 3.57
1 23 9.58
3 23 1.44
5 23 8.22
8 23 3.03
11 23 8.71
13 23 1.15
16 23 1.33
17 23 2.46
18 23 6.19
19 23 1.72
21 23 5.79
0 24 4.87
1 24 8.55
3 24 8.19
4 24 6.46
8 24 2.75
10 24 8.88
11 24 6.98
12 24 1.59
13 24 3.60
21 24 3.30
1 25 7.31
6 25 4.27
9 25 3.35
10 25 6.96
11 25 2.99
12 25 2.27
13 25 7.97
14 25 6.20
16 25 8.90
17 25 4.97
3 26 4.23
6 26 5.90
9 26 5.47
10 26 2.28
16 26 1.32
18 26 5.88
20 26 4.25
22 26 2.96
25 26 3.65
2 27 7.20
3 27 5.20
6 27 7.52
8 27 5.81
10 27 3.38
13 27 2.43
14 27 6.42
17 27 5.20
18 27 9.93
19 27 3.85
22 27 3.79
23 27 2.83
26 27 7.33
0 28 4.34
1 28 7.21
2 28 3.22
5 28 6.65
6 28 9.40
7 28 2.64
8 28 3.93
9 28 3.97
14 28 7.37
19 28 6.08
20 28 8.75
22 28 9.80
26 28 4.26
0 29 1.79
1 29 6.79
2 29 6.69
5 29 2.94
6 29 4.66
8 29 2.83
12 29 4.63
13 29 1.52
15 29 2.49
17 29 7.81
20 29 4.86
21 29 2.90
24 29 6.79
2 30 1.47
3 30 5.78
5 30 4.20
6 30 4.82
8 30 8.22
10 30 7.65
11 30 7.94
13 30 9.37
14 30 8.66
15 30 6.05
18 30 6.32
19 30 7.68
20 30 9.05
25 30 8.84
26 30 6.01
28 30 6.12
29 30 5.24
0 31 7.74
1 31 4.00
2 31 4.47
4 31 8.12
5 31 9.43
6 31 9.48
7 31 2.41
8 31 6.37
9 31 2.37
10 31 3.05
12 31 6.84
14 31 6.64
15 31 2.57
19 31 3.84
20 31 5.17
23 31 6.12
24 31 2.56
25 31 8.52
27 31 9.87
30 31 6.21
0 32 8.27
1 32 9.15
2 32 8.88
3 32 5.19
6 32 8.22
8 32 5.35
9 32 9.86
11 32 3.27
14 32 1.16
15 32 6.64
16 32 8.72
18 32 3.29
19 32 9.90
20 32 4.36
23 32 4.02
24 32 1.60
25 32 2.31
29 32 7.02
0 33 6.27
1 33 9.49
5 33 9.97
7 33 3.60
8 33 3.36
9 33 5.26
10 33 7.51
11 33 3.91
12 33 2.19
14 33 2.55
20 33 2.06
22 33 6.39
24 33 2.01
27 33 3.89
28 33 6.74
31 33 9.56
0 34 9.64
2 34 1.55
5 34 8.42
7 34 1.44
9 34 5.55
10 34 9.36
11 34 5.65
17 34 3.33
19 34 3.99
20 34 1.46
21 34 6.81
22 34 6.65
29 34 1.84
32 34 7.67
4 35 5.98
5 35 4.15
6 35 1.80
7 35 6.76
9 35 5.39
10 35 4.06
11 35 1.95
13 35 7.53
14 35 1.21
15 35 4.49
16 35 1.27
18 35 4.30
21 35 8.80
22 35 1.43
24 35 5.54
25 35 3.78
28 35 8.85
31 35 8.20
33 35 7.16
34 35 9.92
2 36 7.21
3 36 9.54
4 36 3.92
5 36 5.81
6 36 4.45
8 36 2.38
10 36 2.25
11 36 7.81
17 36 1.19
18 36 6.73
21 36 9.38
22 36 9.31
25 36 9.49
26 36 9.41
27 36 7.51
28 36 8.25
30 36 1.32
31 36 7.42
33 36 3.38
0 37 1.42
5 37 9.06
8 37 8.08
13 37 3.04
16 37 5.41
17 37 1.18
18 37 6.49
19 37 2.70
22 37 4.80
23 37 8.35
28 37 7.88
29 37 7.07
33 37 8.60
36 37 9.44
1 38 5.67
3 38 5.77
4 38 4.18
5 38 5.45
7 38 9.67
8 38 6.20
11 38 8.25
12 38 1.74
13 38 9.96
14 38 6.59
15 38 1.67
17 38 2.54
18 38 8.81
20 38 9.21
26 38 4.04
27 38 6.47
29 38 8.52
31 38 2.85
33 38 3.12
34 38 4.01
35 38 9.32
37 38 3.39
1 39 9.60
3 39 8.83
4 39 1.62
5 39 9.89
9 39 5.37
12 39 6.86
15 39 6.56
23 39 2.64
26 39 4.77
28 39 8.35
30 39 6.88
31 39 4.04
33 39 2.55
34 39 7.32
35 39 1.27
1 40 6.44
3 40 7.90
6 40 7.48
8 40 5.74
11 40 7.82
14 40 4.84
17 40 7.33
19 40 6.80
24 40 7.52
25 40 3.61
27 40 9.91
30 40 1.12
32 40 6.02
33 40 6.01
35 40 1.54
38 40 9.11
0 41 3.20
3 41 9.81
4 41 9.53
6 41 4.09
7 41 1.18
8 41 5.60
10 41 3.85
11 41 1.49
13 41 6.54
15 41 1.28
16 41 2.12
19 41 4.41
21 41 1.07
22 41 7.53
23 41 1.75
24 41 5.15
25 41 8.65
26 41 1.19
27 41 5.52
30 41 2.11
31 41 6.73
32 41 5.23
36 41 4.16
40 41 5.99
0 42 6.87
1 42 4.15
3 42 4.20
4 42 3.17
5 42 3.56
7 42 9.45
8 42 2.87
9 42 6.31
10 42 6.58
12 42 6.76
16 42 5.31
19 42 9.33
20 42 8.10
21 42 5.19
23 42 5.33
24 42 1.48
25 42 1.50
27 42 6.23
28 42 8.25
29 42 5.55
30 42 3.15
31 42 2.64
34 42 6.13
35 42 8.60
36 42 8.50
38 42 7.86
40 42 7.75
0 43 8.89
1 43 8.28
2 43 6.64
3 43 6.31
5 43 2.85
6 43 7.80
8 43 9.04
9 43 1.04
13 43 4.38
14 43 4.12
18 43 3.27
19 43 7.02
21 43 9.01
26 43 4.23
28 43 5.85
30 43 1.06
31 43 4.35
32 43 9.87
35 43 7.99
38 43 3.16
39 43 2.52
40 43 2.96
42 43 3.54
0 44 1.20
1 44 4.73
3 44 6.99
7 44 2.61
8 44 7.39
9 44 5.06
11 44 3.49
12 44 9.12
15 44 7.23
19 44 4.94
20 44 3.99
21 44 1.33
22 44 6.30
23 44 3.63
24 44 8.93
25 44 9.32
26 44 4.14
31 44 8.97
35 44 7.09
39 44 7.67
40 44 6.73
41 44 3.10
42 44 6.70
8
14 8.65
20 4.05
1 3.82
44 5.87
23 7.70
5 1.58
28 8.59
36 3.54
AC output:

Code: Select all

Daniel can save $12.08
Don't leave the house
Don't leave the house
Daniel can save $1.66
Daniel can save $3.96
Daniel can save $0.99
Daniel can save $11.71
Daniel can save $15.15
Daniel can save $18.55
Daniel can save $15.32
Check input and AC output for thousands of problems on uDebug!

IUmplt
New poster
Posts: 1
Joined: Fri Apr 25, 2014 5:54 pm

Re: 11284 - Shopping Trip

Post by IUmplt » Fri Apr 25, 2014 5:57 pm

Can someone help me see what is wrong? I keep getting WA with all my variables integers. Is it possible to get the value out of 32-bit integer?

Code: Select all

#include <cstdio>
#include <cstring>

#define MAXIN (1 << 30) - 1;

int a[51][51];
int b[13][2];
int c[13][13];
int d[1<<13][13];
int ok[1<<13][13];
int best;

int dp(int s, int m, int k, int n) {
    int t;
    int i;
    
    if (ok[s][k])
        return d[s][k];
    if (m == 1)
        return c[0][k] - b[k][1];
    for (i = 1; i <= n; i++) {
        if (i != k && (s & (1 << i))) {
            t = dp(s ^ (1 << k), m-1, i, n) + c[i][k] - b[k][1];
            if (t < d[s][k]) {
                d[s][k] = t;
                ok[s][k] = 1;
            }
        }
    }
    if (d[s][k] + c[k][0] < best)
        best = d[s][k] + c[k][0];
    return d[s][k];
}

int main()
{
    int se, n, m, p, i, j, k, s, fl, x, y;
    int t;
    
    scanf("%d", &se);
    while (se--) {
        for (i = 0; i < 51; i++)
            for (j = 0; j < 51; j++)
                a[i][j] = MAXIN;
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        memset(ok, 0, sizeof(ok));
        for (i = 0; i < 1 << 13; i++)
            for (j = 0; j < 13; j++)
                d[i][j] = MAXIN;
        scanf("%d %d", &n, &m);
        for (i = 0; i <= n; i++)
            a[i][i] = 0;
        while (m--) {
            scanf("%d %d %d.%d", &i, &j, &x, &y);
            t = x * 100 + y;
            if (t < a[i][j])
                a[i][j] = a[j][i] = t;
        }
        for (k = 0; k <= n; k++)
            for (i = 0; i <= n; i++)
                for (j = 0; j <= n; j++)
                    if (a[i][j] > a[i][k] + a[k][j])
                        a[i][j] = a[i][k] + a[k][j];
        scanf("%d", &p);
        s = 0;
        while (p--) {
            scanf("%d %d.%d", &k, &x, &y);
            t = x * 100 + y;
            for (i = 1; i <= s; i++) {
                fl = 0;
                if (b[i][0] == k) {
                    b[i][1] += t;
                    fl = 1;
                    break;
                }
            }
            if (!fl) {
                b[++s][0] = k;
                b[s][1] = t;
            }
        }
        b[0][0] = 0;
        b[0][1] = 0;
        for (i = 0; i <= s; i++)
            for (j = 0; j <= s; j++)
                c[i][j] = a[b[i][0]][b[j][0]];
        best = MAXIN;
        d[1][0] = 0;
        for (i = 1; i <= s; i++)
            dp((1 << (s+1)) - 1, s, i, s);
        if (best < 0) {
            best = -best;
            if (best % 100 < 10)
                printf("Daniel can save $%d.0%d\n", best / 100, best % 100);
            else
                printf("Daniel can save $%d.%d\n", best / 100, best % 100);
        }
        else
            printf("Don't leave the house\n");
    }
    return 0;
}

Post Reply

Return to “Volume 112 (11200-11299)”