136 - Ugly Numbers

[brianfry713]

Print a newline char at the end of the last line.

[t_sleepy]

Thanks a lot...accepted..

[mhu]

Hi,

I'm wondering how people manage to get a CPU time of 0.000s for almost all problems. My guess is that this is somehow input / output related. Problem 136 - Ugly Numbers is a nice one to illustrate what I mean. After offline precomputation I end up with the following code, which basically just outputs one single string:

Code: Select all

#include <iostream>
using namespace std;

int main() { 
    cout.sync_with_stdio( false );
    cout << "The 1500'th ugly number is 859963392.\n"; 
    return 0; 
}

This leads to a CPU time of 0.012s (place > 10k). If I replace C++ way of outputing the resulting string by printf, it is even worst and I get 0.019s. As I don't perform any computation, the time difference has to come from the way I output the result. Thus I wonder if there is a faster way than using standard input / output methods?

Would be great if someone could share his/her secrets about fast IO! (Or any other interesting tuning tips... )

Cheers,

Michael

[brianfry713]

It seems that most of the 0 sec runtimes are from before around 2005, when I think the server was updated. So trying to get 0 sec runtimes might be impossible.

Even this code took 0.012 sec to get WA in C on problem 136:

Code: Select all

int main() {return 0;}

In general, printf is faster than cout, and write is faster than printf.

[mhu]

thanks a lot for your reply! (a bit weird that programs ran faster in the old days than today... )

[Shihab]

AC

[alex8078]

Hello, everyone! I got the correct answer on my PC, but I got a WA after submission. I try some modifications and take care of the output format but still WA after I submit to UVA online judge. Please help me! Thx!!

Code: Select all

#include <stdio.h>
#include <cstdlib>
#include <iostream>
using namespace std;

long ugly[1500];

int minimum(const int& b2,const int& b3,const int& b5)
{
   int a = ugly[b2-1]*2;
   int b = ugly[b3-1]*3;
   int c = ugly[b5-1]*5;
   
   if((a<b)&&(a<c)) return 1;
   else if((b<a)&&(b<c)) return 2;
   else if((c<a)&&(c<b))return 3;
   else if((a==b)&&(b==c)) return 7;
   else if(a==b) return 4;
   else if(b==c) return 5;
   else if(a==c) return 6;   
}

int update_next_ug(int& b2, int& b3, int& b5, int &ug_num)
{
    int condition = minimum(b2,b3,b5);
    ++ug_num;
    int next_ug = 1;  
    switch(condition)
    {
       case 1:
               next_ug = ugly[b2-1]*2;
               ++b2;
               break;
       case 2:
               next_ug = ugly[b3-1]*3;
               ++b3;
               break;
       case 3:  
               next_ug = ugly[b5-1]*5;
               ++b5;
               break;  
       case 4:
               next_ug = ugly[b2-1]*2;
               ++b2;
               ++b3;
               break;
       case 5:
               next_ug = ugly[b3-1]*3;
               ++b3;
               ++b5;
               break;      
       case 6:
               next_ug = ugly[b2-1]*2;
               ++b2;
               ++b5;
               break;
       case 7:
               next_ug = ugly[b2-1]*2;
               ++b2;
               ++b5;
               ++b3;
               break;
            
    } 
    return next_ug;
}

int main(void)
{
  int b2 = 1;
  int b3 = 1;
  int b5 = 1; 
  int ug_num = 1; 
  long last_ug = 1;
  
  while(1)
  {
     ugly[ug_num-1] = last_ug;
     if(ug_num==1500) break;
     last_ug = update_next_ug(b2,b3,b5,ug_num);
  }

   printf("The 1500'th ugly number is %d.",ugly[1499]);
  return 0;   
}