10215 - The Largest/Smallest Box ...

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

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 09, 2003 9:18 pm

Did you look at the problemstats of this problem? It's impossible to get Accepted using Pascal. I wrote two identical programs, one in Pascal (my 'natural' language) and one in C, after many hours of frustration. The C program got accepted at once.

I guess it's all about implementation specific rounding errors and a lazy problemsetter... (Mark my words: I don't say lousy, but lazy. I consider Manzoor to be one of the most original and productive problemsetters, but IMHO he makes some slips in the rounding error department once in a while, see 10402 for which nobody to date reproduced his (seemingly) erronious result (124 WA and 0 AC point in that direction)).

My Pascal code is (WA):[pascal]program p10215;

var
w,l,x,x1,x2,vol1,vol2:real;
begin
while not eof do begin
readln(w,l);
if (w>l) then begin
x:=w;
w:=l;
l:=x;
end;
x1:=((l+w)-sqrt(l*l+w*w-l*w))/6.0;
x2:=((l+w)+sqrt(l*l+w*w-l*w))/6.0;
vol1:=x1*(w-2.0*x1)*(l-2.0*x1);
vol2:=x2*(w-2.0*x2)*(l-2.0*x2);
if (vol2<vol1) then x:=x1 else x:=x2;
writeln(x:0:3,' 0.000 ',(w/2.0):0:3);
end;
end.[/pascal]
And my C code is (AC):[c]#include <stdio.h>
#include <math.h>

int main(void){
double w,l,x,x1,x2,vol1,vol2;

while (scanf("%lf %lf",&w,&l)==2) {
if (w>l) {
x=w;
w=l;
l=x;
}
x1=((l+w)-sqrt(l*l+w*w-l*w))/6.0;
x2=((l+w)+sqrt(l*l+w*w-l*w))/6.0;
vol1=x1*(w-2.0*x1)*(l-2.0*x1);
vol2=x2*(w-2.0*x2)*(l-2.0*x2);
if (vol2<vol1) x=x1; else x=x2;
printf("%.3lf %.3lf %.3lf\n",x,0.0,w/2.0);
}
return 0;
}[/c]
Looks the same, feels the same, tastes the same. Please don't steal it... :wink:

Derk
New poster
Posts: 23
Joined: Mon Mar 17, 2003 3:53 am
Location: Louisville, KY
Contact:

Hm

Post by Derk » Wed Apr 09, 2003 10:13 pm

I switched float to double and got AC.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Thu Apr 10, 2003 9:01 am

Oh, Joey you are right.
There is NONE accepted with Pascal.
Thank you. I think I need to switch to the next problem.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Jan 16, 2004 8:32 am

The problem says:
Given the width and height of the box, you will have to find the value of x for which the box has maximum and minimum volume.


Input

The input file contains several lines of input. Each line contains two positive floating-point numbers L(0<L<10000) and W(0<W<10000); which indicate the length and width of the card respectively.
so are we getting the length and width of the card (as in input specification) or the width and height of the box???

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10215 WA

Post by midra » Tue Apr 13, 2004 3:54 am

Here is my code:

[c]
#include <stdio.h>

int main()
{
double l,w;
double res1,res2,a,b,c;
while(scanf("%lf %lf",&l,&w)!=EOF)
{
a=12;
b=4*(w+l);
c=w*l;
res1=(b + sqrt(b*b - 4*a*c))/(2*a);
res2=(b - sqrt(b*b - 4*a*c))/(2*a);
if (res1>res2)
printf("%.3lf 0.000 %.3lf\n",res2,res1);
else
printf("%.3lf 0.000 %.3lf\n",res1,res2);
}
return 0;
}
[/c]

It seems to be ok....
plz if someone knows help me!!

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Fri Apr 30, 2004 11:03 pm

I switched long double to double and got AC :)

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jun 19, 2004 2:46 pm

I think this problem should have a correction program for it.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Tue Jul 27, 2004 6:10 am

Can anybody see what's wrong with this code?[cpp]#include <iostream>
using namespace std;

long double a, b;

inline long double f(const long double &x){
return (a - 2*x)*(b - 2*x)*x;
}

int main(){

while(cin >> a >> b){
long double mn = 0;
long double mx = a > b ? b/2 : a/2;

while(mx - mn > 0.0000000001)
if(f(mn + (mx - mn)/3.0) > f(mn + 2.0*(mx - mn)/3.0)) mx = mn + 2.0*(mx - mn)/3.0;
else mn = mn + (mx - mn)/3.0;
cout.setf(ios::fixed);
cout.precision(3);
cout << mn << " " << 0.0 << " " << (a > b ? b/2 : a/2) << endl;

}

return 0;
}
[/cpp]

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Fri Aug 13, 2004 10:54 pm

minskcity, you are using long double. marian said his code got AC when he switched from long double to double. This is my code, and it works:

Code: Select all

int main()
{
    double L, W;
    while( cin >> L >> W )
        printf( "%.3f %.3f %.3f\n",
            ( L + W - sqrt( ( double )( L*L - L*W + W*W ) ) ) / 6.0,
            0.0, ( W <? L ) * 0.5 );
    return 0;
}
If only I had as much free time as I did in college...

