## 11099 - Next Same-Factored

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

Moderator: Board moderators

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)

### Last Contest - Problems A and F

What is wrong with solutions of this simple problems?

<cut>

Maybe there are simple bugs, but I can't find it.
Thanks for help.
Last edited by ulin on Thu Sep 21, 2006 8:27 pm, edited 1 time in total.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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
48
hope it helps
In being unlucky I have the record.

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)
Thanks!!!

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
thanks a lot, arsalan_mousavian
Jalal : AIUB SPARKS

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

### 11099 - Next Same-Factored

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;
}
}``````

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)
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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

### Re: 11099

farzane wrote:I need a hint to solve this problem whitout getting tle.
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
In being unlucky I have the record.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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
New poster
Posts: 4
Joined: Fri Sep 22, 2006 10:20 am

### 11099 Time Limit

see the next post!!!
Last edited by mahan on Fri Sep 22, 2006 11:59 am, edited 1 time in total.

mahan
New poster
Posts: 4
Joined: Fri Sep 22, 2006 10:20 am

### 11099 Time Limit

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
New poster
Posts: 2
Joined: Fri Sep 22, 2006 1:20 pm
Contact:
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
New poster
Posts: 2
Joined: Fri Sep 22, 2006 1:20 pm
Contact:
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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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!``
Last edited by arsalan_mousavian on Fri Sep 22, 2006 10:05 pm, edited 1 time in total.
In being unlucky I have the record.

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Code: Select all

``removed``
Last edited by farzane on Fri Sep 22, 2006 10:11 pm, edited 1 time in total.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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
Last edited by arsalan_mousavian on Fri Sep 22, 2006 10:10 pm, edited 1 time in total.
In being unlucky I have the record.