Se pot obține 100p cu liste liniare alocate dinamic ?

La a doua problema, tu tratezi doar cazul în care n are două cifre, ceea ce nu e specificat în enunț. ( n ar putea avea 5 cifre).
În plus, cât timp t < n executa e bucla infinită pentru că t nu își modifică valoarea.

[grupa 3.]

FiÅŸierul de intrare seriale.in va contine pe prima linie 2 numere naturale N si K. Pe linia 2 vor fi N numere reprezentand indicii serialelor din prima grupa. Pe linia 3 vor fi K numere reprezentand indicii serialelor din grupa 3.

Trebuia sa fie grupa 2, nu ? 

Am primit un mail de la infoarena newsletter care spune ca prima runda a concursului Algorimiada are loc pe 5 decembrie, dar pe pagina concursului scrie ca e pe 6 decembrie...

Din câte știu eu nu există soluție polinomială la problema asta. https://en.wikipedia.org/wiki/Addition-chain_exponentiation.

Unde ai găsit enunțul?

E temă de laborator... și am încercat s-o rezolv cu programare dinamică, am căutat o formulă, apoi nu am mai avut idei.

Dacă nu ai nicio idee, poți să te uiți la comentarii:

http://www.infoarena.ro/problema/flori

Fie n și k două numere naturale. Definim m(k) = numărul minim de înmulțiri
pentru a obține nk. Spre exemplu, pentru k =15, avem m(15) = 5, întrucât:
n * n = n^2
n^2 * n = n^3
n^3 * n^3 = n^6
n^6 * n^6 = n^12
n^12 * n^3 = n^15
Scrieți un program în C care calculează m(1) + m(2) + .... + m(200).

Am nevoie doar de o idee de rezolvare ? De un hint, de orice m-ar putea ajuta să-mi dau seama cum aș putea rezolva problema...

Este acceptata si solutia
1 2 3
5 6

?

Acest indiciu mi-a zis că sunt pe drumul cel bun. Nu aveam în minte o metodă clară de a implementa această idee. Într-un final, am găsit o cale. Dar presupun că trebuie să-i fac o îmbunătățire. Am luat 80p. Mai am o idee, dar are aceeași complexitate ca ultima sursă trimisă.

E doar mult de scris, nu înțeleg unde ai probleme.

Există un indicator care arată unde s-a ajuns cu citirea fișierului.
De exemplu, să luăm aceleași date de intrare: 10 9 8 7 6 5 4 3 2 1
Când indicatorul ajunge la 1 el nu știe ca acolo se termină fișierul, mai încearcă o citire și atunci descoperă că a ajuns la final. Și îți afișează de două ori ultima valoare pentru că afișezi fără verifici dacă s-a ajuns la final.

Cod:

    while( !fin.eof() )
    {
        fin >> x;
        cout << x << ' ';
    }

Un alt mod de a evita asta, deși eu le prefer pe celelalte două, este:

Cod:

# include <fstream>
# include <iostream>
using namespace std;

int main()
{
    ifstream fin("date.txt");

    int x;
    while( !fin.eof() )
    {
        fin >> x;
        if( fin.eof() ) break;
        cout << x << ' ';
    }

    fin.close();
    return 0;
}

Poți să-mi dai un hint ?

[date.txt]

Trebuie să faci o citire înainte de while și nu o să mai pățești asta.

Fișierul date.txt:

Cod:

10 9 8 7 6 5 4 3 2 1

Cod:

# include <fstream>
# include <iostream>
using namespace std;

int main()
{
    ifstream fin("date.txt");

    int x;
    while( !fin.eof() )
    {
        fin >> x;
        cout << x << ' ';
    }

    fin.close();
    return 0;
}

Programul afișează 10 9 8 7 6 5 4 3 2 1 1

Cod:

# include <fstream>
# include <iostream>
using namespace std;

int main()
{
    ifstream fin("date.txt");

    int x;
    fin >> x;
    while( !fin.eof() )
    {
        cout << x << ' ';
        fin >> x;
    }

    fin.close();
    return 0;
}

Programul afișează 10 9 8 7 6 5 4 3 2 1

Sper că ți-am fost de ajutor.

PS: Poți să scrii programul și așa, dacă vrei:

Cod:

# include <fstream>
# include <iostream>
using namespace std;

int main()
{
    ifstream fin("date.txt");

    int x;
    while( fin >> x )
        cout << x << ' ';

    fin.close();
    return 0;
}

1) Nu e corectă. Tu verifici dacă a È™i b dau acelaÈ™i rest la împărÈ›irea cu k, iar de aici nu rezultă că ele îl au ca divizor comun pe k ( de exemplu: a=3 b=7 k=2 3%2=1 7%2=1. însă 2 nu e divizor nici pentru a,nici pentru b ) CondiÈ›ia ar trebui să fie „a%k = 0 È™i b%k = 0”. Ar trebui să începi cu k de la 2 până la a/2 (b/2) [o să încerc să explic asta mai jos], orice număr se împarte la 1. ÃŽn afară de asta, am văzut că ai vrut să tratezi cazul în care numerele nu au divizori comuni. Nu poÈ›i face pur È™i simplu o ramură de "altfel". Poate că acea condiÈ›ie nu e adevărată pentru k=2 È™i e adevărată pentru k=3, în cazul ăsta, algoritmul afiÈ™ează: "nu se pot determina divizorii comuni 3...". ( de exemplu: a = 3 b = 12  când k = 2 algoritmul scrie "nu se pot determina divizorii comuni" È™i, la pasul următor, scrie 3 ). Trebuie să iei o variabilă logică, să îi spunem ok. Dacă ok = 0, atunci nu ai găsit niciun divizor comun. Dacă ok = 1, atunci ai găsit cel puÈ›in un divizor comun. ÃŽl iniÈ›ializezi pe ok cu 0 È™i în momentul când găseÈ™ti un divizor îi atribui lui ok 1. ÃŽn rest, ar trebui să meargă.
Cum am zis mai sus, eu m-aș fi folosit de Cel Mai Mare Divizor Comun și aș fi scris ceva de genu ăsta:

a,b,copa,copb,r,k,cmmdc,ok întreg
citește a,b

copa = a
copb = b

cât timp b != 0 execută
r = a%b
a = b
b = r
sfârșit cât timp

cmmdc = a
a = copa
b = copb
ok = 0
pentru k <- 2,cmmdc execută
    dacă a%k == 0 È™i b%k == 0 atunci
        scrie k
        ok = 1
    sfârÈ™it dacă

dacă ok = 0 atunci
    scrie "Numerele nu au divizori comuni."
sfârșit dacă

Explicație pentru k <- 2,număr/2:
O proprietatea a oricărui număr întreg este că se împarte la 1 și la el însuși. Asta se știe. Nu știu dacă se poate demonstra, e ceva evident.

Mai întâi să luăm un exemplu, să spunem că numărul e 24. Divizorii lui 24 sunt 2,3,4,6,8,12. Ce înseamnă că numărul x este divizor a lui y ? Rezultă că există z întreg ( natural în cazul ăsta ) astfel încât y = x*z.
24 = 2*12
24 = 3*8
24 = 4*6
24 = 6*4
24 = 8*3
24 = 12*2

Dacă am merge peste jumătatea numărului, ar ieși ceva de genul ăsta număr = (număr/2+1)*2 =>
număr = ((număr+2)/2)*2 =>
număr = număr+2 ceea ce este imposibil.

2) Îți voi spune mai întâi ce face algoritmul tău pentru problema 2. Citește un n, verifică dacă n dă un rest mai mic decât n la împărțirea cu numerele de la 1 la n, ceea ce e adevărat pentru fiecare i ( i <-1,n ). Și însumează numerele de la 1 la n în variabila s. Algoritmul, pentru n = 5, afisează: 1,3,6,10,15.

Tu trebuie să faci suma cifrelor lui i în variabila s și apoi să verifici dacă e mai mică sau egală cu n.

Scrieți un program care citește 5 numere întregi și calculează suma celor
mai mari 3 numere dintre ele pe baza unui algoritm ce realizează un număr
minim de comparații. Câte comparații realizează algoritmul vostru?

Cod:

# include <stdio.h>
# include <limits.h>

int main()
{
    int a,b,c,d,e,m1,m2;
    m1 = m2 = INT_MAX;

    scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
    if( a <= b )
    {
        if( a < m1 ) m1 = a;
        if( b < m2 ) m2 = b;
    }
    else
    {
        if( a < m2 ) m2 = a;
        if( b < m1 ) m1 = b;
    }

    if( c <= d )
    {
        if( c < m1 ) m1 = c;
        if( d < m2 ) m2 = d;
    }
    else
    {
        if( c < m2 ) m2 = c;
        if( d < m1 ) m1 = d;
    }

    if( e < m1 )
    {
        m2 = m1;
        m1 = e;
    }
    else if( e < m2 )
        m2 = e;

    printf("%d",a+b+c+d+e-m1-m2);

    return 0;
}

Algoritmul meu face 7 comparații. Se pot face mai puține comparații ?

Singurul mod de a te a verifica e cu creionul pe hârtie. Să faci un tabel cu valorile variabilelor la fiecare pas și să iei mai multe cazuri (mai multe seturi de date de intrare ) și să verifici dacă datele de ieșire sunt cele așteptate.

La primul algoritm nu ar trebui să ai o ramură de "altfel" la "daca a < b atunci" ? Ce se întâmplă dacă b e mai mare ? În locul tău, m-aș fi ajutat de CMMDC.
Al doilea algoritm e bun.

Chiar dacă făceai programul pe calculator și îl compilai, nu ți-ar fi dat eroare dacă algoritmul e greșit. Erorile pe care ți le-ar arăta compilatorul ar fi erori de sintaxă, de alocare a memoriei, etc. El nu are cum să știe dacă algoritmul tău e bun sau nu, asta e sarcina ta.

Pentru că n nu mai are niciun divizor după n/2 în afară de n. Nu are rost să verifici dacă n e divizibil cu n/2+1,n/2+2... pentru că știi sigur că nu e.

Dacă e vorba de divizori improprii ( de obicei, atunci când nu se specifică, e vorba de divizorii proprii ), poți modifica algoritmul astfel:

n,div,nr,sum intreg
citeste n
nr = 0
sum = 0
scrie 1,
pentru div <- 2,n/2 executa
{
    daca n % div = 0 atunci
    {   
         scrie div,
         nr = nr+1
         sum = sum + div
    }
}
scrie n
scrie nr, sum

Am scos reinit()-urile și am folosit un vector pentru a determina cea mai mare secvență de unu. Cum aș mai putea să reduc complexitatea ?

[V]

În loc de sortare am construit un vector V cu proprietatea că V[ i ] reține numărul secvențelor de cel puțin i de 1.

Puțin off-topic:
Am încercat să implementez asta și pentru logs, dar am luat 60p. Am citit câteva comentarii și după am încercat să fac citirea cu parsare, dar nu m-am ridicat mai sus de 60p.

După, am zis să încerc ideea cu sortarea, dar am luat 30p...( folosind qsort din stdlib )

Mersi pentru răspuns. 
Nu pot să cred că rezolvarea era așa de simplă și nu am văzut-o.

[B]

Fie B o matrice binară (elemente numai 0 și 1) cu L linii și C coloane. Vrem
să gasim valoarea m cea mai mare astfel încât există o sub-matrice pătratică M
de dimensiuni m x m din B care are toate elementele = 1. Dacă este permisă
permutarea coloanelor lui B scrieți un program care calculează m.

Iau o matrice m[i..L][j..C] cu proprietatea că m[ i ][ j ] = suma elementelor matricei pătratice cu colțul din stânga sus în i și colțul din dreapta jos în j. Verific dacă această sumă e egală cu "latură la pătrat", apoi păstrez cea mai mare astfel de sumă.

Nu reușesc să-mi dau seama cum ar trebui să îl aflu pe m, dacă se pot permuta coloanele.

PS: Nu e o obligatoriu să se folosească programarea dinamică.

[nr]

Variabila care "numără" divizorii e nr.

nr = 0
daca n % div = 0 atunci
    nr = nr+1

( daca div e un divizor a lui n , atunci nr e incrementat )

Div ia valori de la 2 pentru că orice număr are ca divizori improprii numărul și 1. Nu are sens să verific dacă 6 e divizibil cu 1 pentru că știu deja asta. Am zis mai sus că nu am înțeles dacă cerința se referă la numărul de divizori proprii, dar am presupus că așa e.

ex:
divizorii improprii a lui 6: 1,6
divizorii proprii a lui 6: 2,3

Dacă vrei să afișezi și divizorii improprii, poți să faci mici modificări în algoritm.

Formula de arie pare bună.

[pentru]

Poți să rezolvi toate cerințele cu un singur algoritm.
Nu înÈ›eleg dacă cerinÈ›a se referă la numărul de divizori proprii sau improprii ai numărului n. 

Acum, ceea ce nu înțeleg la algoritmul tău:
- de ce n <- 0,9
- de ce i <- i+n
- unde e rezolvarea celorlalte 2 

Ceea ce ar trebui să faci este să parcurgi cu o structură pentru ( div <- 2,n/2 ) posibili divizori ai numărului și să verifici dacă sunt divizori proprii ( adică dacă n % div = 0 ) . În cazul în care sunt, îi scrii, îi numeri și îi însumezi.

n,div,nr,sum intreg
citeste n
nr = 0
sum = 0
pentru div <- 2,n/2 executa
{
    daca n % div = 0 atunci
    {   
         scrie div,_
         nr = nr+1
         sum = sum + div
    }
}
scrie nr, sum

N-am prea stat pe el, dar cred că http://www.artofproblemsolving.com/community e printre cele mai importante.

E exact ce îmi trebuia.

Eu prima data am căutat în română, am găsit câte ceva, dar nimic activ. Când am căutat în engleză am găsit niște chestii care arătau deplorabil.