443 Jetoane

[•filipb]

Aici puteţi discuta despre problema Jetoane.

[•Florian]

Mh...am trimis 2 surse in care am abordat idei diferite...cu ambele iau 90...nu cer decat sa ma lamuriti daca testul 2 este corect sau daca greseala este a mea, ori daca a luat cineva 100. Apropo, cred ca ar trebui micsorata limita de timp la 0.1 secunde...

[•Tabara]

Mh...am trimis 2 surse in care am abordat idei diferite...cu ambele iau 90...nu cer decat sa ma lamuriti daca testul 2 este corect sau daca greseala este a mea, ori daca a luat cineva 100. Apropo, cred ca ar trebui micsorata limita de timp la 0.1 secunde...

Ai o greseala undeva in program! 
Am luat 100, deci nu cred ca e gresit testul 2.
 

[•Florian]

Asta voiam sa stiu. Multumesc! 

[•jupanu92]

Ce pr usoar mam mirat ca am luat din prima 100 de p dar dupaia cand am vazut ca e de cls a 7 a mam lamurit de ce am luat atat 

[•cos_min]

Ce pr usoar mam mirat ca am luat din prima 100 de p dar dupaia cand am vazut ca e de cls a 7 a mam lamurit de ce am luat atat 

Forumul este special pentru intrebari, nu pentru impresii personale asupra problemelor...(ce ar fi daca toti ne-am exprima impresiile despre fiecare problema?)

[•jupanu92]

Nu m-as supara daca si-ar impartasii fiecare impresia despre o problema ... eram si eu bucuros ca mia iesit din prima 100   

[•wefgef]

No offence, nu cred ca ne pasa .

[•Tabara]

Nu m-as supara daca si-ar impartasii fiecare impresia despre o problema ... eram si eu bucuros ca mia iesit din prima 100   

Daca mai faci vreo 4-5 care crezi ca iti plac in mod deosebit iti poti exprima parerea asupra lor intr-un singur post aici.

[•shnako]

Are careva vreo idee cum pot face programul asta sa mearga mai rapid? Ca iau TLE pe 3 teste. Mersi.
_{P.S.: Voi scoate sursa cand voi primi un raspuns bun. Daca am incalcat cu ceva regulamentul rog adminii sa o scoata.}

Cod:

#include <fstream.h>  
#include <time.h>    
ifstream f("jetoane.in");  
ofstream g("jetoane.out");    
unsigned int a[28001], b[28001], i, j, ii, jj, aux, n, min=0, max, s1, s2, m;    
int poz (int ls, int ld)    
    {  
    i=ls;    
    j=ld;    
    ii=0;    
    jj=-1;  
    while (i<j)    
        {    
        if (a[i]>a[j])    
            {  
            aux=a[i];    
            a[i]=a[j];    
            a[j]=aux;    
            aux=-ii;  
            ii=-jj;    
            jj=aux;    
         }    
        i+=ii;  
        j+=jj;    
        }    
    return i;    
    }  
void qsort(int ls, int ld)    
    {    
    int p;    
    if (ls<ld)  
        {    
        p=poz(ls,ld);    
        qsort (ls, p-1);    
        qsort (p+1, ld);  
        }    
    }    
int pozl (int ls, int ld)    
    {  
    i=ls;    
    j=ld;    
    ii=0;    
    jj=-1;  
    while (i<j)    
        {    
        if (b[i]>b[j])    
            {  
            aux=b[i];    
            b[i]=b[j];    
            b[j]=aux;    
            aux=-ii;  
            ii=-jj;    
            jj=aux;    
         }    
        i+=ii;  
        j+=jj;    
        }    
    return i;    
    }  
void qsortl(int ls, int ld)    
    {    
    int p;    
    if (ls<ld)  
        {    
        p=pozl(ls,ld);    
        qsortl (ls, p-1);    
        qsortl (p+1, ld);    
        }    
    }    
int main(void)    
    {    
    f>>m>>n;    
    for (i=1;i<=m;i++)    
        f>>a[i];    
    for (i=1;i<=n;i++)    
        f>>b[i];    
    qsort (1,m);  
   qsortl (1,n);                                   //citiri si sortari de siruri.    
   for (i=1;i<=m;i++)  
    {    
    for (j=1;a[i]>=b[j];j++)  
        if (a[i]==b[j])    
            {  
                min=a[i];  
            break;  
            }  
      if (min)                                     //aflarea minimului  
        break;  
      }  
   for (i=m;i>0;i--)  
    {  
    for (j=n;a[i]<=b[j];j--)  
        if (a[i]==b[j])    
            {    
                max=a[i];    
            break;    
            }  
      if (max)                                      //aflarea maximului  
        break;  
      }    
    for (i=1;a[i]<min;i++)  
    s1++;    
   for (i=1;b[i]<min;i++)    
    s2++;    
   for (i=m;a[i]>max;i--)    
    s1++;    
   for (i=n;b[i]>max;i--)    
    s2++;    
   g<<min<<" "<<max<<" ";    
   if (s1==s2)  
    g<<0;    
   else    
    if (s1>s2)    
        g<<1;    
      else    
        g<<2;  
    f.close();    
   g.close();    
    return 0;    
    }  

[•gabor_oliviu1991]

ma tem ca nu poti implementa ideea ta pt 100. si eu aveam aproximativ aceasi idee ca tine. cel putin eu nu puteam sa scap de 3 TLE-uri. parerea mea sa te gandesti la alta rezolvare

[•shnako]

Merge ideea asta, dar cu MergeSort in loc de QuickSort.

[•gabor_oliviu1991]

hehe...merci, am implementat si eu cu merge sort si am scos 100. dar de ce nu ai intrat si quickul totusi?

[•c_e_manu]

simplu... pe numere sortate/aproape sortate cu quicksortul simplu ai O(n^2)... mergesort e constant O(n logn)... mey oliviu, nu ai invatat la scoala  .. ce 2 iti da profa 

[•Bit_Master]

Am si eu o intrebare?
E gresit conceptul urmator pt a lua numerele comune a doi vectori?

Cod:

- ii sortezi
- pornesti cu doi indici, cate unul pe fiecare vector incepand de la pozitia 1

- cat timp indicii nu sunt in afara vectorilor
{
   - compari valorile indicate de vectori sa vezi daca sunt comune
   - avansezi cu cel care indica o valoare mai mica
}

Iei 40 puncte asa.

[•Vali_Deaconu]

Eu am făcut-o cu frecvență în O(n) È™i am luat 100p. Nu vă mai complicaÈ›i cu MergeSort.