randomtaiwanese
New poster
Posts: 32
Joined: Fri Oct 01, 2004 10:53 pm

Post by randomtaiwanese » Thu Nov 25, 2004 10:25 pm

someone wanna check my code???
btw... formatting decimals in java is a pain in the ass
[java]import java.io.IOException;
import java.util.StringTokenizer;
import java.text.NumberFormat;

class Main
{
static String ReadLn(int maxLg)
{
byte lin[]=new byte[maxLg];
int lg=0,car=-1;
try
{
while(lg<maxLg)
{
car=System.in.read();
if ((car<0)||(car=='\n'))
break;
lin[lg++]+=car;
}
}
catch(IOException e)
{
return(null);
}
if ((car<0)&&(lg==0))
return(null);
return (new String (lin, 0, lg));
}
public static void main(String[] args)
{
Main newMain = new Main();
newMain.start();
}
void start()
{
String input;
StringTokenizer tokenizer;
double w,l,m;
while ((input=Main.ReadLn(20))!=null)
{
tokenizer = new StringTokenizer(input);
l = new Double(tokenizer.nextToken()).doubleValue();
w = new Double(tokenizer.nextToken()).doubleValue();
m = Math.min(l,w);
System.out.print(FormatDecimal((((w+l)-Math.sqrt((w*w+l*l-w*l)))/6.0),3)+" 0.000 ");
System.out.println(FormatDecimal(m/2,3));
}
}
String FormatDecimal(double inp,int dec)
{
String in = new String(new Double(inp).toString());
NumberFormat nf = NumberFormat.getInstance();
nf.setGroupingUsed(false);
nf.setMaximumFractionDigits(dec);
in = nf.format(new Double(in).doubleValue());
int k=0;
if(in.charAt(0)=='.')
in = "0"+in;
while((in.charAt(k)!='.')&&!(k>=in.length()-1))
{
if(k<in.length())
{
if(in.charAt(k)=='.')
break;
else k++;
}
else break;
}
int diff = in.length()-k-1;
if(in.charAt(k)!='.')
{
in+=".";
for(int i=0;i<dec;i++) in+="0";
}
else if(dec>diff)
for(int i=0;i<(dec-diff);i++)
in+="0";
return in;
}
}[/java]
Last edited by randomtaiwanese on Thu Nov 25, 2004 10:51 pm, edited 1 time in total.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Nov 25, 2004 10:44 pm

Did you read my previous posting? It's impossible to get accepted in Pascal, and my strong impression is that it's also impossible to get accepted in Java. To date there are 599 people that got accepted, non of them with Java or Pascal.
Rewrite your code in C or C++.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Nov 25, 2004 10:50 pm

Holy mother of god!
I think your only mistake is choosing the wrong language for this problem. :-)

Somebody correct me if I'm wrong, but Java's NumberFormat by default rounds 0.5 to the nearest even number (which is 0), and printf() rounds up (which is 1). Since changing double to long double gives Wrong Answer, this little detail could be what is wrong with your code.
If only I had as much free time as I did in college...

randomtaiwanese
New poster
Posts: 32
Joined: Fri Oct 01, 2004 10:53 pm

Post by randomtaiwanese » Fri Nov 26, 2004 5:34 pm

little joey wrote:Did you read my previous posting? It's impossible to get accepted in Pascal, and my strong impression is that it's also impossible to get accepted in Java. To date there are 599 people that got accepted, non of them with Java or Pascal.
Rewrite your code in C or C++.
shame, becuase i have spent soo much time on writing a method on formatting a double value to a certain decimal place... ><

randomtaiwanese
New poster
Posts: 32
Joined: Fri Oct 01, 2004 10:53 pm

Post by randomtaiwanese » Fri Nov 26, 2004 5:43 pm

Abednego wrote:Holy mother of god!
I think your only mistake is choosing the wrong language for this problem. :-)

Somebody correct me if I'm wrong, but Java's NumberFormat by default rounds 0.5 to the nearest even number (which is 0), and printf() rounds up (which is 1). Since changing double to long double gives Wrong Answer, this little detail could be what is wrong with your code.
nah... java isnt this bad, it is only just about 3-5 times slower than other languages if both uses the best compiler, but because of the STONEAGE java compiler they have... java is like 10 times slower, a program with just ONE println() method takes 0.004 seconds to run on the OJ

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Nov 17, 2005 12:17 pm

Sigh...

I couldn't find what was wrong with my code (Java), so I came here, read that thing, went and checked the stats - 791 so far, C/C++ only.

That would explain some other WAs on similarly easy problems, I think (10137 (AC at PC), 10056...)

I guess I'll just skip any problems involving precision. Yes, I know I could just submit it in C and be done with it, but that's not the point.

Darko

P.S. Btw, people got AC by printing 3 0's? (I tried both 2 and 3) From the problem description one could say that if x_min = 0, you print only one, not two?

Post Reply

Return to “Volume 102 (10200-10299)”