Page 2 of 3
Re: 11284 - Shopping Trip
Posted: Tue Nov 18, 2008 11:13 am
by tryit1
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.
Re: 11284 - Shopping Trip
Posted: Tue Nov 18, 2008 5:40 pm
by Darko
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

Re: 11284 - Shopping Trip
Posted: Sun Aug 21, 2011 7:53 am
by FelixP
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

Re: 11284 - Shopping Trip
Posted: Wed Oct 19, 2011 7:01 pm
by razor
@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.
Re: 11284 - Shopping Trip
Posted: Wed Feb 13, 2013 11:12 am
by AKJ88
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;
}
Re: 11284 - Shopping Trip
Posted: Wed Feb 13, 2013 6:25 pm
by fh
@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:
Re: 11284 - Shopping Trip
Posted: Thu Feb 14, 2013 10:35 am
by AKJ88
@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;
}
Re: 11284 - Shopping Trip
Posted: Thu Feb 14, 2013 4:26 pm
by fh
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
Re: 11284 - Shopping Trip
Posted: Wed Jul 31, 2013 4:36 am
by a.elbashandy
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;
}
Re: 11284 - Shopping Trip
Posted: Wed Jul 31, 2013 8:32 am
by brianfry713
try solving it without using floating point.
Re: 11284 - Shopping Trip
Posted: Wed Jul 31, 2013 4:18 pm
by a.elbashandy
@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;
}
Re: 11284 - Shopping Trip
Posted: Wed Jul 31, 2013 8:14 pm
by brianfry713
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.
Re: 11284 - Shopping Trip
Posted: Thu Aug 01, 2013 5:13 am
by a.elbashandy
AKJ88 Yes i use extra matrix for saving minimum distance between dvd stores and the initial position only
Re: 11284 - Shopping Trip
Posted: Fri Aug 02, 2013 12:14 am
by brianfry713
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
Re: 11284 - Shopping Trip
Posted: Fri Apr 25, 2014 5:57 pm
by IUmplt
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;
}