Imprimă pagina - 309 Chernel

Titlul: 309 Chernel
Scris de: Adrian Diaconu din Ianuarie 27, 2007, 18:18:14

Aici puteţi discuta despre problema Chernel (http://infoarena.ro/problema/chernel).

Titlul: Raspuns: 312 Chernel
Scris de: Airinei Adrian din Ianuarie 28, 2007, 00:09:19

Testul 6 nu respecta conditia N <= 100.000

Titlul: Raspuns: 312 Chernel
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 28, 2007, 08:26:35

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

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

Titlul: Raspuns: 312 Chernel
Scris de: Airinei Vasile din Ianuarie 28, 2007, 15:33:06

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.

Titlul: Raspuns: 312 Chernel
Scris de: Bondane Cosmin din Ianuarie 28, 2007, 15:40:07

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

Titlul: Raspuns: 312 Chernel
Scris de: Airinei Vasile din Ianuarie 28, 2007, 16:02:58

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. :-k

Titlul: Raspuns: 312 Chernel
Scris de: Damian Alexandru din Ianuarie 28, 2007, 16:53:49

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;

Titlul: Raspuns: 312 Chernel
Scris de: Airinei Vasile din Ianuarie 28, 2007, 17:29:03

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.

Titlul: Raspuns: 312 Chernel
Scris de: Airinei Adrian din Ianuarie 28, 2007, 17:45:25

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

Titlul: Răspuns: 309 Chernel
Scris de: Dan H Alexandru din Iulie 03, 2012, 09:00:04

Pentru cei care iau 80p punteti long long :aha:

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Ianuarie 27, 2007, 18:18:14