## 11284 - Shopping Trip

Moderator: Board moderators

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

### Re: 11284 - Shopping Trip

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

### Re: 11284 - Shopping Trip

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

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

@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

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???

Code: Select all

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

#define INF 100000000

using namespace std;

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
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;
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;
}

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

### Re: 11284 - Shopping Trip

@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

@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???
My new code is here:

Code: Select all

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

#define INF 10000000

using namespace std;

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
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;
dst1 = tsp(0, I|1);
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;
}

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

### Re: 11284 - Shopping Trip

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

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 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;

double ans = INF_MIN, temp, temp1, temp2;

for (int i = 0; i <= p; 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);

}

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

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

@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 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;

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

for (int i = 0; i <= p; 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);

}

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

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

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

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

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;
}
``````