914 - Jumping Champion

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

Moderator: Board moderators

914 - Jumping Champion

Postby bongssi » Mon Oct 30, 2006 10:58 am

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

Postby Jan » Mon Oct 30, 2006 1:25 pm

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
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Thank you very much, JAN...

Postby bongssi » Mon Oct 30, 2006 1:46 pm

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

Postby peace » Fri Feb 16, 2007 2:50 pm

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 :wink:
peace
New poster
 
Posts: 5
Joined: Wed Aug 09, 2006 1:34 am

Postby Jan » Fri Feb 16, 2007 4:19 pm

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
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Why WA??

Postby ranban282 » Sat Mar 17, 2007 2:23 pm

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

Postby Jan » Sat Mar 17, 2007 3:36 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
Location: Dhaka, Bangladesh

Postby Iffat » Wed Jun 27, 2007 7:17 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

Postby emotional blind » Wed Jun 27, 2007 7:41 pm

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


dont use this..

use it
Code: Select all
scanf("%ld",&n);
User avatar
emotional blind
A great helper
 
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

Postby Iffat » Wed Jun 27, 2007 8:01 pm

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

Postby emotional blind » Wed Jun 27, 2007 8:03 pm

So, OLE solved.. :)

okay..
try this
Code: Select all
1
2 3
User avatar
emotional blind
A great helper
 
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

Postby emotional blind » Wed Jun 27, 2007 8:05 pm

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
User avatar
emotional blind
A great helper
 
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

Postby Iffat » Wed Jun 27, 2007 8:09 pm

AC :D
thank u bhaia:):)
Iffat
New poster
 
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Postby emotional blind » Wed Jun 27, 2007 8:10 pm

Iffat
You just forgot to remove your code.
User avatar
emotional blind
A great helper
 
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

Postby Iffat » Wed Jun 27, 2007 8:14 pm

removed... :)
Iffat
New poster
 
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Next

Return to Volume IX

Who is online

Users browsing this forum: No registered users and 6 guests