Найдите пару натуральных чисел, которые имеют наименьшую энергию среди всех пар, имеющих сумму n

Question

Существует натуральное число n. Вы должны найти пару натуральных чисел x, y, сумма которых равна n, а также иметь наименьшую энергию среди других пар, имеющих сумму n.

Energy(x) = sum of all digits of x
Total Energy = Energy(x) + Energy(y)

1 <= n <= 10^9

For eg, 
n = 10000
A few pairs: 
5000 + 5000 -> Energy = 10
1000 + 9000 -> Energy = 10
9999 + 1 -> Energy = 37
2999 + 7001 -> Energy = 37

So possible answers are:
(5000, 5000), (1000, 9000) etc

Я пробовал решение, упомянутое выше, но это не оптимизированный подход

Я буду l oop от 1 до n-1 и попробую все пары и проверим их сумма цифр, но это займет слишком много времени для больших чисел. Например,

n= 50

1,49--> energy 14
2,48--> energy 14
3,47--> energy 14
4,46--> energy 14
5,45--> energy 14
.
.
.
.
10,40-->energy 5

(отредактировано). Подумав, я пришел к следующему решению. Был бы признателен, если кто-то может предложить лучшее решение

public int sum(int n) {
    String s = String.valueOf(n);
    if (isNonZeroOnlyOne(n)) {
        int num = getNonZeroNo(n);
        if (num == 1)
            return 10;
        return num;
    }
    return calculateEnergy(s);
}

private int calculateEnergy(String s) {
    int sum = 0;
    for(int i=0; i<s.length(); i++)
        sum += s.charAt(i) - '0';
    return sum;
}

private int getNonZeroNo(int n) {
    String s = String.valueOf(n);
    for(int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if (c != '0')
            return c-'0';
    }
    return '0';
}

private boolean isNonZeroOnlyOne(int n) {
    String s = String.valueOf(n);
    int count = 0;
    for(int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if (c != '0')
            count++;
        if (count > 1)
            return false;
    }
    return true;
}

Answer 1

Это просто.

, если n имеет тип 10 ^ x, тогда ответ равен 10. В противном случае ответ представляет собой сумму цифр n.

Идея в том, чтобы разбить число в пару, содержащую цифры меньше тех, которые присутствуют в n. если вы разберетесь на более мелкие цифры, сумма останется такой же, как и исходное число. пример для 7 = 1-6,2-5,3-4.

для таких чисел, как 100, 1000 .... di git 1 не может быть разбит на дальнейшие пары, поэтому мы попытайтесь сделать 10 как сумму di git так, чтобы сумма стала n. как для 10 = 5-5,2-8,3-7 100 = 20-80,40-60

для других чисел, например 123, его можно разбить на 100-23, 120-3, 111 -12 ... все даст вам сумму 6. которая является суммой цифр исходного числа.

если вы попытаетесь разбить на следующие пары, такие как 80-43, 52-71, вы увидите что сумма di git увеличивается по мере того, как вы разбиваетесь на число, содержащее цифры, которые больше, чем те, что присутствуют в n. как 8 4,5,7 больше 3.

Answer 2

Наименьшая энергия может быть получена по простой формуле.

1) При N> 100 пара может быть N-100 и 100, и энергия будет такой же, как энергия N. Например, : N = 500; Пара = 400 и 100; Энергия = 5

2) N> = 10 и N <= 100, пара = N-10 и 10, например: N = 50; Пара = 40 и 10; Энергия = 5 </p>

3) N> = 2 и N <= 10, пара = N-1 и 1, например: N = 5; Пара = 4 и 1; Энергия = 5 </p>

Answer 3

Приведенная ниже логика c будет охватывать все сцены ios

if (N%10 == 0) {

      x1= (N/10);
      x2 = N-x1
}else{

     x1 = N-10; 
     x2 = 10;
}

Answer 4

Я потратил более 1 часа на эту проблему. Какой должен быть ответ за n = 1? Поэтому я думаю, что n должно быть больше, чем 1 . Я предполагаю, что n > 1.

Таким образом, решение с использованием грубой силы здесь не сработает, поскольку n достаточно велико. Поэтому вам нужно более оптимизированное решение. Вам нужно подумать, сколько раз вам нужно carry 1 в сумме, чтобы сделать n. Это самое большее 9 раз!

Если у вас есть какая-то базовая c идея с digit-dp(Dynamic Programming), тогда эта проблема проста. Постарайтесь разместить все возможные ди git на месте n и взять среди них минимум энергии. Эта проблема проста, когда вы полностью понимаете digit-dp технику. Вы можете узнать это у здесь и здесь .

На практике вы можете найти множество проблем здесь ( Dynami c program section).

Для ваших ссылок я написал этот код только сейчас, и он работает правильно. Надеюсь, что вы можете использовать это как ссылку.

#include <bits/stdc++.h>

using namespace std;

const string INF_STRING = "9999999";
const int INF_INT = 9999999;

pair<string, int> INF = make_pair(INF_STRING, INF_INT);

int nod;
int digits[10];

int num_of_digits(int a) {
    int cnt = 0;
    while(a) {
        digits[cnt] = a % 10;
        a = a / 10;
        cnt++;
    }
    return cnt;
}

pair<string, int> dp[10][2][2][2];

pair<string, int> solve(int ind, int carry, bool is1, bool is2) {
    if(ind >= nod) {
        if(carry != 0 ||  !is1 || !is2) return INF;
        return make_pair("", 0);
    }
    pair<string, int> &ret = dp[ind][carry][is1][is2];
    if(ret.second != -1) return ret;
    ret = INF;
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            int s = (i + j + carry);
            pair<string, int> cur = INF;
            if(s % 10 == digits[ind]) {
                cur = solve(ind + 1, s / 10, is1 || (i > 0? 1:0), is2 || (j > 0? 1:0));
            }
            if((cur.second + i + j) < ret.second) {
                ret.second = cur.second + i + j;
                ret.first =  cur.first + (char)(i + '0');
            }
        }
    }
    return ret;
}

int stringToInt(string num) {
    stringstream ss;
    ss<<num;
    int ret;
    ss >> ret;

    return ret;
}

int main() {
    int i, t, cases = 1, j, k, pos;
    int n;

    scanf("%d", &n);
    nod = num_of_digits(n);

    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 2; j++) {
            dp[i][j][0][0] = make_pair(INF_STRING, -1);
            dp[i][j][0][1] = make_pair(INF_STRING, -1);
            dp[i][j][1][0] = make_pair(INF_STRING, -1);
            dp[i][j][1][1] = make_pair(INF_STRING, -1);
        }
    }

    pair<string, int> res = solve(0, 0, 0, 0);

    string num1_str = res.first;
    int num1 = stringToInt(num1_str);
    int num2 = n - num1;

    printf("Minimum Energy: %d\n", res.second);
    printf("Num1 = %d, Num2 = %d\n", num1, num2);


    return 0;
}

/*
Input:
10000

Output:
Minimum energy: 10
Num1 = 1000, Num2 = 9000

*/