Posted: Sun Mar 24, 2002 6:17 am
Always assume that since the problem has been solved, the input set is within specification. Are you using floating point?
Page 2 of 19
Posted: Sun Mar 24, 2002 9:28 am
I'm using one.
Posted: Sun Mar 24, 2002 9:39 am
I've just seen your constant there. You hopefully don't rely on this constant being slightly larger than 1? Because this constant will be used as exactly 1. Look at this code:
The output is "1.110223e-15 0.000000e+00". This is because the distance between the leftmost and rightmost 1-bit is too large for a double. Note that I already made d as long as possible. If I insert one more 0, then output is "0.000000e+00 0.000000e+00"
Code: Select all
int main () {
double d = 1.000000000000001;
double e = 1.00000000000000000000000000000001;
printf( "%e %en", d-1, e-1 );
}
Posted: Thu Mar 28, 2002 12:09 am
Here is my latest code. And it works absolutely OK on all test cases. But I am getting wrong answer.
I use VC++/Windows. Can any body help me with a test case thats fails my program.
Thanx.
Code: Select all
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
double round(double num)
{
if(ceil(num)-num<num-floor(num))
return ceil(num);
else
return floor(num);
}
int main(){
double inht,workn,finht,N;
double gen,number,i;
while(cin>>inht>>workn){
if(inht==0&&workn==0) break;
if(inht!=1)
{
gen=1;
while((pow(inht,1/gen)-pow(workn,1/gen)-1)>0.000000000001||round(pow(inht,1/gen))-(int)(pow(inht,1/gen)+0.0005)>0.00000000001||round(pow(workn,1/gen))-(int)(pow(workn,1/gen)+0.0005)>0.00000000001)
gen++;
N=pow(workn,1/gen);
number=0;
finht=0;
for(i=0;i<gen;i++)
{
finht+=inht*pow((1/(N+1)),i)*pow(N,i);
number+=pow(N,i);
}
finht+=inht*pow((1/(N+1)),i)*pow(N,i);
}
else
{
number=0;
finht=1*workn;
}
cout<<setiosflags(ios::fixed)<<setprecision(0)<<number<<" "<<finht<<endl;
}
return 0;
}
Thanx.
Posted: Thu Mar 28, 2002 2:49 am
Ok, this is the last time I say this, I swear: Please get yourself a good mail program or configure yours correctly. Please don't take this personally, but this has been said way too often now...
I just got your program accepted! Without any changes!
You can also look at the thread I started last week in "Misc" with the screaming title "ATTENTION!...".
I just got your program accepted! Without any changes!
You can also look at the thread I started last week in "Misc" with the screaming title "ATTENTION!...".
Posted: Thu Mar 28, 2002 5:44 am
Stefan,
It just got accepted. thanx a lot. I usually use my university's mail program and it never gave me trouble, thats the reason I didnt even suspect this. hmmm, I guess I would go UNIX now.
It just got accepted. thanx a lot. I usually use my university's mail program and it never gave me trouble, thats the reason I didnt even suspect this. hmmm, I guess I would go UNIX now.
Time Limit Exceeded (107)
Posted: Fri Apr 26, 2002 1:09 am
I solved the problem right, but I had time limit exceeded error. I do not see how I could get such an error (except if the number of worker cats is a prime number).
Posted: Fri Apr 26, 2002 4:01 am
Rule #1, if the judge says your answer is wrong, your solution is most likely incorrect in someway. As most Computer Scientists know, proving correctness is mighty difficult. I suggest that if you are using floating point to make sure you are incorporating epsilon. Also, make sure your input works well with files. Try piping the sample test file into your program. Please post more specifics if you need more detailed help.
I actually had tried the program
Posted: Fri Apr 26, 2002 9:08 am
I have tried the program on the given test sample, once using keyboard for input, then indirecting the input from a file, and the answer was correct in the two times.
Here is the code:
I do not see the bottleneck that may cause a 'time limit exceeded'. I did not get a wrong output, but time limit exceeded error.
Here is the code:
Code: Select all
#include <fstream.h>
#include <math.h>
int levels(int num, int& span) {
int n=0;
bool finished = false;
while(!finished) {
n++;
long x = log(num)/log(n);
int y = int(x+0.5);
if (num==pow(n, y)) { // n is a valid N
span = n;
return y;
}
}
}
void cats(int cat1h, int line1, int& notworking, int& height) {
int N;
int k = levels(line1, N);
notworking = (pow(N, k)-1)/(N-1);
height = 0;
int levheight = cat1h;
for (int i = 0; i <= k; i++) {
height += levheight*pow(N, i);
levheight = levheight/(N+1);
}
}
void main() {
int cat1h, line1, notworking, height;
cin >> cat1h >> line1;
while (cat1h != 0 || line1 != 0) {
cats(cat1h, line1, notworking, height);
cout << notworking << ' ' << height << endl;
cin >> cat1h >> line1;
}Posted: Fri Apr 26, 2002 12:29 pm
Usually TLE is caused by infinite loop. For example, what if return y is never called? Time limit exceeded 
[cpp]int levels(int num, int& span) {
int n=0;
bool finished = false;
while(!finished) {
n++;
long x = log(num)/log(n);
int y = int(x+0.5);
if (num==pow(n, y)) { // n is a valid N
span = n;
return y;
}
}
} [/cpp]
[cpp]int levels(int num, int& span) {
int n=0;
bool finished = false;
while(!finished) {
n++;
long x = log(num)/log(n);
int y = int(x+0.5);
if (num==pow(n, y)) { // n is a valid N
span = n;
return y;
}
}
} [/cpp]
Posted: Sat Apr 27, 2002 10:25 am
Your program is not efficient. To realize this give inputs
483736625
481890304
The output should be 615441 1931252289.
In this problem,your main task is to solve the equation :
log(x+1)/log(x)=log(i)/log(w) in an efficient process.
as i and w is given the right part is a constant (=k)
x must be>1 and the left part is always >1.As x increases, it decreases,
and lim log(x+1)/log(x) =1
x->infinity
The lowese possible value of x is 2. log3 / log2=1.584962501...
log(3^p)/log(2^p) = p (log3) / p (log2) = log3 / log2
but if p!=1, 3^p - 2^p !=1
So, f:N->N (x)=log(x+1)/log(x)
never has any pick,the values of f(x) are sorted.
This implies that ,we can easily apply Bisection method to solve the equation, which we always use to search a criteria in a sorted array,named Binary Search.
Now,
1.Use Binary search process to find the root in a predefined interval,
such as [2,10e100].
2.Use double for calculation and show output using ".0lf"
483736625
481890304
The output should be 615441 1931252289.
In this problem,your main task is to solve the equation :
log(x+1)/log(x)=log(i)/log(w) in an efficient process.
as i and w is given the right part is a constant (=k)
x must be>1 and the left part is always >1.As x increases, it decreases,
and lim log(x+1)/log(x) =1
x->infinity
The lowese possible value of x is 2. log3 / log2=1.584962501...
log(3^p)/log(2^p) = p (log3) / p (log2) = log3 / log2
but if p!=1, 3^p - 2^p !=1
So, f:N->N (x)=log(x+1)/log(x)
never has any pick,the values of f(x) are sorted.
This implies that ,we can easily apply Bisection method to solve the equation, which we always use to search a criteria in a sorted array,named Binary Search.
Now,
1.Use Binary search process to find the root in a predefined interval,
such as [2,10e100].
2.Use double for calculation and show output using ".0lf"
Posted: Fri Jun 07, 2002 5:21 am
hmm i dont know where the error is
to the exmples it works great , but the judge keeps saying WA
i also tryed with doubles...
[c]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(){
long long unsigned height, n_workers, i, n_cats, n, h_total, h;
scanf("%Lu %Lu", &height, &n_workers);
while( (height | n_workers) != 0 ){
if(height == (n_workers+1) ){
printf("%d %Lu\n", 1, (height+n_workers));
}else{
for(i=2;i<=sqrt(n_workers);i++){
if(height%(i+1) != 0) continue;
h=height/(i+1);
h_total=height;
n_cats=1;
for(n=i;n<n_workers;n=n*i){
if(h%(i+1) != 0) break;
h_total=h_total+(h*n);
h=h/(i+1);
n_cats=n_cats+n;
}
if(n==n_workers){
h_t
iotal+=n_workers;
break;
}
}
printf("%Lu %Lu\n", n_cats, h_total);
}
scanf("%Lu %Lu", &height, &n_workers);
}
return 0;
}
[/c]
Thx
to the exmples it works great , but the judge keeps saying WA
i also tryed with doubles...
[c]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(){
long long unsigned height, n_workers, i, n_cats, n, h_total, h;
scanf("%Lu %Lu", &height, &n_workers);
while( (height | n_workers) != 0 ){
if(height == (n_workers+1) ){
printf("%d %Lu\n", 1, (height+n_workers));
}else{
for(i=2;i<=sqrt(n_workers);i++){
if(height%(i+1) != 0) continue;
h=height/(i+1);
h_total=height;
n_cats=1;
for(n=i;n<n_workers;n=n*i){
if(h%(i+1) != 0) break;
h_total=h_total+(h*n);
h=h/(i+1);
n_cats=n_cats+n;
}
if(n==n_workers){
h_t
iotal+=n_workers;
break;
}
}
printf("%Lu %Lu\n", n_cats, h_total);
}
scanf("%Lu %Lu", &height, &n_workers);
}
return 0;
}
[/c]
Thx
107 WA
Posted: Thu Jun 27, 2002 3:48 pm
It's veru strange that this program gets WA. May be there are big numbers in input?(As 10e50?)
[pascal]Program p107;
Var H,Work,P,i,t : integer;
S,Sa,Cur,j : integer;
Function Check(N : integer) : boolean;
Var Res,i,j,k : Integer;
begin
Res:=Round(Exp(ln(H)/(N+1)));
j:=1;
for i:=1 to N+1 do j:=j*Res;
P:=Res;
Res:=Round(Exp(ln(Work)/(N+1)));
k:=1;
for i:=1 to N+1 do k:=k*Res;
Check:=(j=H)and(k=Work);
end;
begin
While True do begin
Readln(H,Work);
if H=0 then break;
for i:=100 downto 1 do
if Check(i) then begin
t:=i;
break;
end;
S:=0; SA:=0;
for j:=1 to t+2 do begin
if j=1 then Cur:=1 else begin Cur:=Cur*(P-1); H:=H div P; end;
SA:=SA+Cur*H;
S:=S+Cur;
end;
S:=S-Work;
Writeln(S,' ',SA);
end;
end.[/pascal]
[pascal]Program p107;
Var H,Work,P,i,t : integer;
S,Sa,Cur,j : integer;
Function Check(N : integer) : boolean;
Var Res,i,j,k : Integer;
begin
Res:=Round(Exp(ln(H)/(N+1)));
j:=1;
for i:=1 to N+1 do j:=j*Res;
P:=Res;
Res:=Round(Exp(ln(Work)/(N+1)));
k:=1;
for i:=1 to N+1 do k:=k*Res;
Check:=(j=H)and(k=Work);
end;
begin
While True do begin
Readln(H,Work);
if H=0 then break;
for i:=100 downto 1 do
if Check(i) then begin
t:=i;
break;
end;
S:=0; SA:=0;
for j:=1 to t+2 do begin
if j=1 then Cur:=1 else begin Cur:=Cur*(P-1); H:=H div P; end;
SA:=SA+Cur*H;
S:=S+Cur;
end;
S:=S-Work;
Writeln(S,' ',SA);
end;
end.[/pascal]
Posted: Thu Jun 27, 2002 6:15 pm
hm........are you sure that the floating point operation has no error?
I know someone uses floating point opearation, but get WA becuase of floating point error.........
I know someone uses floating point opearation, but get WA becuase of floating point error.........
Help Problem107
Posted: Fri Jun 28, 2002 9:20 am
I try may input but still got wrong answer 
!!
Can anyone help me??
#include<stdio.h>
unsigned int height,one_num,temp,count,i,j,non_work,total_height,temp2;
int power_check,power_check2;
main()
{
while(scanf("%d %d",&height,&one_num) != 0)
{ if((height == 0)&&(one_num == 0)) /* end of input */
break;
if((one_num == 1)||(height == 1))
printf("0 %d\n",height);
else
{
for(i=2;i<=one_num;i++)
{
if(one_num % i == 0)
{
power_check = 1;
count = 1;
temp = one_num;
while(temp / i != 1) /* check if the second number is i's power((i)^a) */
{
if (temp % i != 0)
{
power_check = 0; /* not */
break;
}
temp = temp / i;
count++;
}
power_check2 = 0;
if((power_check == 1)&&(height % (i+1) == 0)) /* check if the first number is i's power((i+1)^a) */
{
power_check2 = 1;
temp = height;
while(temp / (i+1) != 1)
{
if (temp % (i+1) != 0) /* not */
{
power_check2 = 0;
break;
}
temp = temp / (i+1);
}
}
if(power_check2 == 1) /* answer found */
break;
}
}
temp = 1;
temp2 = one_num;
non_work = 0;
total_height = 0;
for(j=1;j<=count;j++) /* count total height and number of non-worked cats */
{
one_num = one_num / i;
non_work = non_work + one_num;
temp = temp*(i+1);
total_height = total_height + one_num * temp;
}
printf("%d %d\n",non_work,total_height+temp2);
}
}
}
!!Can anyone help me??
#include<stdio.h>
unsigned int height,one_num,temp,count,i,j,non_work,total_height,temp2;
int power_check,power_check2;
main()
{
while(scanf("%d %d",&height,&one_num) != 0)
{ if((height == 0)&&(one_num == 0)) /* end of input */
break;
if((one_num == 1)||(height == 1))
printf("0 %d\n",height);
else
{
for(i=2;i<=one_num;i++)
{
if(one_num % i == 0)
{
power_check = 1;
count = 1;
temp = one_num;
while(temp / i != 1) /* check if the second number is i's power((i)^a) */
{
if (temp % i != 0)
{
power_check = 0; /* not */
break;
}
temp = temp / i;
count++;
}
power_check2 = 0;
if((power_check == 1)&&(height % (i+1) == 0)) /* check if the first number is i's power((i+1)^a) */
{
power_check2 = 1;
temp = height;
while(temp / (i+1) != 1)
{
if (temp % (i+1) != 0) /* not */
{
power_check2 = 0;
break;
}
temp = temp / (i+1);
}
}
if(power_check2 == 1) /* answer found */
break;
}
}
temp = 1;
temp2 = one_num;
non_work = 0;
total_height = 0;
for(j=1;j<=count;j++) /* count total height and number of non-worked cats */
{
one_num = one_num / i;
non_work = non_work + one_num;
temp = temp*(i+1);
total_height = total_height + one_num * temp;
}
printf("%d %d\n",non_work,total_height+temp2);
}
}
}