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

[Obey-Kun]

Вот ещё одно решение:

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

using namespace std;

int bestpow(int a)
{
    int i = 0;
    while(a - pow(10, i) >= 0) {
        i = i + 1;
    }
    return i - 1;
}

/// Количество чисел БЕЗ единички в промежутке [1; k]
int f(int k)
{
    if(bestpow(k) <= 0) {
        if(k == 0) {
            return 1;
        } else {
            return k;
        }
    }
    
    if(int(k / pow(10, bestpow(k))) >= 2) {
        return (int(k / pow(10, bestpow(k))) - 1) * pow(9, bestpow(k))
               + f(k - int(k / pow(10, bestpow(k))) * pow(10, bestpow(k)));
    }
    
    if(int(k / pow(10, bestpow(k))) == 1) {
        return pow(9, bestpow(k));
    }
}

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

[Акоб]

извени Obey-Kun у меня компилятор сдох. ни хрена не понимаю((
дай дебаг своей программы.

[Obey-Kun]

Вместо bestpow можно int(log10(K))+1 или типа того
это отсюда -- http://www.linux.org.ru/forum/talks/5864969/
всё, я спать, а то пива нажрался

Акоб, http://programmersforum.ru/showpost....&postcount=112

[Акоб]

Enter fucking positive number: 201
i = 2, tmp = 2, dikiy(tmp, i) = 119
i = 1, tmp = 0, dikiy(tmp, i) = 0
i = 0, tmp = 1, dikiy(tmp, i) = 1
Your answer is 120, dumbass.
Press any key to continue

[Obey-Kun]

Так это правильный результат...

[Акоб]

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

[Obey-Kun]

А так для 1000?

#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);
        return 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]

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

а так?

[Акоб]

зачем нужно return exp(dn * log(10)) - exp(dn * log(9)) + 1;
не легче просто посчитать 10^n?

то же самое.



обьясни пожалуйста return tmp + (m - 2) * (tmp - 1) + pow(10, n) - 1;