914 - Jumping Champion

[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;
}

[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.

[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

[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

10
0 1
2 3
1 3
2 5
3 5
5 5
6 10
7 19
7 23
0 1000000

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

[Jan]

Some cases...

Input:

Code: Select all

15
734 1561
56 1606
184 1075
382 501
741 1173
684 779
279 283
667 836
125 243
737 765
119 577
737 828
556 795
60 1901
793 1432

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.

[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;
}

[Jan]

Replace

Code: Select all

vector<int> jump_array(100,0);

with

Code: Select all

vector<int> jump_array(1000,0);

Hope it helps.

[Iffat]

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

Code: Select all

cut

thnx
mouri

[emotional blind]

Code: Select all

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

dont use this..

use it

Code: Select all

scanf("%ld",&n);

[Iffat]

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

[emotional blind]

So, OLE solved..

okay..
try this

Code: Select all

1
2 3

[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

[Iffat]

AC
thank u bhaia:):)

[emotional blind]

Iffat
You just forgot to remove your code.

[Iffat]

removed...