Imprimă pagina - 443 Jetoane

Titlul: 443 Jetoane
Scris de: Filip Cristian Buruiana din Iunie 01, 2007, 15:35:39

Aici puteţi discuta despre problema Jetoane (http://infoarena.ro/problema/jetoane).

Titlul: Răspuns: 443 Jetoane
Scris de: Florian Marcu din Iunie 01, 2007, 16:58:33

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... :-'

Titlul: Răspuns: 443 Jetoane
Scris de: Tabara Mihai din Iunie 01, 2007, 17:39:48

Citat din mesajul lui: Marcu Florian din Iunie 01, 2007, 16:58:33

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

Titlul: Răspuns: 443 Jetoane
Scris de: Florian Marcu din Iunie 01, 2007, 18:37:56

Asta voiam sa stiu. Multumesc! :thumbup:

Titlul: Răspuns: 443 Jetoane
Scris de: Anonim din Martie 31, 2008, 18:20:44

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 \:D/

Titlul: Răspuns: 443 Jetoane
Scris de: Bondane Cosmin din Martie 31, 2008, 19:26:56

Citat din mesajul lui: Popescu Marius din Martie 31, 2008, 18:20:44

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 \:D/

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

Titlul: Răspuns: 443 Jetoane
Scris de: Anonim din Martie 31, 2008, 21:03:48

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

Titlul: Răspuns: 443 Jetoane
Scris de: Andrei Grigorean din Martie 31, 2008, 21:18:24

No offence, nu cred ca ne pasa :).

Titlul: Răspuns: 443 Jetoane
Scris de: Tabara Mihai din Martie 31, 2008, 23:18:59

Citat din mesajul lui: Popescu Marius din Martie 31, 2008, 21:03:48

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

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 (http://infoarena.ro/forum/index.php?topic=1011.0).

Titlul: Răspuns: 443 Jetoane
Scris de: Vlad Schnakovszki din Ianuarie 19, 2009, 23:19:57

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;    
    }

Titlul: Răspuns: 443 Jetoane
Scris de: gaboru corupt din Ianuarie 19, 2009, 23:37:46

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

Titlul: Răspuns: 443 Jetoane
Scris de: Vlad Schnakovszki din Ianuarie 27, 2009, 09:42:30

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

Titlul: Răspuns: 443 Jetoane
Scris de: gaboru corupt din Ianuarie 27, 2009, 12:29:41

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

Titlul: Răspuns: 443 Jetoane
Scris de: Emanuel Cinca din Ianuarie 27, 2009, 17:13:45

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 :rotfl:

Titlul: Răspuns: 443 Jetoane
Scris de: Alexandru-Iancu Caragicu din August 24, 2010, 15:28:48

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.

Titlul: Răspuns: 443 Jetoane
Scris de: Vali Deaconu din Februarie 07, 2015, 17:27:24

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Filip Cristian Buruiana din Iunie 01, 2007, 15:35:39