OJ Board • 914 - Jumping Champion

Page 1 of 3

914 - Jumping Champion

Posted: Mon Oct 30, 2006 10:58 am

by bongssi

I got WA at problem 914(Jumping Champion).
But I can't find the bugs... I'm so sad now...
Would you mind giving some test input and output? Or plzzzzz notify me my fault...
-----------------------------------------------------------------------------------

#include <stdio.h>
#include <math.h>
struct jump_info{

int jump_dst;
int jump_occur;
}jump[80000];

int primes[80000];
int jump_list[80000];
int is_prime(int n){

int i, sqrt_n;
if(n<2 || (n>2 && n%2==0)) return 0;

sqrt_n = (int)sqrt(n);
for(i=3; i<=sqrt_n; i+=2)
if(n % i == 0) return 0;

return 1;
}

int main(void){

int i, j, k, case_qty, prime_qty=0, jump_qty, start, end, start_index, end_index;
int is_champ, tmp;
primes[prime_qty++] = 2;
for(i=3; i<=1000000; i+=2)
if(is_prime(i)) primes[prime_qty++] = i;

for(i=0; i<prime_qty-1; i++)
jump_list = primes[i+1] - primes;

scanf("%d", &case_qty);
for(i=0; i<case_qty; i++){

scanf("%d %d", &start, &end);

for(j=0; j<prime_qty; j++){
if(primes[j] >= start){
start_index = j;
j++;
break;
}
}

for( ; j<prime_qty; j++){
if(primes[j] > end){
end_index = j-1;
break;
}
}

is_champ = 1;
jump_qty = 0;
for(j=start_index; j<end_index; j++){

for(k=0; k<jump_qty; k++){

if(jump[k].jump_dst == jump_list[j]){
jump[k].jump_occur++;
break;
}
}

if(k==jump_qty){
jump[jump_qty].jump_dst = jump_list[j];
jump[jump_qty++].jump_occur = 1;
}
}

for(j=jump_qty-1; j>=1; j--){

if(jump[j].jump_occur > jump[j-1].jump_occur){

tmp = jump[j].jump_occur;
jump[j].jump_occur = jump[j-1].jump_occur;
jump[j-1].jump_occur = tmp;

tmp = jump[j].jump_dst;
jump[j].jump_dst = jump[j-1].jump_dst;
jump[j-1].jump_dst = tmp;
}

else if(jump[j].jump_occur == jump[j-1].jump_occur){
is_champ = 0;
break;
}
}

if(is_champ && jump_qty>0)
printf("The jumping champion is %d\n", jump[0].jump_dst);
else
printf("No jumping champion\n");
}

return 0;
}

Posted: Mon Oct 30, 2006 1:25 pm

by Jan

Try the following I/O set

Input:

Code: Select all

2
1 1000000
1872 182789

Output:

Code: Select all

The jumping champion is 6
The jumping champion is 6

Hope it helps.

Thank you very much, JAN...

Posted: Mon Oct 30, 2006 1:46 pm

by bongssi

hmm my program gives different answer.
Both of two cases, it says "No jumping champion" ...
Maybe I'll have to fix my code...k

Posted: Fri Feb 16, 2007 2:50 pm

by peace

hello everyone, I also get WA in this problem.

I try several case, but I cannot find the bug..

here are some case I try:

Input:

Code: Select all

My Output:

Code: Select all

No jumping champion
The jumping champion is 1
The jumping champion is 1
No jumping champion
The jumping champion is 2
No jumping champion
No jumping champion
No jumping champion
The jumping champion is 4
The jumping champion is 6

Can anyone offer some other tricky input?

thx a lot

Posted: Fri Feb 16, 2007 4:19 pm

by Jan

Some cases...

Input:

Code: Select all

Output:

Code: Select all

The jumping champion is 6
The jumping champion is 6
The jumping champion is 6
No jumping champion
No jumping champion
The jumping champion is 8
The jumping champion is 2
No jumping champion
The jumping champion is 2
The jumping champion is 4
The jumping champion is 6
The jumping champion is 4
The jumping champion is 6
The jumping champion is 6
The jumping champion is 6

Hope these help.

Why WA??

Posted: Sat Mar 17, 2007 2:23 pm

by ranban282

I am trying to solve problem 914. I am passing Jan's test cases, but still getting WA. Any more cases, or someting wrong with my code?
Here goes:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;

int main()
{
	vector<bool> v(1000000,1);
	v[0]=0;
	v[1]=0;
	int prime[1000]={2};
	int c=1;
	for(int i=3;i<1000;i+=2)
	{
		int flag=1;
		for(int j=3;j*j<=i;j+=2)
		{
			if(i%j==0)
			{
				flag=0;
				break;	
			}
		}
		if(flag)
			prime[c++]=i;
	}
	for(int i=0;i<c;i++)
	{
		for(int j=2*prime[i];j<1000000;j+=prime[i])
			v[j]=0;
	}
	vector<int> p;
	for(unsigned  i=0;i<v.size();i++)
	{		if(v[i])
		{p.push_back(i);}
	}
	vector<int> jump(p.size()-1);
	for(int i=0;i<jump.size();i++)
	{
		jump[i]=p[i+1]-p[i];
		//cout<<jump[i]<<endl;
	}
	int n;
	scanf(" %d",&n);
	while(n--)
	{
		int a,b;
		scanf(" %d %d",&a,&b);
		vector<int> jump_array(100,0);
		int lb=lower_bound(p.begin(),p.end(),a)-p.begin();
		int ub=upper_bound(p.begin(),p.end(),b)-p.begin();
		for(int i=lb;i<ub-1;i++)
		{jump_array[jump[i]]++;}
		int m=max_element(jump_array.begin(),jump_array.end())-jump_array.begin();
		if(count(jump_array.begin(),jump_array.end(),jump_array[m])!=1)
			printf("No jumping champion\n");
		else printf("The jumping champion is %d\n",m);
	}

	return 0;
}

Posted: Sat Mar 17, 2007 3:36 pm

by Jan

Replace

Code: Select all

vector<int> jump_array(100,0);

with

Code: Select all

vector<int> jump_array(1000,0);

Hope it helps.

Posted: Wed Jun 27, 2007 7:17 pm

by Iffat

can anyone tell me y i got Output Limit Exceed frm this code?

Code: Select all

cut

thnx
mouri

Posted: Wed Jun 27, 2007 7:41 pm

by emotional blind

Code: Select all

while(scanf("%ld",&n)!=EOF){

dont use this..

use it

Code: Select all

scanf("%ld",&n);

Posted: Wed Jun 27, 2007 8:01 pm

by Iffat

i edited that part but got WA....
i tested all the test cases,they r all r8...don know where is the bug....

Posted: Wed Jun 27, 2007 8:03 pm

by emotional blind

So, OLE solved..

okay..
try this

Code: Select all

1
2 3

Posted: Wed Jun 27, 2007 8:05 pm

by emotional blind

I think

Code: Select all

if(num>1 && f==1)

should be replaced by

Code: Select all

if(num>0 && f==1)

Best of Luck

Posted: Wed Jun 27, 2007 8:09 pm

by Iffat

AC

thank u bhaia:):)

Posted: Wed Jun 27, 2007 8:10 pm

by emotional blind

Iffat
You just forgot to remove your code.

Posted: Wed Jun 27, 2007 8:14 pm

by Iffat

removed...