минимальное положительное число, делимое на N

Question

1 <= N <= 1000 </p>

Как найти минимальное положительное число, которое делится на N, а его сумма должна быть равна N.

Например:N Результат:1: 110: 190

И алгоритм не должен занимать более 2 секунд.

Есть идеи (псевдокод, паскаль, с ++ или java)?

Answer 1

Пусть f (len, sum, mod) будет логическим значением, что означает, что мы можем построить число (возможно, с ведущими нулями), длина которого len + 1, сумма цифр равна сумме и дает mod при погружении на n.

Тогда f (len, sum, mod) = или (f (len-1, sum-i, mod-i * 10 ^ len), для i от 0 до 9). Тогда вы можете найти минимальное l, что f (l, n, n) верно. После этого просто найдите первую цифру, затем вторую и т. Д.

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, N) FOR(i, 0, N)

#define FILL(a,v) memset(a,v,sizeof(a))



const int maxlen = 120;
const int maxn = 1000;

int st[maxlen];
int n;

bool can[maxlen][maxn+1][maxn+1];
bool was[maxlen][maxn+1][maxn+1];

bool f(int l, int s, int m)
{
    m = m%n;
    if(m<0)
        m += n;

    if(s == 0)
        return (m == 0);
    if(s<0)
        return false;
    if(l<0)
        return false;   

    if(was[l][s][m])
        return can[l][s][m];

    was[l][s][m] = true;
    can[l][s][m] = false;

    REP(i,10)
        if(f(l-1, s-i, m - st[l]*i))
        {
            can[l][s][m] = true;
            return true;
        }
    return false;
}


string build(int l, int s, int m)
{
    if(l<0)
        return "";
    m = m%n;
    if(m<0)
        m += n;
    REP(i,10)
        if(f(l-1, s-i, m - st[l]*i))
        {
            return char('0'+i) + build(l-1, s-i, m - st[l]*i);
        }
    return "";
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);

    cin>>n;
    FILL(was, false);   
    st[0] = 1;
    FOR(i, 1, maxlen)
        st[i] = (st[i-1]*10)%n;
    int l = -1;
    REP(i, maxlen)
        if(f(i, n, n))
        {
            cout<<build(i,n,n)<<endl;
            break;
        }

    return 0;
}

ПРИМЕЧАНИЕ , что для этого используется ~ 250 МБ памяти.

РЕДАКТИРОВАТЬ : Я нашел тест, в котором работает это решение, слишком долго. 999, занимает почти 5 с.

Answer 2

Подумав немного, думаю, я нашел ожидаемый ответ.

Думайте об этом как о графике.Для любого номера вы можете создать новый номер, умножив его на 10 и добавив любую из цифр 0-9.Вам нужно будет использовать BFS, чтобы сначала набрать наименьшее число.

Для каждого узла сохраняйте сумму и остаток.Используя эти значения, вы можете перемещаться к соседним узлам, также эти значения помогут вам снова и снова избегать бесполезных состояний.Чтобы напечатать число, вы можете использовать эти значения для отслеживания ваших шагов.Сложность O (n ^ 2), в худшем случае таблица полностью заполнена.(См. Код)

Примечание : Код в первую очередь принимает количество тестов.Работает при 0,3 с для n <= 1000. </p>

[Редактировать] : Ac на спой в 6,54 с.Тестовые файлы имеют 50 номеров.

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define F first
#define S second 
#define N 1100
#define mp make_pair
queue<pair<int, int> >Q;
short sumTrace[N][N], mulTrace[N][N];

void print(int sum, int mul) {
    if (sumTrace[sum][mul] == 42)return;
    print(sum-sumTrace[sum][mul], mulTrace[sum][mul]);
    printf("%d",sumTrace[sum][mul]);
}
void solve(int n) {
    Q.push(mp(0,0));
    sumTrace[0][0]=42; // any number greater than 9
    while (1) {
        int sum = Q.front().F;
        int mul = Q.front().S;
        if (sum == n && mul == 0) break;
        Q.pop();
        for (int i=0; i<10; i++) {
            int nsum = sum+i;
            if (nsum > n)break;
            int nmul = (mul*10+i)%n;
            if (sumTrace[nsum][nmul] == -1) {
                Q.push(mp(nsum, nmul));
                sumTrace[nsum][nmul] = i;
                mulTrace[nsum][nmul] = mul;
            }
        }
    }
    print(n,0);
    while(!Q.empty())Q.pop();
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        memset(sumTrace, -1, sizeof sumTrace);
        solve(n);
        printf("\n");
    }
    return 0;
}

Answer 3

Конечно, псевдокод, так как он пахнет домашней работой: -)

