infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Iunie 25, 2007, 16:20:41



Titlul: 467 Orase
Scris de: Adrian Diaconu din Iunie 25, 2007, 16:20:41
Aici puteţi discuta despre problema Orase (http://infoarena.ro/problema/orase).


Titlul: Răspuns: 467 Orase
Scris de: Gabriel Bitis din Iunie 26, 2007, 14:40:01
Ce complexitate trebuie sa aiba solutia?


Titlul: Răspuns: 467 Orase
Scris de: Bondane Cosmin din Iunie 26, 2007, 15:31:14
Eu am reusit sa scot un O(n*logn), pe total, si am luat 100 pcte.


Titlul: Răspuns: 467 Orase
Scris de: Ionescu Vlad din Iunie 26, 2007, 22:44:21
in exemplu, strazile sunt:

5 6
2 2 (1)
0 3
2 7 (2)

distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile?


Titlul: Răspuns: 467 Orase
Scris de: Florian Marcu din Iunie 27, 2007, 07:38:28
Pai..dupa cum vezi in explicatie [ in desen ] strazile au fost desenate una in sus si una in jos, asta pentru a simplifica probabil intelegerea. Cred k se pot suprapune, insa calculul distantei va ramane la fel [ dist (i,j)=li+ lj <=>asta doat in cazul suprapunerii]. Sau...mai simplu:considera orice pereche i,j kare s-ar "suprapune" k fiind opuse [ k in desen] si s-a rezolvat tot.  :thumbup:


Titlul: Răspuns: 467 Orase
Scris de: Ionescu Vlad din Iunie 27, 2007, 12:21:16
pai si daca am:

2 2
2 3
2 4

cum mai consider ca sunt opuse?  :-'
probabil ca-i asa cum spui, n-am rezolvat inca problema, dar nu prea e logic...


Titlul: Răspuns: 467 Orase
Scris de: Andrei Purice din Iunie 27, 2007, 12:31:29
Din moment ce nu este precizat modul lor de asezare atunci ramane de datoria ta sa il alegi... si pentru a obtine maximul te duci cu max1 intr-o directie si cu max2 in cealalta ;) . In cazul tau rezultatul va fi 7 :)


Titlul: Răspuns: 467 Orase
Scris de: Sima Cotizo din Iunie 27, 2007, 19:32:58
Am facut un program N log N, imi ia 30 cu TLE si un WA... nu asta conteaza... ci faptul ca am facut in main
Cod:
return 50;
daca N>50000... si am 6 teste cu NonZero Exit Status... Care sunt limitele pana la urma?


Titlul: Răspuns: 467 Orase
Scris de: Bondane Cosmin din Iunie 27, 2007, 19:38:42
N <= 50000. Pentru ca eu mi-am declarat astfel sirurile pe care le-am folosit si a mers fara probleme.


Titlul: Răspuns: 467 Orase
Scris de: Sima Cotizo din Iunie 27, 2007, 19:42:09
Tocmai scriam un reply in care sa sustin ca nu e asa, dar am gresit ... :) citeam (n,m) nu (m,n)... Greseala mea, scuze!  :oops:


Titlul: Răspuns: 467 Orase
Scris de: Sebastian Crisan din Iunie 27, 2007, 21:46:39
[..]
distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile?

Probabil ca atunci cand vrei sa mergi dintr-un oras in altul trebuie sa treci si pe strada principala: dist(i, j)=L[ i]+L[j]+|D[ i]-D[j]|.


