Zadanie Suma Cyfr - 2 etap XXIV OI

Question

Cześć, mam problem z zadaniem Suma Cyfr z 24OI.

https://szkopul.edu.pl/problemset/problem/Ng815bt4Fko9lj2-l7eVl3Aw/site/?key=statement

Podejrzewam, że chodzi tutaj o sprytnego dpka, ale zupełnie nie wiem jak do tego podejść, a do zadania nie ma omówienia.

Answer 1

Zacząłbym od ograniczenia m = 1 oraz powbijalbym te prostsze ograniczenia. Zastanów się jak skonstruować dp-ka, dla m = 1. Z tego co dobrze czytam ograniczenia to jak zrobisz to + te prostsze to można już 80pkt zgarnąć. Na konkursie jedna z strategi jest robienie od najpostszych ograniczeń, bo po 1 masz już jakieś punkty a po drugie jaka jest szansa, że wymyślisz całe rozwiązanie zadania, jak nie umiesz go jeszcze zrobić dla m = 1?

Comments

Ograniczenie m=1 to już spora część zadania. Masz może pomysł jak to zrobić dla m=1 i k <= 10^9?

---

Nie myślałem nad tym za dużo, ale jak tak zacząłem, to myślę, że dobrą próbą (nie wiem jeszcze, czy dobrą, ale intuicja mi tak mówi) jest naliczenie digit dp, w sposób, że dp[i][j][k] - ile jest liczb mające i cyfr, zaczynające się na cyfrę j, mające sumę k. Takiego dp-ka można sobie łatwo policzyć, tylko pytanie jak odtworzyć wynik. No i teraz chyba da się to zrobić od tyłu. W sensie najpierw szukasz ilocyfrowa jest liczba, znajdujesz pierwszą jej cyfrę, odejmujesz k o ile było wcześniejszych liczb i szukasz drugą cyfrę itd. Chyba to poprostu zadziała.

---

Tak jak pisałem. Dokładnie ten dp działa. Ifujesz pierwsze 3 ograniczenia na łącznie 20pkt, mi ten dp wszedł na 60pkt i już masz 80. Teraz jeszcze muszę się zastanowić jak zrobić to podzielność, ale podejrzewam, że wystarczy dodać kolejny stan do dp, ale muszę to przemyśleć jeszcze, ale opiszę dokładniej tego dp-ka.

Robisz właśnie to dp: dp[i][j][k] - ile jest liczb mające i cyfr, zaczynające się na cyfrę j, mające sumę k. Liczysz to banalnie prosto. Iterujesz się najpierw po długości, potem po sumie, potem po każdej cyfrze [0,9] i liczysz dp z sumy - wartość cyfry. Tylko musisz zrobić coś takiego, że te wartości potencjalnie chyba mogą przekroczyć max_K (10^18), to robisz sobie zmienną nieskończoność, np. INF, no i jak wartość w dp przekracza 10^18, to dajesz INF, żeby się z long longa nie przerzuciło.

Jak masz naliczone to dp, to robisz dwie rzeczy. Na początku znajdujesz długość wyniku i jaką ma pierszą cyfrę (zgodnie z treścią zadania, jak odpowiedź dłuższa niż 200, to piszesz NIE). Robisz to tak, że idziesz po długościach liczby, 1,2,3,4.... i,  dla każdej długości iterujesz się po cyfre 0,1,2,3,4...j(do 9) dodajesz do sumy wartość z dp[i][j][s] i szukasz pierwszego momentu takiego, ze ta suma jest >= k_i. Jak jest to znalazłeś tą cyfrę. Odejmujesz od s tą pierwszą cyfrę i szukasz jaka będzie na drugiej pozycji praktycznie identycznym sposobem.

np popatrz na mój kod, wydaje się być dość czytelny:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t), t.end()

int s = 0, m = 0, q = 0, len = 0, akt_s = 0;
const int max_dlugosc = 201, ile_cyfr = 10, max_S = 205;
ll k = 0, INF = 1e18+50;
ll dp[max_dlugosc][ile_cyfr][max_S];
char T[10];

inline ll znajdz()
{
    ll sum = 0;
    bool czy_robimy = true;
    for (int i = 1; i < max_dlugosc and czy_robimy == true; ++i)
    {
        for (int j = 1; j < ile_cyfr and czy_robimy == true; ++j)
        {
            sum += dp[i][j][akt_s];
            if (sum >= k)
            {
                k -= sum - dp[i][j][akt_s];
                len = i;
                return j;
                czy_robimy = false;
            }
        }
    }
    return -1;
}

