4
\$\begingroup\$

there is only one rule: get accept for this problem http://acm.ut.ac.ir/sc/problemset/view/1032!

to submit your code, you need to create an account(if you don't want to do so, just post your code here and I'll submit it). so far shortest code is written with C and has 85 character length.

winner will be the shortest C/C++ code submitted before 2012/02/01

note: to check shortest codes submitted you can click on "accepted runs" and then "code length"

as elssar suggested I've copied the question here :

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + ... + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.

figure http://acm.ut.ac.ir/sc/assets/problem_images/1032_50ac13c53158fd843d1884e8afa962dd.jpg

Input

The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.

Output

For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.

Sample Input

1.00
3.71
0.04
5.19
0.00

Sample Output

3 card(s)
61 card(s)
1 card(s)
273 card(s)

\$\endgroup\$
  • \$\begingroup\$ Would be nice if you copied the question over here. \$\endgroup\$ – elssar Jan 16 '12 at 14:30
  • \$\begingroup\$ I just saw a guy on 9gag that recently posted an image of this :) \$\endgroup\$ – ajax333221 Jan 16 '12 at 18:53
  • \$\begingroup\$ Shouldn't there be 5 outputs for 5 inputs? \$\endgroup\$ – Thomas Eding Jan 17 '12 at 4:38
  • 1
    \$\begingroup\$ I know the problem says C/C++, but that's for the ACM site. Can we post answers in other languages here on CG? \$\endgroup\$ – elssar Jan 17 '12 at 7:24
  • \$\begingroup\$ @trinithis 0 is used to terminate input, so it's not really an input to program. In any case, the answer for 0 would be trivial - 0 \$\endgroup\$ – elssar Jan 17 '12 at 7:33
2
\$\begingroup\$

C, 149 89

Well, this was a noobish shot at it, but probably a decent starting point:

#include <cstdio>
float i;
int o(float a,int n=2){return a<0?n-2:o(a-1./n,n+1);}
main(){if (scanf("%f",&i),i==0) return 0;printf("%d card(s)\n",o(i));main();}

It reported as 145 characters.


With a push in the right direction, I got the solution down to 122 by changing the function to a for loop.

#include <cstdio>
float i;
main(){
if (scanf("%f",&i),i==0) return 0;
int n=2;for(;i>0;)i-=1./n++;
printf("%d card(s)\n",n-2);
main();}

On a roll!

#include <cstdio>
main()
{
    float i,n=2;
    for(scanf("%f",&i);i>0;i-=1/n++);
    if (n-=2) printf("%.0f card(s)\n",n), main();
}

Scooted scanf, for loop division doesn't need 1. any more, adjusting n now done in conditional.


Switched over to C, got some good savings. Down to 89 characters.

main(n)
{
    float i;
    for(scanf("%f",&i);i>0;i-=1./++n);
    if (--n) printf("%d card(s)\n",n), main(1);
}
\$\endgroup\$
  • \$\begingroup\$ A for( loop is probably going to be more concise than a recursive function for the calculation in o(. Maybe something like main(){if (scanf("%f",&i),i==0) return 0;for(n=2;i>0;n++)i-=1./n;printf("%d card(s)\n",n-2);main();} (if I understand your logic correctly). (Demo: ideone.com/CgFbp) Also there are some extra spaces that can be removed (ex. between if ( and ) return). \$\endgroup\$ – mellamokb Jan 16 '12 at 18:54
  • \$\begingroup\$ Turns out that the way the program is judged, whitespace doesn't matter (which is actually kinda nice for readability). \$\endgroup\$ – Mr. Llama Jan 16 '12 at 19:02
  • 1
    \$\begingroup\$ A few more optimizations: main(){scanf("%f",&i);for(n=2;i>0;i-=1./n++);n-=2;if(n)printf("%d card(s)\n",n),main();} Edit: Just tried submitting it, was accepted as 115 characters :). I removed return statement, moved check for i==0 to be instead a check of if(n) toward the end. \$\endgroup\$ – mellamokb Jan 16 '12 at 19:03
  • \$\begingroup\$ Got 3 more characters off: Combine definitions to float i,n=2; and change printf to use %.0f to round the float value. \$\endgroup\$ – mellamokb Jan 16 '12 at 19:14
  • \$\begingroup\$ You can shave off just a bit more by defining and initializing n just before the for loop: int n=2;for(;i>0;i-=1./n++) \$\endgroup\$ – Mr. Llama Jan 16 '12 at 19:15
0
\$\begingroup\$

As I said so far there is an answer with 85 characters written in C99 (note that white spaces are not counted)

main(i){for(float x;i=scanf("%f",&x),x;printf("%d card(s)\n",--i))for(;x>0;x-=1./++i);}

that was the whole code, hope It gives you the idea how to optimize it!

\$\endgroup\$
  • \$\begingroup\$ It seems we were on similar paths then... I'm currently 4 characters higher, but making good progress (I think). If anything, I'm glad to have come close without knowing the current best entry. \$\endgroup\$ – Mr. Llama Jan 16 '12 at 19:56
  • \$\begingroup\$ I know two other codes (almost the same as this one) with 85 characters, but so far I couldn't find anything better than This \$\endgroup\$ – Ali1S232 Jan 16 '12 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.