ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1658. Сумма цифр

WA2 please help
Послано Ghiorghiu Ioan-Viorel 25 дек 2017 03:24
I keep getting WA2, but none of the threads posted here seem to help me: every example i found worked on my program, and i just can't see what's wrong with it. Can someone please tell me if they see anything that doesn't work within my program? Thank you in advance.
#define DM 8101
#define DN 901
#include <iostream>
#include <set>
#include <queue>
using namespace std;

int n, v, vp, s, sp, cf[DN][DM], dp[DN][DM];
multiset <int> ord;//ordering the elements
queue <int> q;//rebuild

void formare(int nrc, int car, int sum, int ptr)//no of digits, digit, sum, sumof squares
{
    if (nrc > 100 || (cf[sum][ptr] && cf[sum][ptr] <= nrc))
        return;
    cf[sum][ptr] = nrc;
    dp[sum][ptr] = car;
    for (int i = 9; i >= 1; --i)
        formare(nrc + 1, i, sum + i, ptr + i*i);
}

void realc(int s, int sp)
{
    if (!s || !sp || !dp[s][sp])
        return;
    q.push(dp[s][sp]);
    v+=dp[s][sp];
    vp+=dp[s][sp]*dp[s][sp];
    realc(s - dp[s][sp], sp - dp[s][sp]*dp[s][sp]);
}

int main()
{
    cin >> n;
    for (int i = 9; i >= 1; --i)
        formare(1, i, i, i*i);
    cf[0][0] = 1;
    dp[0][0] = 0;
    while (n--)
    {
        cin >> s >> sp;
        if (s > 900 || sp > 8100)
            cout << "No solution\n";
        else if (s == 0 && sp == 0)
            cout << "0\n";
        else
        {
            realc(s, sp);
            if (q.size() <= 100)
            {
                while (!q.empty())
                {
                    if (v == s && vp == sp)
                        ord.insert(q.front());
                    q.pop();
                }
                for (auto i:ord)
                    cout << i;
                ord.clear();
                if (v != s || vp != sp)
                    cout << "No solution";
                cout << '\n';
            }
            else
            {
                cout << "No solution\n";
                while (!q.empty())
                    q.pop();
            }
        }
        v = vp = 0;
    }
    return 0;
}
Re: WA2 please help
Послано Ghiorghiu Ioan-Viorel 25 дек 2017 04:15
Nevermind, apparently I was calculating the number the wrong way, I found the mistake.