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

[Obey-Kun]

это не 10^n

exp(dn * log(10)) - exp(dn * log(9)) + 1 при dn=5 равно 31 (если отбросить дробную часть)

давай сначала отладим, а потом всё объясню

[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) {
        double dn = double(n);
cout << exp(dn * log(10)) << " - " << exp(dn * log(9)) << " + 1" << endl;
        return int(exp(dn * log(10)) - exp(dn * log(9))) + 1;
    } else {
        int 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);
        cout << "i = " << i << ", tmp = " << tmp << ", dikiy(tmp, i) = " << dikiy(tmp, i) << endl;
        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;
}

[Акоб]

Enter fucking positive number: 1000
1000 - 729 + 1
i = 3, tmp = 1, dikiy(tmp, i) = 271
1000 - 729 + 1
Your answer is 271, dumbass.
Press any key to continue

[Акоб]

пожалуйста посчитай скорость работы моего кода при 4294967256.

[Obey-Kun]

Ха, что за дьявольщина? На моём калькуляторе 1000 - 729 + 1 получается 272)))

Попробуй так:

#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) {
        double dn = double(n);
cout << exp(dn * log(10)) << " - " << exp(dn * log(9)) << " + 1" << endl;
        return int(exp(dn * log(10)) - exp(dn * log(9))) + 1;
    } else {
        int 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);
        cout << "i = " << i << ", tmp = " << tmp << ", dikiy(tmp, i) = " << dikiy(tmp, i) << endl;
        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;
}

[Obey-Kun]

дай ссылку

[Акоб]

Enter fucking positive number: 1000
1000 - 729 + 1
i = 3, tmp = 1, dikiy(tmp, i) = 271
1000 - 729 + 1
Your answer is 271, dumbass.
Press any key to continue

[Obey-Kun]

Мне для этого моего кода скорость выполнения посчитать или что?

[Акоб]

#include<iostream.h>

int stepen(int);

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;
}

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

я тогда перепутал

[Obey-Kun]

Маленькое время получается, я щас под шафе и померить точнее не могу.

1000 - 729 + 1
Your answer is 271, dumbass.

Кааак? Почему???
А если сделать так?

#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) {
        double dn = double(n);
        cout << exp(dn * log(10)) << " - " << exp(dn * log(9)) << " + 1" << endl;
        cout << int(exp(dn * log(10))) << " - " << int(exp(dn * log(9))) << " + 1" << endl;
        return int(exp(dn * log(10))) - int(exp(dn * log(9))) + 1;
  } else {
        int 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);
        cout << "i = " << i << ", tmp = " << tmp << ", dikiy(tmp, i) = " << dikiy(tmp, i) << endl;
        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;
}