Stiu ca a trecut timpul de raspundere la probleme, dar pentru suma maxima (sau fiecare suma intermediara) domeniul de valori este tot 10^9 in modul?
Si

Ce legatura are Miruna cu problema ?

Sursă în Free Pascal cu punctaj maxim aici.

  In sfarsit am gasit care era problema pentru care nu obtineam punctaj maxim aici. Lucrez in Free Pascal si nu am gasit o sursa de 100 de puncte. Am observat insa ca algoritmul lucreaza [putin] mai repede daca functiile care le creez eu au si parametrii sau variabile locale, adica daca nu utilizeaza variabilele globale.
  Pentru a ma lamuri am folosit:

Cod:

uses sysutils;
const n=2000;
type vector=array[0..n]of longint;
const pasi=100000000;
var v:vector;
    i,m:longint;
    t1,t2:ttimestamp;

procedure abc1;
begin
m:=((1+i)div 2)mod n;
v[m]:=i;
end;

procedure abc2(a,b:longint);
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

procedure abc3(a,b:longint);
var m:longint;
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

procedure abc4(var v:vector;a,b:longint);
var m:longint;
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

procedure abc5(v:vector;a,b:longint);
var m:longint;
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

begin

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc1;
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc2(1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc3(1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc4(v,1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi div 100 do abc5(v,1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);
end.

  Adica am creeat un program cu 5 proceduri care fac de fapt acelasi lucru (in afara de procedura a 5-a). Prima procedura nu foloseste insa nici un parametru, numai variabilele globale, iar incepand cu a 2-a procedura am mai adaugat parametri si variabile locale. Pentru fiecare procedura am cronometrat timpul in care se executa aceasta de pasi ori. Astfel se observa mici diferente intre timpi.
  Unul dintre rezultatele care le-am obtinut acasa este:

Cod:

3813
3687
3500
3469
6484

  Daca procedurile au mai multi parametri sau au si variabile locale, atunci acestea se executa mai repede. Nu stiu daca este valabil pentru toate exemplele, dar se pare ca sursa aceasta pentru cautare binara se incadreaza in timp [la limita]. Se poate observa ca ultima procedura se executa totusi intr-un timp mult mult mai mare decat celelalte, acest lucru se datoreaza faptului ca vectorul v nu a fost transmis ca parametru de referinta.

  Eu ma refer la situatia cand sunt in timpul unui concurs si nu gasesc un algoritm eficient pentru rezolvarea unei probleme. In acest caz voi incerca sa gasesc solutii pentru problema pana cand timpul maxim de executie admis se apropie de sfarsit, moment in care returnez cea mai buna solutie care am gasit-o pana atunci. Pentru acest caz, in Turbo Pascal utilizam:

Cod:

const maxt=0.95;
var t2:longint absolute $0000:$046c;
     t1:longint;
begin
t1:=t2;
while (t2-t1)/18.2<maxt do
  begin
  {caut solutie}
  end;
{afisez solutia cea mai buna gasita}
end.
{solutia este furnizata in maxim 0.95 secunde (timpul maxim admis)}

   Problema in Free Pascal este ca nu pot declara variabila t2 pentru ca primesc eroare la compilare. Si atunci ar trebui sa folosesc o functie sau o procedura dintr-o unitate. Folosind gettime din unitatea DOS mi se pare mai putin eficient deoarece trebuie efectuate destule calcule pentru a afla timpul trecut intre doua momente de timp. Adica in Turbo Pascal aflam numarul de tacti care daca ii impart la 18.2 obtin numarul de secunde trecute (aproximativ), dar cu procedura gettime trebuie efectuate mai multe calcule. Sau daca utilizez SysUtils :

Cod:

uses sysutils;
const maxt=990;
var start,stop:TTimeStamp;
begin
start:=DateTimeToTimeStamp(now);
repeat
// continuare cautare solutie
stop:=DateTimeToTimeStamp(now);
until stop.time-start.time>maxt;
// afisare solutia cea mai buna
end.
{solutia este furnizata in maxim 990 milisecunde (timpul maxim admis)}

pot sa fac aceasta verificare, dar nu stiu cat de rapid lucreaza functia DateTimeToTimeStamp() si, ce e cel mai important, nu stiu daca la concursuri avem voie sa utilizam astfel de unit-uri.
   Prin urmare, as vrea sa stiu care este cea mai buna metoda sa rezolv in Free Pascal o astfel de problema in timpul unui concurs!

Am incercat in freepascal sa cronometrez timpul de executie, dar vad ca nu merge, imi da eroarea "absoulute can only be associated with a var or const". m-am uitat si in cartea lui Catalin Francu.In Tp 7 imi merge.Stiti cumva cum sa-l fac sa mearga si in fp...
Eu am facut download la Fp de pe net
((V 0.9.2)
compiler(V1.0.10)
debugger GDB(V 5.2.1))   .
 poate nu ii calumea asta pe care l-am luat...Are tot felul de bug-uri la debuging, nu-mi afiseaza intotdeauna calcumea vectorii...Nu-mi compileaza totdeauna codul modificat etc...
     Are cumva cineva un link de unde sa fac download si sa fie si calcumea.Nu de alta dar n-am chef sa fac download si sa aiba si ala probleme...

   Stiu ca nu s-a scris de mult aici, insa stie cineva sa-mi spuna cum pot sa cronometerez timpul in Free Pascal!? Am cautat si nu am gasit cum pot declara o variabila la locatia $0:$46c.    De fapt nu stiu daca se poate fara sa utilizez anumite functii/proceduri dintr-un anumit unit ...
   In Free Pascal este destul de greu sa lucrezi intr-adevar pentru ca are multe erori .

M-am uitat peste unele surse si am observat ca se declara vectorul cu muchii de 250002 elemente, insa maximul de muchii este 250000. Este necesar acest lucru sau la ce ajuta? Eu am rezolvat problema folosind un vector cu 250000 de pozitii.

Am inteles. Mersi pentru raspunsuri!

Cred ca "operator" e cuvant rezervat, mai nou, in pascal. Incearca sa-i zici functiei "is_operator" sau ceva de genul.

Da! Mersi pentru ajutor  . Abia acum am  downloadat Free Pascalul si am observat; pana acum aveam un alt Pascal  . Acum mai ramane sa fac un program de 100 de pcte, am primit numai 90 deoarece am rezolvat problema fara sa ma uit peste rezolvarile date.

Cine imi poate spune, va rog, de ce nu imi compileaza corect sursa #294972    ? Acasa merge... si inca bine (cred).
http://infoarena.ro/job_detail/294972

prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim

Daca te referi la sursa asta cred ca voiai sa scrii aici aici.
In ceea ce priveste diferenta dintre timpii de executie de acasa si cei de pe infoarena, trebuie sa stii ca evaluatorul infoarena ruleaza pe Linux unde timpii de evaluare sunt considerabil mai mici si in plus poate are o configuratie diferita de cea a PC-ului tau.

mersi pt raspuns  si scuze de greseala, dar cand am dat click pe "Lasa un comentariu" am ajuns la pagina asta de forum

prima mea pb rezolvata... am primit 100 pcte dar am creat acasa un fisier cu 100000 de numere si programul a terminat executia in 0.6 secunde pt datele din acest fisier (am cronometrat). deci depaseste timpul de executie din pb si totusi... am primit punctaj maxim