Ar cam trebuie refacute testele pntru ca toate sunt cu elementele in ordine crescatoare(celalat caz nu ar fi luat in considerare).

Se mai preciza in enunt ca P,D,C<=5.000

"Mult succes in runda a patra care are loc duminica, 21 februarie de la ora 9:00.". Cred ca e martie nu februarie.

Uite rezolvarea mea:
Am observat ca daca b>=2*a, fiecare numar de la 1 la b sigur e divizor al intervalului. Asta e usor de demonstrat cu principiul cutiei.
Daca b<=2*a trebuie sa cautam care numere mai mici ca a nu divid nici un numar din [a,b]
Observam ca aceste numere sunt cele astfel incat [(a-1)/x]=[b/x], pentru ca nu va mai aparea nici un multiplu de-al sau in intervalul [a,b]
Asa ca putem face un for de la 1 la sqrt(b) sa eleminam numerele de la 1 la b care respecta aceasta chestie si observam cateva cazuri:

I Daca [(a-1)/i]=[b/i] eliminam 1 de la rezultat(adica pe i)
II Fie
x=[(a-1)/i]
y=[b/i]
u=[(a-1)/(i+1)]
v=[b/(i+1)]

Toate numerele mai mari ca v dau cel mult i in raportul [b/k] (k>=v)
Toate numerele mai mici sau egal cu x dau cel putin i in raportul [(a-1)/i] (k<=x)
Deci toate numerele k apartinand lui (v;x] au proprietatea [(a-1)/k]=[b/k]

