11099  Next SameFactored
Moderator: Board moderators
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.
<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.

 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
your output :
48
hope it helps
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
In being unlucky I have the record.
11099  Next SameFactored
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)
please help.
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;
}
}

 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
Re: 11099
consider the case that maximum power for each prime factor is 1 ( like 5 , 7 , 6 = 2^1*3^1 ) what is the output ?farzane wrote:I need a hint to solve this problem whitout getting tle.
please help.
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.
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.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
11099 Time Limit
see the next post!!!
Last edited by mahan on Fri Sep 22, 2006 11:59 am, edited 1 time in total.
11099 Time Limit
Hi...
I get TLE for this problem..
Who can help me ?
This is My code:
with thanks
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;
}
}

 New poster
 Posts: 2
 Joined: Fri Sep 22, 2006 1:20 pm
 Contact:

 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://onlinejudge.uva.es/board/viewtopic.php?t=12076
Thanks a lot
http://onlinejudge.uva.es/board/viewtopic.php?t=12076
Thanks a lot

 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 :
output :
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
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.
I'm getting WA.Where is my mistake?Please help.
Thanks in advance
Code: Select all
removed
Last edited by farzane on Fri Sep 22, 2006 10:11 pm, edited 1 time in total.

 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 , i have done these changes in your Code and it Got AC ,and don't forget to remove your code ,
Have AC
Arsalan
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;
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.