Re: 136 Ugly number
Posted: Tue Oct 01, 2013 11:55 pm
Print a newline char at the end of the last line.
Page 11 of 11
Re: 136 Ugly number
Posted: Thu Oct 03, 2013 9:19 am
Thanks a lot...accepted..
General: Fast Input / Output
Posted: 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:
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
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;
}
Would be great if someone could share his/her secrets about fast IO! (Or any other interesting tuning tips...
)Cheers,
Michael
Re: General: Fast Input / Output
Posted: 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:
In general, printf is faster than cout, and write is faster than printf.
Even this code took 0.012 sec to get WA in C on problem 136:
Code: Select all
int main() {return 0;}Re: General: Fast Input / Output
Posted: 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... )
)Re: 136 Ugly number
Posted: Sun Jan 19, 2014 11:58 am
AC
Re: 136 - Ugly Numbers
Posted: 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;
}