## 821 - Page Hopping

Moderator: Board moderators

camara
New poster
Posts: 6
Joined: Wed Jun 15, 2005 7:52 pm

### 821 - Page Hopping

Hi,

Does anyone have test cases for this one? I don't know where else to find my error...
Some of my inputs:
1 2 2 4 1 3 3 1 4 3 0 0
1 2 1 4 4 2 2 7 7 1 0 0
1 100 100 2 2 99 99 3 3 98 98 4 4 97 97 5 5 96 96 6 6 95 95 7 7 94 94 8 8 93 93 9 9 92 92 10 10 91 91 11 11 90 90 12 12 89 89 13 13 88 88 14 14 87 87 15 15 86 86 16 16 85 85 17 17 84 84 18 18 83 83 19 19 82 82 20 20 81 81 21 21 80 80 22 22 79 79 23 23 78 78 24 24 77 77 25 25 76 76 26 26 75 75 27 27 74 74 28 28 73 73 29 29 72 72 30 30 71 71 31 31 70 70 32 32 69 69 33 33 68 68 34 34 67 67 35 35 66 66 36 36 65 65 37 37 64 64 38 38 63 63 39 39 62 62 40 40 61 61 41 41 60 60 42 42 59 59 43 43 58 58 44 44 57 57 45 45 56 56 46 46 55 55 47 47 54 54 48 48 53 53 49 49 52 52 50 50 51 51 1 0 0
98 99 99 11 11 98 0 0
1 2 2 1 2 3 3 2 3 4 4 3 4 5 5 4 5 1 0 0
1 2 1 3 1 4 1 5 2 1 2 3 2 4 2 5 3 1 3 2 3 4 3 5 4 1 4 2 4 3 4 5 5 1 5 2 5 3 5 4 0 0
0 0

The corresponding output:
Case 1: average length between pages = 1,833 clicks
Case 2: average length between pages = 1,750 clicks
Case 3: average length between pages = 50,000 clicks
Case 4: average length between pages = 1,500 clicks
Case 5: average length between pages = 1,750 clicks
Case 6: average length between pages = 1,000 clicks

Do you guys have different results or different test cases?
Thanks!

camara
New poster
Posts: 6
Joined: Wed Jun 15, 2005 7:52 pm
Problem solved!
It was in the input reading function...

By the way, the examples above are just fine.

yure666
New poster
Posts: 2
Joined: Wed Nov 11, 2009 7:04 pm

### Re: 821 - Page Hopping

My program seems to be runing OK but I get WA, can someone post some cases?

Code: Select all

``````1 2 1 4 4 2 2 7 7 1 0 0
1 100 100 2 2 99 99 3 3 98 98 4 4 97 97 5 5 96 96 6 6 95 95 7 7 94 94 8 8 93 93 9 9 92 92 10 10 91 91 11 11 90 90 12 12 89 89 13 13 88 88 14 14 87 87 15 15 86 86 16 16 85 85 17 17 84 84 18 18 83 83 19 19 82 82 20 20 81 81 21 21 80 80 22 22 79 79 23 23 78 78 24 24 77 77 25 25 76 76 26 26 75 75 27 27 74 74 28 28 73 73 29 29 72 72 30 30 71 71 31 31 70 70 32 32 69 69 33 33 68 68 34 34 67 67 35 35 66 66 36 36 65 65 37 37 64 64 38 38 63 63 39 39 62 62 40 40 61 61 41 41 60 60 42 42 59 59 43 43 58 58 44 44 57 57 45 45 56 56 46 46 55 55 47 47 54 54 48 48 53 53 49 49 52 52 50 50 51 51 1 0 0
98 99 99 11 11 98 0 0
1 2 2 1 2 3 3 2 3 4 4 3 4 5 5 4 5 1 0 0
5 1 5 2 5 3 5 4 2 1 2 3 2 4 2 5 1 2 1 3 1 4 1 5 3 1 3 2 3 4 3 5 4 1 4 2 4 3 4 5 0 0
1 2 1 3 1 4 1 5 2 1 2 3 2 4 2 5 3 1 3 2 3 4 3 5 4 1 4 2 4 3 4 5 5 1 5 2 5 3 5 4 0 0
1 2 2 1 0 0
0 0
1 2 2 1 0 0``````

Code: Select all

``````Case 1: average length between pages = 1.833 clicks
Case 2: average length between pages = 1.750 clicks
Case 3: average length between pages = 50.000 clicks
Case 4: average length between pages = 1.500 clicks
Case 5: average length between pages = 1.750 clicks
Case 6: average length between pages = 1.000 clicks
Case 7: average length between pages = 1.000 clicks
Case 8: average length between pages = 1.000 clicks
``````

sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

### Re: 821 - Page Hopping

Don't know, Its such an easy problem. But, still not able to get AC in it
O tries Floyd but, it timed out and now I've tries with BFS but, still no luck. Getting TLE for long time! Please guide me, if any problem is there with my code?
Or, I how can I refine my algorithm ?

Regards,
SITZ

Code: Select all

``````#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef long long int64;
typedef unsigned long long uint64;

#define INF	1LL<<60
#define FOI(i, A, B) for(i=A; i<=B; i++)
#define FOD(i, A, B) for(i=A; i>=B; i--)

map<int, vector<int> >::iterator it1, it2, it3;
map<int, bool> use;

int bfs(int src, int des){
queue< pair<int, int> > q;
q.push(make_pair(src, 0));
while( !q.empty() ){
pair<int, int> p = q.front();
q.pop();
if( use[p.first] )
continue;
if( p.first == des )
return p.second;
int i;
q.push( make_pair(adj[p.first][i], p.second + 1) );
use[p.first] = true;
}
return 0;
}

int main(){
//freopen("testI.txt", "r", stdin);
//freopen("testO.txt", "w", stdout);
for(int T = 1; ; T++){
int i, j, k;
int A, B;
scanf("%d%d", &A, &B);
if(A == 0 && B == 0)
break;
while( true ){
scanf("%d%d", &A, &B);
if(A == 0 && B == 0)
break;
}
double den = 0;
double num = 0;

if((*it1).first != (*it2).first){
use.clear();
use[(*it3).first] = false;
num += bfs((*it1).first, (*it2).first);
den += 1;
}
}
}

printf("Case %d: average length between pages = %.3lf clicks\n", T, num/den);
}
return 0;
}
``````

spewer
New poster
Posts: 4
Joined: Tue Dec 20, 2011 4:04 pm

### Re: 821 - Page Hopping

if u have Tim Limit
my algo do this pretty fast
try this :

Code: Select all

``````1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
1 100 100 1 0 0
0 0
``````