## 914 - Jumping Champion

Moderator: Board moderators

bongssi
New poster
Posts: 14
Joined: Mon Jul 31, 2006 10:35 am

### 914 - Jumping Champion

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;

int primes;
int jump_list;
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.jump_dst);
else
printf("No jumping champion\n");
}

return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

bongssi
New poster
Posts: 14
Joined: Mon Jul 31, 2006 10:35 am

### Thank you very much, JAN...

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
New poster
Posts: 5
Joined: Wed Aug 09, 2006 1:34 am
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### Why WA??

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;
v=0;
int prime={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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Replace

Code: Select all

``vector<int> jump_array(100,0);``
with

Code: Select all

``vector<int> jump_array(1000,0);``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am
can anyone tell me y i got Output Limit Exceed frm this code? Code: Select all

``cut``
thnx
mouri
Last edited by Iffat on Wed Jun 27, 2007 8:10 pm, edited 2 times in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

Code: Select all

``while(scanf("%ld",&n)!=EOF){``
dont use this..

use it

Code: Select all

``scanf("%ld",&n);``

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am
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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
So, OLE solved.. okay..
try this

Code: Select all

``````1
2 3``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am
AC thank u bhaia:):)

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
removed... 