Liczba potyczkowa

pytanie zadane 29 grudnia 2022 w C i C++ przez polandonion Mądrala (7,040 p.)
edycja 29 grudnia 2022 przez polandonion

Liczba potyczkowa. Siedze nad tym juz jakies 2 dni i absolutna pustka. Oczywiscie udalo mi sie zrobic bruta, ale to dalo mi tylko 20%. Naprowadzi ktos?

komentarz 29 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)

To było trudne zadanie. Trzeba zrobić 4 wymiarowego dp.

komentarz 29 grudnia 2022 przez TOWaD Mądrala (6,000 p.)

takie coś daje 20%?

komentarz 29 grudnia 2022 przez polandonion Mądrala (7,040 p.)

twoje daje 0%: link - w niektorych przypadkach wypisuje ci liczbe o 1 mniejsza

moj kod: link

komentarz 29 grudnia 2022 przez TOWaD Mądrala (6,000 p.)
edycja 29 grudnia 2022 przez TOWaD

no fakt for (size_t i=l; i<=r; i++)

edit: a to

komentarz 29 grudnia 2022 przez polandonion Mądrala (7,040 p.)
edycja 29 grudnia 2022 przez polandonion

troche lepiej, choć nadal nie wiecej niz ja - 20%: link

komentarz 29 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)

hint: dp[d][mod][mask][?] to liczba szukanych liczb x spełniające następujące warunki: mają długość d, x % MOD = mod, a mask to maska bitowa cyfr występujących w x. Pytanie jak dobrać MOD i czym jest ?

komentarz 29 grudnia 2022 przez polandonion Mądrala (7,040 p.)

Nie za bardzo ogarniam 4. wymiair. Nie ma innego rozwiązania?

komentarz 29 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)

Być może, ale wszyscy których sprawdzałem rozwiązali to w ten sposób. Kod jest całkiem krótki, trzeba tylko wymyslić rozwiązanie

btw nie trzeba rozumieć 4 wymiarów, tablica moze mieć tyle wymiarach ile chcesz :)

komentarz 30 grudnia 2022 przez TOWaD Mądrala (6,000 p.)
edycja 31 grudnia 2022 przez TOWaD

40% , jak by pokombinować z kolejnością i mod7, to może by się dało urwać 20%

edit: to max co z tego algorytmu można wyciągnąć. Jak by ktoś na priv lub tu pokazał wysłał rozwiązanie to bym zaspokoił swoją ciekawość

1 odpowiedź

odpowiedź 31 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)
wybrane 7 stycznia 2023 przez polandonion

Najlepsza

Jako że zadanie jest trudne i @TOWaD był ciekaw wzorcówki to wklejam poprawne rozwiązanie:

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <sys/resource.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef uint32_t ul;
typedef int32_t l;
typedef uint64_t ull;
typedef int64_t ll;

template <typename T>
using statistics_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const l INF = 1000000000 + 9;
const ll MOD = 2520;
const l PRIME = 200003;
const ll L_INF = 1000000000000000000LL + 7;
const double EPS = 1e-5;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)
#define ALL(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

ll lf, rt;
ll dp[20][MOD][515][2]; //prefix | modulo | mask | smaller
vector<l> num;


ll calc(l pos, l mod, l mask, bool smaller)
{
    if(dp[pos][mod][mask][smaller] != -1)
        return dp[pos][mod][mask][smaller];

    if(pos == num.size())
    {
        FORE(1, 9, d)
            if(mask & (1 << (d-1)) && (mod % d != 0))
                return 0;

        return 1;
    }

    l limit;
    if(smaller == 0)
        limit = num[pos];

    else limit = 9;

    dp[pos][mod][mask][smaller] = 0;
    FORE(1, limit, d)
    {
        bool n_smaller{smaller};
        if(d < limit)
            n_smaller = 1;

        dp[pos][mod][mask][smaller] += calc(pos+1, (mod*10+d)%MOD, mask | (1 << (d-1)), n_smaller);
    }

    return dp[pos][mod][mask][smaller];
}

ll prepare(ll v)
{
    if(v == 0)
        return 0;

    REP(20, i)  
        REP(MOD, j)
            REP(515, k)
                REP(2, m)
                    dp[i][j][k][m] = -1LL;

    num.clear();
    while(v)
    {
        num.PB(v%10LL);
        v /= 10LL;
    }

    reverse(ALL(num));

    ll res{0};
    res = calc(0, 0, 0, false);
    FOR(1, num.size(), i)
        res += calc(i, 0, 0, true);

    return res;
}

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

    cin >> lf >> rt;
    cout << prepare(rt) - prepare(lf-1) << "\n";
}

To rozwiązanie dostało na potyczkach 9 pkt (na 10), bo rekurencja była za wolna. Ale da się łatwo przepisać na zwykłe pętle i wtedy dostaje 10