136 - Ugly Numbers

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

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 136 Ugly number

Post by brianfry713 » Tue Oct 01, 2013 11:55 pm

Print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

t_sleepy
New poster
Posts: 2
Joined: Tue Oct 01, 2013 1:32 pm

Re: 136 Ugly number

Post by t_sleepy » Thu Oct 03, 2013 9:19 am

Thanks a lot...accepted.. :wink:

mhu
New poster
Posts: 2
Joined: Thu Oct 03, 2013 5:23 pm

General: Fast Input / Output

Post by mhu » Thu Oct 03, 2013 5:38 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: General: Fast Input / Output

Post by brianfry713 » Thu Oct 03, 2013 10:42 pm

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.
Check input and AC output for thousands of problems on uDebug!

mhu
New poster
Posts: 2
Joined: Thu Oct 03, 2013 5:23 pm

Re: General: Fast Input / Output

Post by mhu » Fri Oct 04, 2013 4:17 pm

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

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 136 Ugly number

Post by Shihab » Sun Jan 19, 2014 11:58 am

AC

alex8078
New poster
Posts: 2
Joined: Thu Jan 08, 2015 8:05 pm

Re: 136 - Ugly Numbers

Post by alex8078 » Thu Oct 01, 2015 12:52 pm

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;   
}

Post Reply

Return to “Volume 1 (100-199)”