11099 - Next Same-Factored

[ulin]

What is wrong with solutions of this simple problems?

<cut>

Maybe there are simple bugs, but I can't find it.
Thanks for help.

[arsalan_mousavian]

about Problem A :
the map has 2 character , it is not mentioned that these 2 characters are l and w , there can be 2 arbitrary characters , but the character at (X,Y) shows land and the other character shows water

about problem F :

input :
24

output :
36
your output :
48
hope it helps

[ulin]

Thanks!!!

[CodeMaker]

thanks a lot, arsalan_mousavian

[farzane]

I need a hint to solve this problem whitout getting tle.
I used these 2 methds but both of them get tle.
1)produce and keep all of the prime factors of all numbers up to 2000000(like Eratosten algorithm)
2)produce and keep all of the prime factors of all numbers up to 1000000(like Eratosten algorithm)and for the rest of the numbers...(here is my code)

Code: Select all

#include<iostream.h>
const int max=1000000;
int f[max][7],size[max];

bool chek(int a,int b){
	int i;
	if(size[a]!=size[b])return false;
	for(i=0;i<size[a];i++)
		if(f[a][i]!=f[b][i])return false;
	return true;
}

void main(){
	int i,j,n,x;
	bool ans,is;
	for(i=0;i<max;i++)
		size[i]=0;
//	size[2]=1;
//	f[2][0]=2;
	for(i=2;i<max;i++){
		if(size[i])continue;
		size[i]=1;
		f[i][0]=i;
		for(j=i+i;j<max;j+=i)
			f[j][size[j]++]=i;
	}

	while(cin>>n){
		if(n==1){cout<<"Not Exist!"<<endl;continue;}
		ans=false;
		for(i=n+1;i<max;i++){
			ans=chek(n,i);
			if(ans)break;
		}
		if(!ans)
			for(;i<2000000;i++){
				x=i;
				is=true;
				for(j=0;j<size[n];j++){
					if(x%f[n][j]!=0){is=false;break;}
					while(x%f[n][j]==0)x/=f[n][j];
				}
				if(is&&x==1){ans=true;break;}

			}
		

		if(ans)cout<<i<<endl;
		else cout<<"Not Exist!"<<endl;
	}
}

please help.

[ulin]

There are too many datacases to solve it like you do.
Try to build answ integer (some candidates) using prime factors of n.

[arsalan_mousavian]

I need a hint to solve this problem whitout getting tle.
please help.

consider the case that maximum power for each prime factor is 1 ( like 5 , 7 , 6 = 2^1*3^1 ) what is the output ?
otherwise you can solve it simply
and also you can memoize for each input you read , so if there is multiple input with the same value you answer after the first time in O(1) , i did this last thing during the Contest and my program gets AC whereas it got TLE without this

Hope it helps . . .
Arsalan

[Vexorian]

about Problem A :
the map has 2 character , it is not mentioned that these 2 characters are l and w , there can be 2 arbitrary characters , but the character at (X,Y) shows land and the other character shows water

hey this was a good catch , it succesfully prevented me from getting AC there, and it wasn't really the problemsetter's fault it was mine for not reading the problem correctly.

[mahan]

see the next post!!!

[mahan]

Hi...
I get TLE for this problem..
Who can help me ?
This is My code:

Code: Select all

#include <iostream>

using namespace std;

const int Max=1000005;
int a[Max];
int prime[Max];


void main(){
	long int i,j,sw;
	long int num;
	for(i=0;i<Max;i++){
		a[i]=1;
		prime[i]=1;
	}
	for(i=2;i<Max;i++){
		if(a[i]==1){
			for(j=i;j<Max;j+=i){
				if(a[j]==1) a[j]=i;
				prime[j]*=i;
			}
		}
	}

	cin>>num;
	while(!cin.eof()){
		sw=0;
		for(i=num+a[num];i<Max ;i+=a[num]){
			if(num==1)	break;
			if((prime[i]==prime[num]) && prime[i]<2000000 ){
				cout<<i<<endl;
				sw=1;
				break;
			}
		}
		if(!sw) cout<<"Not Exist!"<<endl;
		cin>>num;
	}
}

with thanks

[lhotombolspasikumanaya]

Hi ...
I got WA with my code ... could anyone give me some critical test case (input and output)

and i also want to ask this ... if input :
0
1
12
999999
my output:
Not Exist!
Not Exist!
18
1222221

is that correct ???
Thanks a lot

[lhotombolspasikumanaya]

could anyone give me some critical test case for problem F and answer my question in topic thread below ???

http://online-judge.uva.es/board/viewtopic.php?t=12076

Thanks a lot

[arsalan_mousavian]

0 is an invalid input , as it is mentioned in the problem statement that input will be a positive intger

my AC program output as same as you , maybe you didn't used long long , because for some input ( e.g maximum prime less than 1000000 ) the answer will be input*input that is more than 2000000 but if you use int it overflows and you print the result incorrectly

input :

Code: Select all

999983

output :

Code: Select all

Not Exist!

[farzane]

I'm getting WA.Where is my mistake?Please help.

Code: Select all

removed

Thanks in advance

[arsalan_mousavian]

your Code doesn't pass my input in my previous post!!!,you should change your Code as follow ,

Code: Select all

if(isprime[n])ans[n]=n*n;

to 

if(isprime[n]){
  ans[n]=n*n;
  if ( ans [n] >= MAX ) 
      ans [n] = -1 ;
}

and 

if(ans[n]>MAX)ans[n]=-1;

to 
if(ans[n]>=MAX)ans[n]=-1;

i have done these changes in your Code and it Got AC ,and don't forget to remove your code ,
Have AC
Arsalan