Deci nu trebuie decat sa scadem din rezultatul curent cate numere sunt in intervalul (v;x] (atentie v deschis)
Si inca o precizare. Deoarece vom merge la sqrt(b) trebuie ca la orice moment sa nu scadem vreun interval care sa contine vreuna din elementele <=sqrt(b). Deci v=max(sqrt(b),[b/(i+1)]
Si inca ceva:vezi sa nu scazi elementele unui interval daca el nu are sens(adica v>=x)

Presupun ca asta e si rezolvarea oficiala.

P.S:Problema asta e foarta usoara, insa la intensitate avand in vedere ca maximul a fost 30 trebuie sa recunosc ca a fost cam grea

L.E: Ambele cazuri trebuie luate in considerare(in paralel). Deci daca primul caz se adevereste asta nu inseamna ca nu mai trebuie sa consideram si al doilea sau invers.

Mi-a aparut eraore in evaluator: "Evaluatorul nu a returnat un numar la stdout pe testul 1 (se ignora spatii, newline, etc)"

M-am uitat mai atent peste ele si singura diferenta majora e faptul ca in cea .cpp pentru fiecare nemuritor verifica daca are un vecin sa sara peste el, iar in cea .c pentru fiecare nemuritor se cauta un vecin peste care sa sara.
 Nici eu nu inteleg care ar fi diferenta dintre cele doua, mai ales ca in antetul primeia scrie "Backtracking neoptimizat:17s" iar in antetul celeilalte scrie "Bactraking optimizat:0.17s".

Din cate imi amintesc sursa cpp era cea scrisa de Marinel Serban si in loc sa treaca prin lista nemuritorilor(care e destul de mica) trecea prin matrice(care e de vreo 30 de ori mai mare pe cel mai mare test).
A doua sursa era scrisa de Emanuela Cerchez in C si trecea prin lista nemuritorilor.
Nu sunt sigur dar cred ca acesta ar cam fi motivul.

Ms pentru raspuns. Am luat 100, se pare ca gresisem recurenta. 

Mai complicat: ai putea inlocui map-ul cu un hash(daca nu stii ce inseamna iti sugerez sa rezolvi problema hashuri de la arhiva educationala) sau mult mai simplu sa te folosesti de faptul ca diferenta dintre cel mai mare si cel mai mic de pe un rand este de 250.000. Daca stii count sort il poti modifica un pic(scazand din toate numerele minimul) si astfel ai complexitate O(n*m).
Map-ul are complexitate logaritmica asa ca e de preferat sa nu o folosesti in situatii in care poti folosi altceva mai rapid.

Mie pentru 4 imi da 58 si pentru 5 imi da 229
Imi poate spune cineva daca sunt corecte si acestea si urmatoarele:

Cod:

16->954437182
235-> 67746279303732470299079800993775310454613674971028019766908788186314490859803941408868095282875861796837441649610812260296869722067770248839

Multumesc anticipat!

Foloseste tag-ul [ code ] [/ code ] cand postezi teste.

@Vlad Chiar daca (1<<31) iese din int el asa va arata in baza 2 100....00(31 zerouri) care este perceput ca -2³¹. Imediat ce scazi 1, iar depeseste limita int(de data asta cea inferioara) si ia valoare pe care o vreau.A stfel ca la (1<<31) adunam -1
(1<<31):10000000000000000000000000000000
(-1):      11111111111111111111111111111111
rezultat: 01111111111111111111111111111111

Observam ca primul bit(cel de semn) a fost adunat ca si ceilalti biti si s-a redus. Vreau sa marchez faptul ca indiferent cat de mari sunt numerele cu care faci operatii pe int, ele se vor executa ca si celelalte doar ca nu se vor tine cont de ceilalti biti.
Aceste apelari nu sunt gresite(eu sincer le folosesc mereu cand nu trebuie sa adun maximul undeva).
Ex: MAXT=(1<<31)-1;
     MINT=MAXT+1;(ne intoarcem inapoi in -2³¹)
La MINT am atribuit valoarea asa fiindca nu imi da mereu cum trebuie daca pun MINT=(1<<31);

Cand faci update in acel if verifici lung_max[mat [ i][ 0]], insa mat[ i][ 0] este caracter si chiar tu ai zis ca in lung_max tu tii numaarul maxim de cuvinte ce pot ramane incepand cu cuvantul i(imi pare rau pentru cacafonie). Incearca sa pui

Cod:

if(lung_max[i]>=lung_max[a[mat[i][0]-'a'])
		   a[mat[i][0]-'a']=i;

Din cate cred vei lua 100 acum.

Dap. Asta trebuie afisat. 

Vezi ca daca cel mai lung sir de acelasi numar e fix la sfarsit programul tau nu-l gaseste, pentru ca nu merge in n+1 sa verifice cu n. Iti sugerez sa mai faci o verificare dupa forul de la 1 la n.
 Alta problema e ca trebuie sa reinitializezi t1=0 cand incepi fiecare din cei m pasi altfel ai putea compara cu ultimul element de pe linia anterioara ceea ce nu e corect.
A treia problema e faptul ca cei 250.000 de pomi ai tai sunt intr-un char. Tu acolo stochezi inaltimea lor, care depaseste cu mult 127 care e limita la char. Iti sugerez sa treci in int.
Sper sa te ajute.

Intocmai, nu forul a facut sa iei KBS si faptul ca ai initializat minimul gresit.
Initializeaza-l cu 2.000.000.000 daca ti se pare mai usor si vei vedea ca vei scapa de KBS.
Si mai trebuie sa faci aux de lungime 250.001(de la 0 la 250.000) si x de 700.001(de la 0 la 700.000).
Am incercat eu cu sursa ta si mi-a dat 54 de puncte
http://infoarena.ro/job_detail/414802

Am inlocuit

Cod:

min1=250000;

cu

Cod:

min1=(1<<31)-1;

si acum nu am primit decat cateva TLE si un Wrong answer. Vezi ca in functia maj ai un for in altul, complexitate O(n^2). Incearca sa reduci chestia asta si vei lua 100.
(1<<x) este egal cu 2^x, si fiindca 2³¹ iese din int, mai scadem 1.
Sper sa te ajute!:D

L.E: Am scos si cate un zero de la vectorii tai, ca nu intra in memorie.

Vezi k tu initializezi minimul cu 250.000, numerele pot fi toate mai mari decat 250.000 , de exemplu din intervalul 70.000.000 si 95.000.000.
Astfel tu din toate numerle scazi 250.000(min1 la tine ramane nemodificat) si vei accesa la un moment dat aux[70.000.000] care nu exista.
 Iti recomand sa initializezi minimul daca e int cu

Cod:

mint=(1<<31)-1;

sau daca e long long cu

Cod:

mint=(1LL<<63)-1;

L.E: @Dornescu Vlad, eu am pus totul int, si citesc cu streamuri si am sub 0.5 pe toate testele.

Nu se poate vedea problema " Nu ai permisiuni suficiente pentru a executa aceasta actiune! Te redirectez ..."

Si presupun ca tu in rezolvare faci C[n-2][no-1]*C[n-2][nv-1]*2?
Asta tot la formula din solutia oficiala duce, chiar daca a ta e mai corect exprimata.

In primul rand scuze ca am calculat gresit dupa formula ta.
In al doilea rand uite pusa in aplicare formula ta pentru n=k=5000
1-Solutia Oficiala->12882
2-Formula Ta->53

Cand s-au scris solutiile sunt sigur ca nu s-au tinut cont de schimbarile care aveau loc pe ultima/prima linie sau coloana. De aceea tie iti da cu 1 mai mult, insa trebuie sa te aprob, este o greseala de exprimare in solutia oficiala. Presupun ca o sa se modifice foarte curand.

E corect cum scrie in solutie, exact formula asta o am in rezolvarea mea.
Te-ai gandit ca unul din schimbari se va afla ori pe ultima coloana ori pe ultima linie?
Poate nu ai luat acest caz in vedere.

P.S: Pentru cazul 4 2 din exemplu formula ta da C(2,2)*C(2,2)*2=2 cand defapt ar trebui sa fie 4

Am o rezolvare diferita de cea oficiala si nu sunt sigur daca e corecta 100%, desi am luat 100 de puncte pe ea.
Fac ceva de genul urmator:
1)Adaug tote muchiile de cost 1 in graf si imi formez un alt graf cu ele, daca intre 2 noduri exista deja un drum marchez o dublare(adica nu as avea nevoie de o astfel de muchie in final).
2)Adaug muchiile de cost 0 si in acest graf si la arborele solutie daca satisfac una din urmatoarele conditii.

