821 - Page Hopping

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

Moderator: Board moderators

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

821 - Page Hopping

Post 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!
Top
camara
New poster
Posts: 6
Joined: Wed Jun 15, 2005 7:52 pm

Post by camara »

Problem solved! :)
It was in the input reading function...

By the way, the examples above are just fine.
Top
yure666
New poster
Posts: 2
Joined: Wed Nov 11, 2009 7:04 pm

Re: 821 - Page Hopping

Post 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
Top
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

Re: 821 - Page Hopping

Post 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;
}
Top
spewer
New poster
Posts: 4
Joined: Tue Dec 20, 2011 4:04 pm

Re: 821 - Page Hopping

Post 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
Top
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 821 - Page Hopping

Post by mahade hasan »

Cut ACC
we r surrounded by happiness
need eyes to feel it!
Top
Post Reply

Return to “Volume 8 (800-899)”