Un gospodar are N iepuri (pe care i-a numerotat de la 1 la N) și foarte mulți morcovi. Ce e mai deosebit în această gospodărie este că iepurii sunt organizați ierarhic, în funcție de vârstă, autoritate și nevoile nutriționale. Astfel, fiecare iepure are exact un șef direct (exceptându-l pe Rilă Iepurilă, care este șeful cel mare, șeful tuturor iepurilor). Orice iepure poate avea 0, 1 sau mai mulți subordonați direcți. Orice iepure-șef va mânca cel puțin un morcov mai puțin decât fiecare dintre subordonații săi direcți. Gospodarul nu se poate hotărî câți morcovi să dea fiecărui iepure și ar vrea să știe în câte moduri poate împărți morcovi la iepuri știind că fiecare iepure poate să mănânce minim un morcov și maxim K morcovi.

Cerința

Scrieți un program care calculează numărul de posibilități modulo 30011 de a împărți morcovi la cei N iepuri știind că orice iepure poate mânca între 1 și K morcovi și trebuie să mănânce cu cel puțin un morcov mai puțin decât fiecare dintre iepurii care îi sunt subordonați direcți.

Date de intrare

Fișierul de intrare iepuri1.in conține pe prima linie două numere naturale N şi K, separate printr-un spațiu, reprezentând numărul de iepuri, respectiv numărul maxim de morcovi ce pot fi mâncați de un iepure. Pe fiecare din următoarele N-1 linii se află câte două numere naturale distincte a și b, cuprinse între 1 și N, separate printr-un spațiu, cu semnificația că iepurele a este șeful direct al iepurelui b.

Date de ieșire

Fișierul de ieșire iepuri1.out va conține numărul de moduri de a împărți morcovii conform condițiilor specificate în enunț, modulo 30011.

Restricții și precizări

1 ≤ N, K ≤ 100
Numărul ce trebuie scris în fişierul de ieşire va fi afişat modulo 30011.

Exemplu

iepuri1.in

iepuri1.out

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 iepuri1:

#include <cstdio>
#define NMAX 101
#define KMAX 103
#define MOD 30011

using namespace std;

int N, K, arb[NMAX][NMAX],
    rad, p[NMAX];

void readinput()
{
    int i;
    int a, b;

    freopen( "iepuri1.in", "r", stdin );
    scanf( "%d%d", &N, &K );

    for(i = 0; i < N - 1; i++ )
    {
        scanf( "%d%d", &a, &b );
        arb[a][ ++arb[a][0] ] = b;
        p[b]=a;
    }
    for( i = 1; i <= N; i++ )
        if( !p[i] ) rad = i;
}

int m[NMAX][KMAX];

void go( int rad )
{
    int i, k;
    for(i = 1; i <= arb[rad][0]; i++ )
        go( arb[rad][i] );

    for(k = K; k >= 1; k-- )
    {
        m[rad][k] = 1;
        for(i = 1; i <= arb[rad][0]; i++ )
            {
                m[ arb[rad][i] ][ k + 1 ] += m[ arb[rad][i] ][ k + 2 ];
                m[ arb[rad][i] ][ k + 1 ] %= MOD;

                int temp = m[rad][k];
                temp *= m[ arb[rad][i] ][ k + 1 ];
                m[rad][k] = temp % MOD;
            }
    }
}

void writeoutput()
{
    int sum = 0;

    for( int i = 1; i <= K; i++ )
    {
        sum += m[rad][i];
        sum %= MOD;
    }

    freopen("iepuri1.out", "w", stdout );
    printf("%d\n", sum);
}

int main()
{
    readinput();
    go( rad );
    writeoutput();
    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 #2173 iepuri1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2173 iepuri1 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 #2173 iepuri1