I)Daca uneste doua noduri intre care nu exista drum(in graful nou format)
II)Daca uneste doua noduri intre care exista un drum format de muchii de cost 1 si nu exista drum format din muchii de cost 0 si numarul de dublari este mai mic decat (numarul_de_muchii_de_cost_1-K). In acest caz incrementez si numarul de dublari

3)Mai trec odata odata prin muchiile de cost 1 si le adaug in arborele solutie doar daca nu exista un drum intre cele 2 noduri in arborele solutie.

Daca ma puteti lamuri va rog sa-mi raspundeti.
Multumesc anticipat!

Imi poate spune cineva daca se mai tine anul acesta, si mai exact cand anume.
Multumesc!

Foarte frumoase probleme, mai ales Jap2, abia astept solutia. Am invatat ceva nou si foarte folositor din concursul acesta.
Tineti-o tot asa

Cod:

13 1000000 2
103 345
154 656
321 767
21 8643
543 8777
242 6955
532 7653
23 657
13 7564
67 336
1000 5436
31 9427
3 213
R:8371403227327
RM:436037730864377

13 100000 2
103 345
154 656
321 767
21 8643
543 8777
242 6955
532 7653
23 657
13 7564
67 336
1000 5436
31 9427
3 213
R:43603803564377
RM:43603803564377

5 2391923 234
432 63543
3 543
1 567
4 6542
5 4325
R:4903753644105
RM:9806483859946865

5 236546 43
432 6354
3 543
1 567
4 6542
5 4325
R:24244324377180
RM:24244324377180

10 57 432
3 90
34 654
34 652
65 14
54 14
65 13
54 76
327 453
14 763
23 765
R:10
RM:127470811

10 7657 5476
3 90
34 654
34 652
65 14
54 14
65 13
54 76
327 453
14 763
23 765
R:17142691237
RM:17142691237

RM=rezultatul meu R=rezultatul tau
Sper sa nu fi gresit cu ceva si sa te ajute