Titlul: Răspuns: 467 Orase
Scris de: Florian Marcu din Iunie 27, 2007, 21:54:46
Cum se face asta in N logN? Care e idea care sta la baza algoritmului..? k nu ma prind :oops: Am o rezolvare N^2 cu care prind numa` 40 de puncte...


Titlul: Răspuns: 467 Orase
Scris de: Florin Pogocsan din Iunie 27, 2007, 23:38:10
Pai N*logN vine de la sortare :P , dupa care liniar determini maximul . Mai mult nu zic ca deja e mare spoiler ce am zis :)


Titlul: Răspuns: 467 Orase
Scris de: Sebastian Crisan din Iunie 29, 2007, 16:42:52
Am rezolvat problema, insa nu m-am folosit nicaieri de M (lungimea strazii principale). Voi ati folosit-o undeva?


Titlul: Răspuns: 467 Orase
Scris de: Cezar Mocan din Iunie 29, 2007, 16:59:09
Pai probabil ca te ajuta daca faci sortare de aia in timp liniar ca sa nu mai trebuiasca sa afli maximu din sir... alta utilizare nu-i vad...


Titlul: Răspuns: 467 Orase
Scris de: Andrei Homorodean din Iunie 29, 2007, 20:37:59
In articol e:

Cod:
distanta care trebuie parcursa intre doua orase i < j: Li+Di+Lj-Dj

cred ca e j < i..


Titlul: Răspuns: 467 Orase
Scris de: Mircea Pasoi din Iunie 29, 2007, 21:19:13
Asa e.


Titlul: Răspuns: 467 Orase
Scris de: Bozianu Ana din Iulie 05, 2007, 13:55:10
Am rezolvat problema, insa nu m-am folosit nicaieri de M (lungimea strazii principale). Voi ati folosit-o undeva?


Eu nu. Doar ca am vazut ca solutia este <=3.000.000 deci intra pe long int. In rest in m-a "ajutat" ca pe altii sa fac citirea in ordine gresita a lui m si n  :?


Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 10:55:47
Am incercat solutia oficiala, dar iau numai 50 de puncte, restul sunt TLE-uri
ce sortare ar trebui sa folosesc?(cu insertion sort fac acum)
http://infoarena.ro/job_detail/329952
cred ca se blocheaza undeva, dif de timp e uriasa!


Titlul: Răspuns: 467 Orase
Scris de: Emanuel Cinca din Iulie 08, 2009, 11:04:15
Foloseste quicksort. Desi ar trebui sa intre si cu mergesort, ambele avand complexitatea O(nlogn).


Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 11:10:13
nu am invatat quicksort, chiar daca stiu ca e cel mai rapid  :'(
oricum, caut pe net


Titlul: Răspuns: 467 Orase
Scris de: Cezar Mocan din Iulie 08, 2009, 11:27:17
Foloseste sort-ul din STL. Incluzi libraria <algorithm> si apoi scrii sort(sir + 1, sir + N + 1);


Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 11:50:33
adica pentru vectorul a[50000] scriu sort(a+1,a+n+1)?


Titlul: Răspuns: 467 Orase
Scris de: Popescu Marius din Iulie 08, 2009, 12:11:29
  Da, unde n reprezinta numarul de elemente din vectorul a[50001] . Daca ai elemente in vector de la 1 atunci scri sort(a+1,a+n+1) , iar daca ai de la 0 scri sort(a,a+n);
  Uite aici un exemplu , sper sa te ajute :
Cod:
#include<fstream.h>
#include<algorithm>

using namespace std;

int n,a[500001];

int main()
{
    ifstream fin("sort.in");
    ofstream fout("sort.out");
    fin>>n;
    for(int i=1;i<=n;++i)
      fin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
      fout<<a[i]<<" ";
    return 0;
}



Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 12:12:24
multumesc mult!! karma plus la toti


Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 12:25:51
Cod:
#include<fstream.h>
#include<algorithm>
int main()
{long ...
ifstream q("orase.in");
ofstream w("orase.out");
q>>m>>n;
for(i=1;i<=n;i++)
  {q>>v1[i]>>v2[i];
  v1[i]=v1[i]*100000+v2[i];}
sort(v1+1,v1+n+1);
...
1.Compilatorul da eroare: sort was not declared in this scope ??????
2.elementele din v1 intra in long dupa ce *100000?


Titlul: Răspuns: 467 Orase
Scris de: Emanuel Cinca din Iulie 08, 2009, 12:49:40
Cod:
#include<algorithm>

using namspace std;    //ai uitat partea asta :)
.......
sort();
.......



Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 13:03:36
Cod:
#include<fstream.h>
#include<algorithm>
using namespace std;
int main()
{long long dn,dt,v1[50001],v2[50001],i,n,m,max=0,maxt=0;           //00
ifstream q("orase.in");
ofstream w("orase.out");
q>>m>>n;
for(i=1;i<=n;i++)
  {q>>v1[i]>>v2[i];
  v1[i]=v1[i]*100000+v2[i];}
sort(v1+1,v1+n+1);
for(i=1;i<=n;i++)
  {v2[i]=v1[i]%100000;
  v1[i]=v1[i]/100000;}
dt=v2[1]-v1[1];
for(i=2;i<=n;i++)
  {max=0;
  dn=v2[i]-v1[i];
  if(dn<dt)
   max=v2[i]+v1[i]+dt;
  else
   {max=v2[i]+v1[i]+dn;
   dt=dn;}
  if(maxt<max)
   maxt=max;}
w<<maxt;
return 0;}
sortarea chiar a ajutat! dar acum in loc de TLE este "Incorect!"
http://infoarena.ro/job_detail/330015
am ramas blocat la 50 de puncte!


Titlul: Răspuns: 467 Orase
Scris de: Emanuel Cinca din Iulie 08, 2009, 13:27:22
Vezi ca ti-am trimis PM!  :peacefingers:


Titlul: Răspuns: 467 Orase
Scris de: zloteanu adrian nichita din Iulie 08, 2009, 13:35:32
n-am primit nimic inca, dar sunt dispus sa astept  :weightlift:
LE: trebuie sa dau click pe "mesaje"(meniul de sus) si apoi "mesaje primite"? nu primesc nimic!


Titlul: Răspuns: 467 Orase
Scris de: George Popoiu din Noiembrie 21, 2009, 17:58:33
Imi da cineva un hint cum sa calculez maximul Liniar?


Titlul: Răspuns: 467 Orase
Scris de: irimias robert din Noiembrie 28, 2009, 11:40:51
probabil asta ar trebui sa te ajute, george http://infoarena.ro/problema/ssm



apropo, imi puteti va rog spune de ce metoda asta nu ia 100 de puncte:

Cod:
void program() 
{    long long max=v[1][1]+v[2][1]+v[2][0]-v[1][0];    
     int i=1, j=2;      
     for (int k=3; k<=n; k++)      
     {   int ci=i, cj=j;
         if (v[ci][1]+v[k][1]+v[k][0]-v[ci][0]>max)
         {  max=v[ci][1]+v[k][1]+v[k][0]-v[ci][0];
            j=k;
         }
         if (v[cj][1]+v[k][1]+v[k][0]-v[cj][0]>max)
         {  max=v[cj][1]+v[k][1]+v[k][0]-v[cj][0];
            i=cj;
            j=k;
         }
     }
     g << max;
}

daca nu trebuia sa pun solutia asta rog un admin sa stearga, ms


Titlul: Răspuns: 467 Orase
Scris de: George Popoiu din Noiembrie 29, 2009, 12:28:46
ceva de genu fac si eu robert, nu cred ca e corect. Cred ca e o chichita...


P.S. : Citisem articolul si rezolvasem inaite sa postez :P


Titlul: Răspuns: 467 Orase
Scris de: Paval Cristi Onisim din Decembrie 28, 2010, 14:14:09
Am rezolvat problema in O(M) fara nici o sortare :yahoo:

[editat] am modificat mesajul ca sa evitam postatul consecutiv...


Titlul: Răspuns: 467 Orase
Scris de: UAIC.VlasCatalin din August 22, 2011, 23:25:12
Am trimis numai citirea in pascal si am TLE pe 6 teste, stie cineva ce inseamna asta ca eu deja nu mai inteleg ce se intimpla  ](*,)

LE: S-a rezolvat, nu era problema in algoritm dar am incurcat m cu n la citire  #-o :aha:

 Nu posta consecutiv, ci editeaza mesajele anterioare.


Titlul: Răspuns: 467 Orase
Scris de: UAIC.VlasCatalin din August 24, 2011, 18:06:56
Sucuze pentru post consecutiv, dar nu stiu cum se reediteaza mesajele anterioare, as fi recunoscator daca mi-ati spune cum se face asta, ce sunt incepator pe aici  :)


Titlul: Răspuns: 467 Orase
Scris de: Jack ONeill din Februarie 17, 2015, 11:20:23
Puteti pune testul 3 va rog? Nu stiu de ce nu-mi ruleaza acolo...