914 - Jumping Champion

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

Moderator: Board moderators

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

914 - Jumping Champion

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

Post by 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

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

Thank you very much, JAN...

Post by 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

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

Post by 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:

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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

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

Why WA??

Post by 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;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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

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

Post by 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.

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

Post by 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);

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

Post by 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.... :(

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

Post by 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
Contact:

Post by 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

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

Post by Iffat » Wed Jun 27, 2007 8:09 pm

AC :D
thank u bhaia:):)

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

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

Iffat
You just forgot to remove your code.

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

Post by Iffat » Wed Jun 27, 2007 8:14 pm

removed... :)

Post Reply

Return to “Volume 9 (900-999)”