ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1658. Sum of Digits

WA2 please help
Posted by Ghiorghiu Ioan-Viorel 25 Dec 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
Posted by Ghiorghiu Ioan-Viorel 25 Dec 2017 04:15
Nevermind, apparently I was calculating the number the wrong way, I found the mistake.