fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. int quez_count(int n)
  7. {
  8. 	int i = 10;
  9. 	int res = 0; 
  10. 	while(i < n){
  11. 		res += (i - i/10)*log10(i);
  12. 		i *= 10;
  13. 	}
  14. 	res += (n - i/10)*log10(i)+ceil(log10(n));
  15. 	return res;	
  16. }
  17.  
  18. int koala_count(int n)
  19. {
  20. 	int log = log10( n ) + 1;
  21. 	return ( n + 1 ) * log  - ( pow( 10,  log) - 1 ) / ( 10 - 1 );
  22. }
  23.  
  24. void test()
  25. {
  26. 	srand( time( NULL ) );
  27. 	cout << "Testing..." << endl;
  28. 	for( int i = 0; i< 10; ++i)
  29. 	{
  30. 		int r = rand() % 100000000 + 100000000;
  31. 		cout << r << " : " << quez_count( r ) << " : " << koala_count( r ) << endl;
  32. 	}
  33. }
  34.  
  35. int main() {
  36. 	int repeats = 100000,
  37. 	    size = 9500000000;
  38. 	test();
  39.  
  40. 	clock_t start = clock();
  41. 	for( int i = 0; i< repeats; ++i)
  42. 	{
  43. 		int r = rand() % size + size;
  44. 		quez_count( r );
  45. 	}
  46. 	cout << "Time on quez's solution:" <<(double(clock()-start)/CLOCKS_PER_SEC) << "seconds"<<endl;
  47.  
  48. 	start = clock();
  49. 	for( int i = 0; i< repeats; ++i)
  50. 	{
  51. 		int r = rand() % size + size;
  52. 		koala_count( r );
  53. 	}
  54. 	cout << "Time on koala's solution:" <<(double(clock()-start)/CLOCKS_PER_SEC) << "seconds"<<endl;
  55.  
  56.  
  57.  
  58. 	return 0;
  59. }
Success #stdin #stdout 0.15s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing...
169174872 : 1411462746 : 1411462746
167950503 : 1400443425 : 1400443425
152536488 : 1261717290 : 1261717290
162141890 : 1348165908 : 1348165908
180626349 : 1514526039 : 1514526039
199564317 : 1684967751 : 1684967751
168199097 : 1402680771 : 1402680771
173208774 : 1447767864 : 1447767864
179258369 : 1502214219 : 1502214219
160367896 : 1332199962 : 1332199962
Time on quez's solution:0.13seconds
Time on koala's solution:0.02seconds
https://ideone.com/Z8MFQw
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!