Page 1 of 2
11038 - How Many O's?
Posted: Sun May 28, 2006 10:04 am
by Darko
I didn't manage to solve it yesterday, but now I have no idea what is wrong. I get the sample right, can someone check this I/O:
Code: Select all
1001010101 1010101010
3020203 302010203
-1 -1
Posted: Sun May 28, 2006 10:31 am
by mf
Posted: Sun May 28, 2006 10:42 am
by Darko
Thanks a bunch! Instead of 10^i in one place, I had just 10, but it was OK for the sample input.
Posted: Mon May 29, 2006 4:44 am
by midra
hi, I have difficulty with this problem
I think it in this way:
from 0..9 I have one 0
from 0..99 I have ten 0's
so I think it in this way:
cant representes amount of 0's from 0..(10^i - 1)
so I have
cant[1]=1
cant[2]=10
for(i=3;i<11;i++)
cant=9*(cant[i-1]+pow(10,i-2)) + cant[i-1];
I though this:
suppouse this two numbers of n-digits: 100..00 and 999..99
from 100..00 to 999..99 (both of n-digits)
the amount of 0's is 9*(100..00 to 199..99)
and the amount of 0's from 100..00 to 199..99 is equal to cant[n-1] + pow(10,n-2)
this is because, from 100..00 to 199..99 we can forgive the first digit and count the amount of 0's of the rest (n-1)digits and then I sum pow(10,n-2) because I am counting the case where 10x..xx I mean, first digit 1, second digit 0 and the rest of digits can be anything because this case is not in the amount of cant[n-1] because in amount of 0's of cant[n-1] I don't count numbers that start with 0
the problem is that when I calculate this with brute force, I get another results, and I am not sure if this is the correct idea to solve this problem...maybe there are more elegant and efficient solutions...
I really appreciate any help!!
thanks for reading!
bye!
PD: I hope you understand my ugly explanation
plz let me know if you don't understand some part of my explanation
Posted: Tue May 30, 2006 4:03 am
by Martin Macko
midra wrote:
for(i=3;i<11;i++)
cant=9*(cant[i-1]+pow(10,i-2)) + cant[i-1];
I don't think the highlighted part is correct. For instance, if i=4 the number of uncounted leading zeros in numbers 7000, 7001, ... 7009, 7010, ... 7047, ... 7099, 7100, ... 7999 is 110 and not pow(10,i-2)=100.
Posted: Tue May 30, 2006 5:16 am
by midra
thanks...I think I understand my error
I really apreciate your help!
Posted: Tue May 30, 2006 4:42 pm
by SRX
hi , I have solved this prob , and I use cin as input way
Why if I use
"scanf ( "%lld %lld" , &n , &m ) and scanf ( "%I64d , %I64d" , &n , &m )"
, I get tle
Can someone answer me ?
thanks
Posted: Tue May 30, 2006 8:41 pm
by Martin Macko
SRX wrote:hi , I have solved this prob , and I use cin as input way
Why if I use
"scanf ( "%lld %lld" , &n , &m ) and scanf ( "%I64d , %I64d" , &n , &m )"
, I get tle
I have used the
scanf to read the input, too, but without any problem with the time limit. Just make sure not to write the colon in
"%I64d , %I64d"!
Posted: Wed May 31, 2006 7:03 am
by SRX
Martin Macko wrote:SRX wrote:hi , I have solved this prob , and I use cin as input way
Why if I use
"scanf ( "%lld %lld" , &n , &m ) and scanf ( "%I64d , %I64d" , &n , &m )"
, I get tle
I have used the
scanf to read the input, too, but without any problem with the time limit. Just make sure not to write the colon in
"%I64d , %I64d"!
Code: Select all
#include <iostream>
#include <cstdio>
#include <algorithm>
using std :: cout ;
long long n , m ;
int main () {
while ( scanf ( "%I64d %I64d" , &n , &m ) && n>=0 && m>=0 ) ;
}
hi , why this code get tle ?
Posted: Wed May 31, 2006 7:53 am
by mamun
Can you use %I64d? Use %lld instead.
Posted: Wed May 31, 2006 8:14 am
by SRX
mamun wrote:Can you use %I64d? Use %lld instead.
thanks
I use "%lld" and get ac now !
Posted: Thu Jun 01, 2006 4:46 am
by midra
I use %I64d when I am on windows
and %lld for linux
so, remember always to put to the codes that you send to the online judge %lld instead of %I64d
Posted: Thu Jun 01, 2006 5:43 am
by Martin Macko
midra wrote:so, remember always to put to the codes that you send to the online judge %lld instead of %I64d
To make sure you won't forget to change
%I64d to
%lld before submiting, you may write something like this:
Code: Select all
#ifdef ONLINE_JUDGE
#define LLONG "%lld"
#else
#define LLONG "%I64d"
#endif
int main(void)
{
long long int t=7;
printf("t=" LLONG "\n", t);
return 0;
}
This should compile and work on both -- your windows machine and the online judge, too.
Posted: Thu Jun 01, 2006 7:46 am
by Quantris
When I switched to VS .NET 2003, I discovered that %lld works (%I64d is still a valid alternative), which was nice.
11038 why wa!!!!!!
Posted: Sat Jul 15, 2006 6:49 am
by shakil
please help me(I am new in acm).
[/b]