inline ll znajdz2(int ile)
{
    ll sum = 0;
    bool czy_robimy = true;
    for (int i = 0; i < ile_cyfr and czy_robimy == true; ++i)
    {
        sum += dp[ile][i][akt_s];
        if (sum >= k)
        {
            k -= sum - dp[ile][i][akt_s];
            return i;
            czy_robimy = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    rep(i,10)
        dp[1][i][i] = 1;
    for (int i = 2; i < max_dlugosc; ++i)
    {
        rep(k,max_S)
        {
            rep(j,ile_cyfr)
            {
                int idx = k-j;
                if (idx < 0)
                    continue;
                rep(f,ile_cyfr)
                    dp[i][j][k] = min(INF, dp[i][j][k] + dp[i-1][f][idx]);
            }
        }
    }
    T[0] = '0', T[1] = '1', T[2] = '2', T[3] = '3', T[4] = '4', T[5] = '5', T[6] = '6', T[7] = '7', T[8] = '8', T[9] = '9';
    cin >> s >> m >> q;
    if (m != 1)
    {
        cout << "NIET" << '\n';
        return 0;
    }
    while(q--)
    {
        cin >> k;
        string res;
        akt_s = s;
        int pierwsza_cyfra = znajdz();
        if (pierwsza_cyfra == -1)
        {
            cout << "NIE" << '\n';
            continue;
        }
        akt_s -= pierwsza_cyfra;
        res.pb(T[pierwsza_cyfra]);
        for (int i = 2; i <= len; ++i)
        {
            int cyfra = znajdz2(len-i+1);
            akt_s -= cyfra;
            res.pb(T[cyfra]);
        }
        if (k > 1 or res.size() > 200)
            cout << "NIE" << '\n';
        else
            cout << res << '\n';
    }
    return 0;
}

Jakbyś czegoś nie rozumiał, to pisz. Jak wpadnę, na to, jak dodać do dp-ka m, to się odezwę.

---

A i tak wgl, jak zrobisz to zadanie to z tego 24 OI-a z 2 etapu możesz popatrzeć sobie na zadanie Strajki i Kontenery. Moim zdaniem oddają.

---

@pasjonat_algorytmiki, dzięki za pomoc.

 

Answer 2

Udało mi się to rozwiązać wystarczyło trochę pozamieniać twoje rozwiązanie, usunąłem stan z pierwszą cyfrą (bo nie wchodziło czasowo) i dodałem stan z modulo. Kod jest dosyć prosty i krótki, dlatego uważam, że idzie zrozumieć bez tłumaczenia, chętnie odpowiem na ewentualne pytania.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 201;
const long long inf = 1e18 + 1;

int s, m, q;
ll pot[N]; //10^n % m
ll dp[N][N][N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> s >> m >> q;

	dp[0][0][0] = 1;
	pot[0] = 1;
	for (int i = 1; i < N; i++) {
		pot[i] = pot[i - 1] * 10 % m;
		for (int j = 0; j <= s; j++) {
			for (int k = 0; k < m; k++) {
				for (int l = 0; l <= min(9, j); l++) {
					dp[i][j][k] += dp[i - 1][j - l][(k + 10*m - l*pot[i-1]) % m];
					dp[i][j][k] = min(dp[i][j][k], inf);
				}

			}
		}
	}

	while (q--) {
		ll k;
		cin >> k;
		if (dp[N-1][s][0] < k) {
			cout << "NIE\n";
			continue;
		}

		string res = "";
		bool zeros = true; //czy (jeszcze) stawiam zera na poczatku liczby
		int cs = s; //aktualna suma
		int cm = 0; //aktualne modulo
		for (int i = N-1; i > 0; i--) {
			for (int l = 0; l <= min(9, cs); l++) {
				ll val = dp[i - 1][cs - l][(10*m + cm - l*pot[i-1]) % m];
				if (k <= val) {
					if (!zeros || l > 0 || i == 1) {
						res += (char) (l + '0');
						zeros = false;
					}
					cs -= l;
					cm = (10*m + cm - l*pot[i-1]) % m;
					break;
				}
				k -= val;
			}
		}
		cout << res << "\n";
	}
}