11038 - How Many O's?

[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

Code: Select all

20991740
151899207

[mf]

My program outputs:

Code: Select all

23709830
231396207

[Darko]

Thanks a bunch! Instead of 10^i in one place, I had just 10, but it was OK for the sample input.

[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

[Martin Macko]

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.

[midra]

thanks...I think I understand my error
I really apreciate your help!

[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

[Martin Macko]

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"!

[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

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 ?

[mamun]

Can you use %I64d? Use %lld instead.

[SRX]

Can you use %I64d? Use %lld instead.

thanks
I use "%lld" and get ac now !

[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

[Martin Macko]

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.

[Quantris]

When I switched to VS .NET 2003, I discovered that %lld works (%I64d is still a valid alternative), which was nice.

[shakil]

please help me(I am new in acm).

Code: Select all

Cut after AC

[/b]