După zile întregi de muncă, vrăjitorul Arpsod a terminat de confecționat noua sa baghetă magică, cea mai puternică de până acum. Ca să o testeze, el s-a gândit la următorul antrenament: își va lua K ținte miscătoare și se va apuca să tragă în ele cu cea mai puternică vrajă a lui, “Blatus Blast”. Fiind o magie foarte solicitantă, vrăjitorul a hotărat că va trage doar de N ori. Arpsod este un trăgător extraordinar, astfel fiecare din cele N lovituri va nimeri exact una din cele K ținte. Într-o sesiune de N lovituri, unele ținte pot fi lovite de mai multe ori iar altele niciodată. Vrăjitorul consideră că sesiunea de antrenament este reușită numai dacă fiecare țintă a fost lovită CEL PUȚIN O DATĂ.

De exemplu, dacă avem 3 trageri și 2 ținte, avem următoarele 6 soluții:

1 1 2 ( unde 1 sau 2 reprezintă indicele țintei lovite )
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1

Cerința

În timp ce se odihnește pentru următoarea sesiune de antrenament, ca să mai treacă timpul, a început să numere în câte moduri ar fi putut lovi țintele astfel încât sesiunea de antrenament să fie una reușită.

Curioși din fire, v-ați apucat și voi să numărați dar, văzând că numărul modalităților devine prea mare, ați decis să vă mulțumiți cu restul împărțirii acestui număr la 666013.

Date de intrare

Pe prima linie a fișierului arpsohood.in se vor afla două numere naturale separate prin spațiu: N și K, reprezentând numărul de trageri pe care le va executa Arpsod respectiv numărul de ținte pe care le are la dispoziție.

Date de ieșire

În fișierul arpsohood.out se va scrie, pe prima și singura linie din fișier, numărul de moduri de a lovi țintele astfel încât fiecare țintă să fi fost lovită cel puțin o dată. Acest rezultat se va afișa modulo 666013.

Restricții și precizări

1 ≤ K ≤ N ≤ 500
O lovitură va atinge exact una dintre cele K ținte
Se garantează că pentru 20% din teste 1 ≤ K ≤ N ≤ 8

Exemplu

arpsohood.in

3 2

arpsohood.out

Explicație

Avem următoarele 6 soluții:
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Arpsohood:

// implementare: Cristi Dospra
// punctaj: 20p
// complexitate: O(K^N)

#include <fstream>
using namespace std;

#define Nmax 502
#define Mod 666013

ifstream fin ( "arpsohood.in" );
ofstream fout ( "arpsohood.out" );

int N, K, NrS = 0;
int Frecv[Nmax];

void bkt ( int poz ){

    if ( poz > N ){
        bool ok = 1;
        for ( int i = 1; i <= K; ++i )
            if ( !Frecv[i] ){
                ok = 0;
                break;
            }

        NrS = ( NrS + ok ) % Mod;

        return;
    }

    for ( int i = 1; i <= K; ++i ){
        Frecv[i]++;
        bkt ( poz + 1 );
        Frecv[i]--;
    }
}

int main(){

    fin >> N >> K;

    bkt ( 1 );

    fout << NrS;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1756 Arpsohood

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1756 Arpsohood de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1756 Arpsohood