Количество "единичек"

[Акоб]

я поправил.побробуй сейчас))

[boomeer]

#include <iostream>
#include <assert.h>
#include <math.h>
struct res
{
  unsigned int numDigs;
  bool hasOneDig;

  res( unsigned int n, bool h ) : numDigs( n ), hasOneDig( h ) {}
};

res oneDigitCount( unsigned int input )
{
   assert( input < 10 );

   switch( input )
   {
      case 0:
         return res( 1, false );
      case 1:
         return res( 1, true );
      default:
         return res( input, false );
   }
};

res countNoOnes( unsigned int input )
{
   if( input < 10 )
        return oneDigitCount( input ); // base case that ends recursion

   unsigned int quotient = input / 10;
   unsigned int remainder = input % 10;

   res result = countNoOnes( quotient ); // recursive
   result.numDigs *= 9;

   if( !result.hasOneDig )
   {
       res remainderRes = oneDigitCount( remainder );
       result.numDigs += remainderRes.numDigs;
       if( remainderRes.hasOneDig ) // or remainder==1
          result.hasOneDig = true;
   }

   return result;
}

unsigned int countNumsContainingOne( unsigned int input )
{
   return input + 1 - countNoOnes(input).numDigs;
}

int main(int argc, char* argv[])
{
    int input;
    std::cin>>input;
    std::cout<<countNumsContainingOne(input);
    return 0;
}

Но что то тут не правильно...

[NiCola999]

Акоб, у вас программа на многих диапазонах выдает 0, а на степенях 10, правильный ответ =)) и это очевидно из массива

[Акоб]

я тут много чего поправил, скайите мне цыфры которые вы ставили я проверю.
программа работает так, кол-во(356) = 2*кол-во(99) + 100 + 4*кол_во(9) + 10 + кол_во(6) =2*19 +100 + 4 + 10 + 1 = 153

Скажите мне эти диапазоны.
мне очень интересно.

#include<iostream.h>


int stepen(int x)
{
	int s = 1;
	for(; x >= 1; x--)
		{
			s = s * 10;
		}
	return s;
}




int main()
{
	
	int Buff[10] = {0,1,19,271,3439,40951,468559,5217031,56953279,612579511};
	int N,j,h = 0,n = 0;
	cin>>N;
	j = N;
	

	while(j >= 1)
	{
		j = j / 10;
		h++;
	}


	j = N;
	j = j / stepen(h - 1);
	if(h == 1)
		{
			n = 1;
			cout<<n<<endl;
			return 0;
		}
	
	while(h != 0) 
	{
		if(j == 1)
			{
				if(N % stepen(h - 1) == 0)
					{
						n = n + Buff[h - 1] + 1;
						cout<<n<<endl;
						return 0;
					}
					
				n = n + (N % stepen(h - 1)) + Buff[h - 1] + 1;
				cout<<n<<endl;
				return 0;
			}
		else
			if(j != 0)
			{
				n = n + (j - 1) * Buff[h - 1] + stepen(h - 1);
			}
		N = N % stepen(h - 1);
		j = N;
		h--;
		j = j / stepen(h - 1);

	}
	cout<<n<<endl;


	return 0;
}

это исправленный код
у меня работает правильно.

[NiCola999]

сравнил с лобовым алгоритмом. В промежутке от 1 до 400000 ошибок нет, я думаю дальше не стоит проверять ибо это будет очень долго... По моим расчетам программа закончит тест через 2777,77 часов (~115 дней) после запуска . Кто хочет столько ждать, выкладываю тестовую программку)

[Акоб]

классная штука))
а как вы узнаете скорость работы?

[NiCola999]

проверяется(обоими алгоритмами) 100 чисел в секунду, 10^9 / 100 = 10 млн сек / 3600 = 2777,77 ч / 24 = 115,7 дн. В общем-то при увеличении N скорость уменьшается, так что точно сказать нельзя. Короче очень долго =)). И я с уверенностью могу сказать что ваш алгоритм работает на 100% =)

[Obey-Kun]

#include <iostream>
#include <cmath>
#include <cassert>

using namespace std;

/// Количество чисел с единичкой в промежутке [1; m*10^n]
int dikiy(int m, int n)
{
    assert(m >= 0);
    assert(n >= 0 && n < 10);
    if(m == 0) {
        return 0;
    } else if(n == 0) {
        return 1;
    } else if(m == 1) {
        return exp(n * log(10)) - exp(n * log(9)) + 1;
    } else {
        double tmp = dikiy(1, n);
        return tmp + (m - 2) * (tmp - 1) + pow(10,n) - 1;
    }
}

/// Количество чисел с единичкой в промежутке [1; x]
int fuckingFunc(int x)
{
    assert(x > 0);
    int result = 0;
    for (int i = log10(x); i >= 0; --i) {
        int tmp = x/pow(10,i);
        x -= tmp*pow(10,i);
        result += dikiy(tmp, i);
        if (tmp == 1) {
            /* если текущая цифра -- 1, добавляем остаток к результату и всё,
             * ведь при реальном счёте всё в остатке начиналось бы на 1 */
            result += x;
            break;
        }

    }
    return result;
}

int main()
{
    int x;
    do {
        cout << "Enter fucking positive number: ";
        cin >> x;
    } while(x < 1);
    
    int result = fuckingFunc(x);
    
    cout << "Your answer is " << result << ", dumbass." << endl;
}

Нате. Считает быстрей всего прочего. Осиливает любую степень в допустимых пределах int менее, чем за 0.1 секунды.

[NiCola999]

не верно считает, начиная с 200

1 число - твой, 2 - решение в лоб

118 != 119	n = 200
119 != 120	n = 201
119 != 120	n = 202
119 != 120	n = 203
119 != 120	n = 204
119 != 120	n = 205
119 != 120	n = 206
119 != 120	n = 207
119 != 120	n = 208
119 != 120	n = 209
120 != 121	n = 210
121 != 122	n = 211
122 != 123	n = 212
123 != 124	n = 213
124 != 125	n = 214
125 != 126	n = 215
126 != 127	n = 216
127 != 128	n = 217
128 != 129	n = 218
129 != 130	n = 219
129 != 130	n = 220
130 != 131	n = 221
130 != 131	n = 222
130 != 131	n = 223
130 != 131	n = 224
130 != 131	n = 225
..........

[Obey-Kun]

Эм.. у меня для 201 оно показывает 120. Да и для прочего тоже. Странно. Ты ничего не перепутал?