## 914 - Jumping Champion

Moderator: Board moderators

### 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[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[i] = primes[i+1] - primes[i];

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;
}
bongssi
New poster

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

Try the following I/O set

Input:
Code: Select all
`21 10000001872 182789`

Output:
Code: Select all
`The jumping champion is 6The jumping champion is 6`

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### 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
bongssi
New poster

Posts: 14
Joined: Mon Jul 31, 2006 10:35 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
`100 12 31 32 53 55 56 107 197 230 1000000`

My Output:

Code: Select all
`No jumping championThe jumping champion is 1The jumping champion is 1No jumping championThe jumping champion is 2No jumping championNo jumping championNo jumping championThe jumping champion is 4The jumping champion is 6`

Can anyone offer some other tricky input?

thx a lot
peace
New poster

Posts: 5
Joined: Wed Aug 09, 2006 1:34 am

Some cases...

Input:
Code: Select all
`15734 156156 1606184 1075382 501741 1173684 779279 283667 836125 243737 765119 577737 828556 79560 1901793 1432`

Output:
Code: Select all
`The jumping champion is 6The jumping champion is 6The jumping champion is 6No jumping championNo jumping championThe jumping champion is 8The jumping champion is 2No jumping championThe jumping champion is 2The jumping champion is 4The jumping champion is 6The jumping champion is 4The jumping champion is 6The jumping champion is 6The jumping champion is 6`

Hope these help.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### 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]=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;}`
ranban282
New poster

Posts: 37
Joined: Tue May 02, 2006 1:01 pm

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
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

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.
Iffat
New poster

Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Code: Select all
`while(scanf("%ld",&n)!=EOF){`

dont use this..

use it
Code: Select all
`scanf("%ld",&n);`

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

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

Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

So, OLE solved..

okay..
try this
Code: Select all
`12 3`

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

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

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

AC
thank u bhaia:):)
Iffat
New poster

Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Iffat
You just forgot to remove your code.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

removed...
Iffat
New poster

Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Next