def findNum (n):
    testnum = n
    while testnum <= 1000:
        tempnum = testnum
        sum = 0
        while tempnum > 0:
            sum = sum + (tempnum mod 10)
            tempnum = int (tempnum / 10)
        if sum == n:
            return testnum
        testnum = testnum + n
    return -1

Это занимает около 15 тысячных секунды, когда переводится на Python так хорошо под вашим двухсекундным порогом. Он работает, в основном, проверяя каждое кратное N меньше или равное 1000.

Тест проходит через каждую цифру числа, добавляя ее к сумме, затем, если эта сумма соответствует N, она возвращает число. Если число нет соответствует, оно возвращает -1.

В качестве тестовых случаев я использовал:

 n  findNum(n)     Justification
==  ==========     =============
 1           1       1 =  1 *  1,  1 = 1
10         190     190 = 19 * 10, 10 = 1 + 9 + 0
13         247     247 = 13 * 19, 13 = 2 + 4 + 7
17         476     476 = 17 * 28, 17 = 4 + 7 + 6
99          -1     none needed

Теперь, когда проверяется только число, кратное 1000, в отличие от проверки всех чисел, но проверка всех чисел начинает занимать намного больше двух секунд, независимо от того, какой язык вы используете. Вы можете найти более быстрый алгоритм, но я бы хотел предложить кое-что еще.

Вероятно, вы не найдете более быстрого алгоритма, чем тот, который требуется для простого просмотра значений в таблице. Итак, я бы просто запустил программу один раз , чтобы сгенерировать вывод в соответствии с:

int numberDesired[] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    190, 209, 48, 247, 266, 195, 448, 476, 198, 874,
    ...
    -1, -1};

, а затем просто подключите его к новой программе, чтобы он мог использовать ослепительно быстрый поиск.

Например, вы можете сделать это с помощью некоторого Python, например:

print "int numberDesired[] = {"
for i in range (0, 10):
    s = "    /* %4d-%4d */"%(i*10,i*10+9)
    for j in range (0, 10):
        s = "%s %d,"%(s,findNum(i*10+j))
    print s
print "};"

, который генерирует:

int numberDesired[] = {
    /*    0-   9 */ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    /*   10-  19 */ 190, 209, 48, 247, 266, 195, 448, 476, 198, 874,
    /*   20-  29 */ 3980, 399, 2398, 1679, 888, 4975, 1898, 999, 7588, 4988,
    /*   30-  39 */ 39990, 8959, 17888, 42999, 28798, 57995, 29988, 37999, 59888, 49998,
    /*   40-  49 */ 699880, 177899, 88998, 99889, 479996, 499995, 589996, 686999, 699888, 788998,
    /*   50-  59 */ 9999950, 889899, 1989988, 2989889, 1999998, 60989995, 7979888, 5899899, 8988898, 8888999,
    /*   60-  69 */ 79999980, 9998998, 19999898, 19899999, 59989888, 69999995, 67999998, 58999999, 99899888, 79899999,
:
};

Это займет намного больше времени, чем две секунды, но вот в чем дело: вам нужно только запустить его один раз, а затем вырезать и вставить таблицу в ваш код. Если у вас есть таблица, она, скорее всего, сметет любое алгоритмическое решение.

Answer 4

Максимальная сумма цифр, о которой вам нужно беспокоиться, составляет 1000. Поскольку 1000 / 9 = ~100 Это на самом деле не много, поэтому я думаю, что должно работать следующее:

Рассмотрим следующую структуру данных:

entry { int r, sum, prev, lastDigit; }

Удерживайте очередь entry там, где изначально у вас есть r = 1 mod N, sum = 1, prev = -1, lastDigit = 1; r = 2 mod N, sum = 2, prev = -1, lastDigit = 2 и т. Д.

При извлечении записи x из очереди:

y = new entry
for i = 0 to 9 do
  y.r = (x.r * 10 + i) % N
  y.sum = x.sum + i
  y.prev = <position of x in the queue>
  y.lastDigit = i

  if y.r == 0 and y.sum == N
    // you found your multiple: use the prev and lastDigit entries to rebuild it

  if y.sum < N then
    queue.add(y)

Это в основном BFS на цифрах. Поскольку максимальная сумма, о которой вы заботитесь, невелика, она должна быть достаточно эффективной.

Answer 5

Обновление: Я понял, что результат должен был быть между 0 и 1000, но нет. При больших входах наивный алгоритм может занять значительное время. Выход для 80 будет 29999998880.

---

Вам не нужен причудливый алгоритм. Цикл, который проверяет ваше состояние на 1000 номеров, займет менее 2 секунд на любом достаточно современном компьютере, даже на переведенных языках.

Если вы хотите сделать это умным, вам нужно только проверять числа, кратные N. Чтобы еще больше ограничить пространство поиска, остатки N и результат должны быть равны при делении на 9. Это означает, что теперь Вы должны проверять только один номер на каждые 9N.