OJ Board

The Online Judge board
https://onlinejudge.org/board/

821 - Page Hopping

https://onlinejudge.org/board/viewtopic.php?t=8362

Page 1 of 1

821 - Page Hopping

Posted: Mon Jun 20, 2005 12:42 am
by camara
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!

Posted: Mon Jun 20, 2005 1:05 pm
by camara
Problem solved! :)
It was in the input reading function...

By the way, the examples above are just fine.

Re: 821 - Page Hopping

Posted: Sun Nov 15, 2009 9:44 pm
by yure666
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

Re: 821 - Page Hopping

Posted: Fri Mar 18, 2011 5:34 pm
by sitz
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> >adj;
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;
		FOI(i, 0, adj[p.first].size()-1)
			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++){
		adj.clear();
		int i, j, k;
		int A, B;
		scanf("%d%d", &A, &B);
		if(A == 0 && B == 0)
			break;
		adj[A-1].push_back(B-1);
		while( true ){
			scanf("%d%d", &A, &B);
			if(A == 0 && B == 0)
				break;
			adj[A-1].push_back(B-1);
		}
		int N = adj.size();
		double den = 0;
		double num = 0;
			
		for (it1 = adj.begin(); it1 != adj.end(); it1++){
			for (it2 = adj.begin(); it2 != adj.end(); it2++){
				if((*it1).first != (*it2).first){
					use.clear();
					for (it3 = adj.begin(); it3 != adj.end(); it3++)
						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;
}

Re: 821 - Page Hopping

Posted: Sun Jan 01, 2012 2:15 am
by spewer
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

Re: 821 - Page Hopping

Posted: Sun Sep 30, 2012 9:24 pm
by mahade hasan
Cut ACC
All times are UTC+02:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited