Pai asta e o problema clasica de dinamica.
Am nota prada[ i ] = prada maxima pe care ar lua-o hotul daca jefuieste "optim" in intervalul caselor 1...i,jefuind obligatoriu casa i
Deci prada [ i ] = A[ i ] + max(prada[i-2],prada[i-3]) , cu initializarile prada[0]=0, prada[1]=A[1], prada[2]=A[2] , eventual si prada[3]=A[3]+A[1] , iar recurenta o rulezi pentru i=4,n sau i=3,n

N-am inteles asta cu "jefuieste optim" dar si "jefuind obligatoriu casa i". Eu cred ca nu-ti da bine pe teste de genul asta:

Cod:

5 1 5 1 1 5 1 5

Deci prada[ i ] = prada maxima pe care o poate capata hotul jefuind case in intervalul 1....i ,casa i fiind obligatoriu jefuita.
Am uitat sa precizez ca solutia va fi max(prada[n],prada[n-1]).
Pe exemplul tau vectorul prada va fi :
0 5 1 10 6 11 15 12 20 iar solutia este max(12,20) = 20.  

Explicatia recurentei este ca prada[ i ] = A[ i ] (pentru ca jefuieste obligatoriu si casa i,deci i-1 nu este jefuita) + max(prada[i-2],prada[i-3]) - adica prada[i-2] ar insemna ca este jefuita si casa i-2 deci i-3 nu este jefuita,iar prada[i-3] inseamna ca i-3 este jefuita,i-2 nefiind in acest caz jefuita

Pentru 0 5 1 10 6 11 15 12 20 solutia este 50

Am luat-o ca o secventa dintr-un sir astfel incat suma sa fie maxima fara ca sa poti adauga la suma 2 numere consecutive din sir.

suma[0] = valoareA[0];
      suma[1] = max(suma[0],valoareA[1]);
      for(int i = 2; i < n ; i++)
         suma = max(suma[i-2] + valoareA[ i ] ,suma[i-1]);
Si in suma[n-1] e suma maxima.

Pe o strada, se afla un sir de N case (toate pe o singura parte). In fiecare casa i sunt bunuri de o anumita valoare A[i ]. Stiind ca un hot nu ar jefui niciodata 2 case alaturate (pentru a nu fi prins), sa se afle care este profitul maxim care l-ar putea obtine de pe acea strada. Avand in vedere ca se urmareste maximizarea profitului (evident, A[i ]>0), din fiecare casa jefuita hotul va fura toate bunurile disponibile.

Ceva indicii va rog?

[1]

Ca sa existe solutie , ai nevoie ca suma lor sa fie divizibila cu 2.  n * (n + 1) / 2  se divide cu 2 inseamna ca n se divide cu 4 sau n + 1 se divide cu 4.
Daca n e divizibil cu 4 iei toate perechile i , n - i + 1 si le pui pe rand, alternativ, in multimea celor negative respectiv a celor pozitive.

1 2 3 4 5 6 7 8 :  (1, 8 ) (3, 6) cu plus , celelalte cu minus.

Daca n + 1 e divizibil cu 4 faci aceeasi chestie pentru primele n - 1 numere, si pe al n-lea il pui in multimea cu suma mai mica.

1 2 3 4 5 6 7

Alternativ, poti face knapsack in O(n ^ 3).

Mersi mult, am gasit si un pattern pe pare si impare:
pare: + - pana la n/2 si apoi - + pana la n
impare: ++- si ramai cu o secventa para unde aplici patternul de la pare

Fa un back care sa iti afiseze toate solutiile pt n de la 1 la 20 de exemplu si gaseste un pattern.

Hmm, am sa incerc si lucrul asta . Sper sa fie ceva pattern iin secventele de semne +/-, ca m-am tot gandit azi la niste solutii si am zis ca poate nu am nevoie de back.

Ma poate ajuta cineva va rog cu niste indicii pentru rezolvarea urmatoarei probleme:

Se da un numar natural n. Sa se insereze semnele + si - in expresia 1 ? 2 ? ... ? n astfel incat rezultatul obtinut prin evaluarea expresiei sa fie 0. Exemple: n=3 -> 1+2-3=0, n=4 -> 1-2-3+4=0, n->9 - imposibil. Indicatie: este nevoie de gasirea conditiei de existenta a solutiei si de o aranjare a semnelor (oricare, solutia nu este unica) care sa satisfaca enuntul.

Multumesc anticipat.

shi eu tot numai 60 de pct iau dar imi da incorect sau fisier de iesire lipsa la testele 3 si 4 shi vreau sa spun ca am incercat o multime de metode si variante sa vad unde am greshit shi tot nu inteleg, numere mari nu am probleme, i-am dat teste cu 128 de linii a cate 32 de biti fiecare, si vreau sa spun ca am urmarit cu watch tot testu shi merge perfect, ce cazuri ciudate ati gasit de nu imi merge mie?

Eu citesc numaru il transform in baza 10 shi apoi verific dak e par shi e mai mare decat cel mai mare nr par gasit anterior. Ce e greshit in acest rationament?

Mi-am vazut sursa din nou si mi-am amintit ca si eu luam tot 60 de puncte din cauza ca faceam citirea intr-un int. Apoi am luat un vector de caractere si citeam, dupa care transformam in int. Incearca asa si vezi daca iti merge.

Nu imi ia decat 60 de puncte restul imi dat TLE. Eu am incercat si pe date foarte mari si-mi merge instantaneu, Cam cate linii au testele 4,5 de nu vrea sa-mi intre in timp?

Daca e sa iti mearga iti merge si pe teste foarte mari. Vezi poate nu ai facut corect transformarea sau ai busit-o si nu intra in timp pt numere mari, si ai grija si la ce tipuri de variabile folosesti.

numarul trebuie sa fie prim in baza 2 sau in baza 10, sau in ambele baza??

[Later edit] adik 11 si 101 trebuie sa fie prime sau 3 si 5 cum e in exemplu

Numerele in baza 10 trebuie sa fie prime, adica 3 si 5. E destul de clar asta in enunt.

Va sugerez sa va uitati peste evaluatorul de la problema pentru ca nu functioneaza. Am trimit o sursa care nu face decat sa citeasca din fisier un numar si sa inchida fisierul si ia TLE.

Aici te contrazic. Atata timp cat sunt foarte multi care au luat 100 de puncte nu poti spune ca evaluatorul merge prost. Si poti sa trimiti o sursa in care sa citesti dintr-un fisier si sa inchizi fisierul si sa iti dea TLE. De multe ori se intampla altceva, iei tipul prea mic si iti da WA in loc de TLE si te intrebi ce ai gresit, dar nu e nimic gresit nu intra in timp. Si cu ciurul lui Eratostene intra lejer intr-o secunda chiar si mai putin, dar depinde ce calculati dupa ciur. Timpul ala de 1.03 sau cat era e aproximativ, s-ar putea sa fie mai mare sau mai mic.

E corect pentru 20:

Cod:

18
3 1
4 4
5 2
6 5
7 3
8 6
9 4
10 7
11 5
12 8
13 6
14 9
15 7
16 10
17 8
18 11
19 9
20 12

si pentru 10?

Cod:

8
3 1
4 4
5 2
6 5
7 3
8 6
9 4
10 7

Si pentru n>4 nr de regine va fi n-2? Ca nu punem pe linia 1 si 2.

In momentul cand afli in djikstra nodul alb (dupa explicatia din Cormen) care are distanta pana la 1 minima, atunci faci numararea: aduni toate numerele de forma P

• , unde x e un nod a. i. sa existe muchia x - NOD_CURENT_OPTIM, si d
• + COST_MUCHIE_CURENTA = d[NOD_CURENT_OPTIM]... asa mi se pare cel mai logic si merge usor fara sa iti bati capul pe greseli ( nu faci numararea in timpul relaxarii muchiilor care pornesc din NOD_CURENT_OPTIM, o faci inainte... )[/quote]
  
  Cum o fac inainte. Ca trebuie sa calculez mai intai costul minim pentru nodul respectiv si apoi adun toate drumurile de la nodul anterior x daca is egale si daca nu initializez cu drumurile pt nodul respectiv.
  ceva de forma:

Cod:

for(j=2;j<=n;j++)
  if(s[j]==0)
  if(abs(d[j]-(d[poz]+a[poz][j]))>eps&&a[poz][j]!=0&&j!=poz)
  {
   p[j]=p[poz];
   d[j]=d[poz]+a[poz][j];
  }else
  if(abs(d[j]-(d[poz]+a[poz][j]))<=eps&&a[poz][j]!=0&&j!=poz)
    p[j]+=p[poz];

unde poz este nodul 1-poz-poz-j.

Multumesc tuturor pentru ajutor!Acu merge si le egaleaza.
Acu iau 10 puncte am sa vad de ce.
Cat da pentru testul asta?

Cod:

50 69 
22 33 1347 
11 43 1710 
5 21 354 
1 11 559 
27 45 1157 
9 29 66 
38 15 1480 
1 23 774 
49 5 1836 
37 36 1179 
39 30 397 
12 49 548 
28 20 815 
10 21 83 
7 48 719 
17 11 1019 
47 27 1803 
32 16 170 
42 6 901 
45 5 205 
47 29 691 
2 25 1317 
39 7 159 
20 9 558 
8 42 1194 
40 13 854 
46 16 1022 
18 48 793 
48 6 1428 
18 28 33 
18 11 1190 
27 36 98 
2 8 1241 
47 5 158 
34 41 193 
21 13 588 
29 12 1195 
44 34 1642 
14 34 1813 
28 17 1659 
21 46 681 
34 39 1554 
7 49 1336 
21 40 396 
34 48 1621 
22 39 1683 
5 6 866 
24 43 3 
37 34 1698 
25 35 955 
43 12 99 
28 45 1493 
2 1 193 
7 48 611 
48 45 567 
3 49 759 
14 42 958 
17 20 224 
42 40 871 
4 9 565 
35 17 86 
43 40 984 
40 10 1553 
48 23 503 
48 38 1276 
9 35 498 
13 36 1897 
31 44 1072 
47 1 1051

Mie imi da:
1 3 1 1 2 1 1 1 1 1 2 1 2 1 1 1 1 0 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 2 1 1 3 1 2 1 1 1 1 1 1 3 0

Imi spune si mie cineva daca e corect cum calculez nr de drumuri de cost minim?
Eu calculez cu djickstra drumul minim de la 1 la un nod iar daca il gasesc initializez nr de drumuri minime pt. drumul respectiv cu nr. de drumuri de cost minim de la nodul anterior de la care am cautat costul minim.
Daca e egal adun numarul de drumuri prin nodul prin care e egal.
Si iau 5 puncte fara logaritm iar cu 0.
Ma ajuta si pe mine cineva.
Va rog.Multumesc!
Sau daca nu sa imi dea cineva un test mai mare si raspunsul corect sa verific.(nu unul oficial, ca oricum nu se dau )
Am reusit sa iau 15 puncte dar nu stiu cum sa fac aproximarea aia cu 10e-10 sau -8.Ce intoarce aia si cum o folosesc?

:cry: Am si eu niste intrebari.
Stau de doua zile la problema asta si am luat numa 30 de puncte.
Eu iau fiecare joc si simulez toate posibilaitatile de a juca si in functie de cine castiga am doua variabile pt fiecare jucator pe care le cresc. Daca nr de castiguri pt Paftenie e mai mare sau egal cu cel al secundului ii dau banii.
Am luat cateva teste pe care am calculat si imi da, dar evaluatorul imi da WA.
Tin cont si de faptul ca un unu poate trece si peste altii.
Imi mai da si mie cineva vreo indicatie sau vreo doua teste mai mari si reziltatu sa vad daca imi da corect. Nu teste oficiale.
Daca se poate si un test oficial mia-r fi de folos sa vad ce am gresit(testul 4 sau 5).
Multumes anticipat!  
Si ar mai fi un lucru: ce inseamna memoizare?

A si eu o nelamurire.
In enunt coordonatele sunt de forma x y.
Oricum as numara imi da 7 6 si 11 13 nu 5 6 si 12 10. Ma lamureste si pe mine cineva.
M-am lamurit singur. Neatent.
El porneste din (0,0) si de aia imi da cu unu mai mare. Mersi oricum.

Imi spune si mie cineva ce am gresit. Algoritmul meu mi se pare corect chiar daca e O(N^3). Calculez drumul minim intre toate nodurile grafului cu roy-floyd, iar apoi drumul de cost minim pornind din nodul 1 este :

Cod:

for(i=1;i<n;i++)
s+=a[i][i+1];  //drumul de la nodul 1 la 2; de la 2 la 3 etc. n-1...n
s+=a[n][1]   //drumul de la nodul n la nodul 1
Pentru testul asta de aici (4) imi da un drum mai mic 323963.

Imi explica si mie cineva va rog ce gresesc?PLS ](*,) 
Multumes anticipat! [-o< 

Imi explica si mie cineva va rog ce inseamna decrementare?
Decrementarea a doua numere?
Multumesc! :cry:

Va rog ajutati-ma si pe mine.
Fac citirea caracter cu caracter in c++ si nu imi citeste spatiile(citesc: f>>ch,unde ch este un caracter).De ce?
Fac cu strtok si nu iau numai 60 de puncte. Imi zice si mie cineva ce gresesc?
Trebuie folosita cumva adunarea pe numere mari?
Si impartirea?
 

Exista cumva declarare de tip char dar mai mare decat aceasta?
Ca orice fac iau 50 de pc si in rest Fisier iesire lipsa sau raspuns gresit.
Si la astfel de lucruri e clar ca iau cam mici datele.
Timp 0.1-da numai 50pct.
Eu pun toate cuvintele intr-0 matrice, le sortez iar dupa aceea afisez doar odata fiecare cuvant.
De ce nu merge nuj.
Ma poate ajuta cineva?
 
Gata rezolvasi si luasi in sfarsit 100. Eu luam si transformam literele mari in mici iar la sfarsit cand afisam din mici in mari cele care au fost transformate la inceput. Dar am facut cu un siplu strcmp() si inca o conditie si merge.

Pentru 100 imi da 0.
Asta e fisieru meu de iesire avand in cel de intrare 120 de numere pornind de la 1......pana la 120
[...] - era prea explicit
Nu stiam ca e bun. Da greseam cand puneam limitele si voiam sa il streg si eu de aici.
Deci cifra.out este:
1
5
2
8
3
.
.
.restul  va las acuma sa il descoperiti.

Daca se cere cel mai scurt subsir crescator maximal. In exemplu de ce nu e subsirul format din pozitiile 1 6 adica (1,4). Ce rost are atunci cel mai scurt subsir crescator maximal?

Este  versiunea Borland C++ 5.02 dar am uitat sa scriu acest lucru.
Am scris din nou __int64 x si merge, dar acum stiu de ce nu merge long long.Acesta nu merge decat in linux.Am sa scriu sursa cu long si am sa trimit cu long long. Multumesc oricum pentru informatii.

De ce cand scriu long long si ce vreau sa declar in c++5.02 imi da ceva de tipul too many types in declaration. De ce nu merge?
Si se poate declara ceva de genul int64 n,i,...,a[100] in c++5.02?
sau trebuie sa declar la fiecare variabila in parete x=(long long)100000000000 sau x=(__int64)100000000000000000?

Am observat ca se repeta din 100 in 100 si am luat in calcul ultimele doua cifre. Am facut inmultirea pe numerele mari si apoi afisam rezultatul.Da iau 0 puncte. De ce?
Am scris in fisier 120 de nr si am calculat pentru 30 matematic, cu calculatorul si mi-au dat ca si in fisierul de iesire da tot zero puncte iau.
Oricum la adunare si inmultire conteaza numai ultima cifra.
Imi poate spune si mie cineva va rog ce am gresit in sursa urmatoare?

Cod:

#include <fstream.h>
ifstream f("cifra.in");
ofstream g("cifra.out");
int u=0,i,j,n,p;
int put(int k)
{
 int h,ul=1;
 for(h=1;h<=k;h++)
 {
  ul=ul*k;
  ul=ul%10;
 }
 return ul;
}
int main()
{
 f>>n;
 for(i=1;i<=n;i++)
 {
  f>>p;
  p=p%100;
  u=0;
  for(j=1;j<=p;j++)
  {
   u+=put(j);
   u=u%10;
  }
  g<<u<<"\n";
 }
 return 0;
}

Am tot incercat si incercat zile in sir da nu imi iese nimic.  

Inmultirea pe numerele mari e buna, iar limitele sunt cele din datele problemei. Am facut programul fara ciurul lui eratostene si am luat 80pct pe cand cu ciurul numai 70. De ce nuj.Am sa mai verific o data inmultirea pe numerele mari ca sa fiu sigur ca e corecta.

Nu mai conteaza. Pana la urma am luat 100 .
Greseala nu era implementarea pe numere mari ci tipul folosit la declararea variabilelor. Eu folosit unsigned long int si cred ca a intializat vectorul folosit la inmultirea pe numere mari cu alte valori si de aia WA la ultimele 3 teste. Acu folosit long long si merge => 100 puncte.
Mersi oricum de ajutor.