309 Chernel

[•DITzoneC]

Aici puteţi discuta despre problema Chernel.

[•astronomy]

Testul 6 nu respecta conditia N <= 100.000

[•bogdan2412]

Pot sa zic ca e fix 999999...
In arhiva probabil ca se poate mari limita la 1 milion... dar pentru concurs cam trebuie reevaluat

Cod:

#include <stdio.h>

int N, M;

int main()
{
        freopen("chernel.in", "rt", stdin);
        freopen("chernel.out", "wt", stdout);
        scanf("%d %d", &N, &M);
        if (N == 999999)
                while (1)
                        printf("\n");
        printf("0");
        return 0;
}

Ia TLE pe testu 6 si incorect(evident) pe restu

[•airineiv]

Oare sunt disponibile fisierele de test pentru aceasta problema? Ma chinui de mult timp sa o rezolv si nu stiu de ce nu iese..
Initial m-am "prins" ca coeficientii din forma numarului final sunt de fapt combinari de N-1 luate cate k, unde k=0,..., N-1. Conditia gandita de mine ar fi sa determin care din acesti coeficienti dau restul 0  prin impartire la M.
M-am impotmolit in combinari de n luate cate k care ia si mult timp, da si stack overflow daca e prin programare dinamica pentru N foarte mare... si intr-o solutie in care folosesc doua tablouri pentru stocarea valorilor intermediare ale coeficientilor aici am reusit sa scap de stack overflow si am adus timpul la valori mai bune dar obtin doua rezultate incorecte la doua teste. In ambele variante pentru N mare se obtin coeficienti foarte mari care depasesc chiar maximul pe 64 de biti, si aici trebuie implementate operatiile cu numere mari probabil... Poate cineva sa ma ajute la aceasta problema? Sunt dispus sa arat si codul meu care da asemenea probleme.

[•cos_min]

fisierele oficiale (in/out) pt evaluare nu vor fi facute publice...

[•airineiv]

ma gandeam ca asa e...ca nu vor fi facute publice. Nu  ma voi lasa pana nu voi scoate peste 50 de puncte macar. Nu am crezut la inceput ca va fi atat de dificila rezolvarea acestei probleme.
Daca imi scrie acolo Incorect in dreptul evaluarii inseamna ca am facut o eroare de algoritm in cod, nu?
Si totusi mie imi este clar ca e vorba de calcularea   combinari de N-1 luate cate k, unde k ia valori de la 0 la N-1. 

[•alex_damian]

C(n,k) = C(n,k-1) * (n-k+1) / (k-1) .. nu ajuta ?? (cred ca e corect....)

edit: si daca vrei suma S = suma(0,n) C(n,k) = 2^n;

[•airineiv]

Eu cred mai degrab ca C(n,k)=(n/k)*((n-1)/(k-1))*...*((n-k+2)/2)*((n-k+1)/1) imi poate fi mai de folos. Adica restul lui C(n,k) mod M == 0 <==>
unul din termenii produsului modulo M este 0.

[•astronomy]

Este o problema in arhiva Pascal (numarul 52) din care te-ai putea inspira. Are si solutie oficiala la sectiunea articole (preoni2005, runda 2) 

[•danalex97]

Pentru cei care iau 80p punteti long long