infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Filip Cristian Buruiana din Iulie 04, 2007, 11:14:08



Titlul: 474 Teams
Scris de: Filip Cristian Buruiana din Iulie 04, 2007, 11:14:08
Aici puteţi discuta despre problema Teams (http://infoarena.ro/problema/teams).


Titlul: Răspuns: 474 Teams
Scris de: Maria Stanciu din Martie 31, 2008, 16:10:33
Am facut problema retinand in v[ i ] numarul de aparitii ale lui i in sirul de valori.
Totusi iau 2 TLE-uri desi am incercat sa fac citirea si cu streamuri si in c.

Voi cum ati reusit sa luati 100?

P.S.: ce inseamna sa parsezi citirea?


Titlul: Răspuns: 474 Teams
Scris de: Savin Tiberiu din Martie 31, 2008, 16:20:07
citesti o linie intreaga ca string ( eu folosesc fgets ptr asta) si apoi iti scoti numerele din string.
uite un cod simplu care citeste elementele unui vector:

Cod:
fgets(s,NMAX,stdin);
n=0;x=0;
for (i=0;s[i]!='\n';i++)
        if (s[i]==' ') v[++n]=x,x=0;
            else x=x*10+s[i]-'0';


Titlul: Răspuns: 474 Teams
Scris de: Andrei Misarca din Aprilie 09, 2008, 20:06:26
Si e mai rapida citirea asa? :)


Titlul: Răspuns: 474 Teams
Scris de: Andrei Grigorean din Aprilie 09, 2008, 20:21:47
Da, e mai rapida. Cu cat sunt mai multe numere pe o linie cu atat se simte mai tare diferenta intre o citire normala si parsare.


Titlul: Răspuns: 474 Teams
Scris de: Andrei Misarca din Aprilie 09, 2008, 20:39:25
Dar de ce? Scanf e mai incet decat o adunare + o inmultire? Si citirea unei e asa rapida?


Titlul: Răspuns: 474 Teams
Scris de: Bogdan-Alexandru Stoica din Aprilie 09, 2008, 21:32:07
functia scanf are mai multi parametrii care se efectueaza mai incet decat o adunare si o inmultire, plus ca ea intoarce numarul de variabile (din cele solicitate de tine) citite "cu succes". pentru mai multe detalii despre cum functioneaza scanf citete aici (http://en.wikipedia.org/wiki/Scanf).


Titlul: Răspuns: 474 Teams
Scris de: Ciocan Andrei din Aprilie 10, 2008, 16:30:06
Am o mica nelamurire. Logic, algoritmul meu e bun; si eficient. Tot nu pot sa-mi dau seama pe unde s-a strecurat vreo eroare, de iau WA pe testele 5,7,9 si 10. Timpul de executie este bun. Am explicat cum l-am gandit in sursa.
Ma poate  ajuta cineva,va rog?


Titlul: Răspuns: 474 Teams
Scris de: Pripoae Teodor Anton din Aprilie 10, 2008, 18:37:40
pentru inceput de ce nu le declari pe toate int ? int-ul pe gcc e la fel ca long-ul dar e posibil sa rezulte probleme de aici


Titlul: Răspuns: 474 Teams
Scris de: Ciocan Andrei din Aprilie 10, 2008, 19:27:38
Degeaba :sad: Tot 60... Chiar nu stiu ce ar putea fi. Un test poate ar rezolva totul.


Titlul: Răspuns: 474 Teams
Scris de: MciprianM din Septembrie 17, 2008, 17:17:24
Pt AndreiD.
Daca te mai intereseaza am gasit o greseala in sursa ta(int functia cautbinar)
 
Cod:
for (i=poz+1; p;p/=2)
if (i+p<=n && v[i+p]+v[poz]<=a) i+=p;
In primul apel din main al functiei e nevoie de v[i+p]+v[poz]<a int loc de <= si
 return i+1; (In cazul in care i+1 intra int intervalul in care cauti binar).
Adica trebuie gasita cea mai din stanga valoare v pt care v+v[poz]>=a;


Titlul: Răspuns: 474 Teams
Scris de: Mandu Dragos din Ianuarie 12, 2009, 23:09:04
am si yo o intrebare :D ....dak aplic metoda bruta dupa pt aceea care au aceeasi putere calculez doar odata?  : comb*=f[v[ i ]];altfel ++comb; ](*,)....ar intra in timp ?sau gresesc.... :sad:

[editat de moderator] Cand scrii [ i ] lasa spatii


Titlul: Răspuns: 474 Teams
Scris de: Alexandru Gherghe din Mai 10, 2009, 21:08:22
sortez vectoru si pt fiecare element folosesc cautarea binara pt a cauta cea mai mica pozitie din vector pt care se poate forma o pereche si cea mai mare pozitie. apoi daca elementul meu initial se afla in interval sau capete, la solutie adaug doar poz2-poz1, altfel adaug sol+=poz2-poz1+1; unde gresesc?

va rog frumos, ati putea posta inca un test din cele date?
eu iau 0 puncte si pe testele mele sursa merge bine....


Titlul: Răspuns: 474 Teams
Scris de: Andrici Cezar din Mai 11, 2009, 16:53:33
vezi... ai grija.. eu am facut ca tine dar vezi sa nu aiba capatat de inceput.... si ai grija ca poate nu gaseste ultima pozitie adica pana cand <=b poate orice suma da <=b ,,, daca nu faci asa detaliaza oleac sursa


Titlul: Răspuns: 474 Teams
Scris de: Alexandru Gherghe din Mai 11, 2009, 20:09:24
pai faza e ca gaseste mereu pozitia cea mai din capat... adica practic cand a gasit valoarea intr-un anumit interval restrange oricum acel interval pana cand capatul din stanga ajunge masi mare ca cel din dreapta...


Titlul: Răspuns: 474 Teams
Scris de: A Cosmina - vechi din Iunie 16, 2009, 15:08:16
Nu pricep de ce iau 0 puncte pe ea. La mine pe calculator merge perfect si am verificat pe mai multe texte.
Citat
Killed by signal 11(SIGSEGV).
asa apare peste tot. Ce bug as putea avea?  :-k 

Ruleaza in 5 secude, cam depasesc limita de timp...Ce as putea sa-i fac sa se incadreze in timp?


Titlul: Răspuns: 474 Teams
Scris de: Dragos Oprica din Iunie 16, 2009, 21:49:06
Nu pricep de ce iau 0 puncte pe ea. La mine pe calculator merge perfect si am verificat pe mai multe texte.
Citat
Killed by signal 11(SIGSEGV).
asa apare peste tot. Ce bug as putea avea?  :-k 

Ruleaza in 5 secude, cam depasesc limita de timp...Ce as putea sa-i fac sa se incadreze in timp?

In primul rand, pentru erorile returnate de evaluator poti consulta: http://infoarena.ro/documentatie/evaluator , iar in al doilea rand pentru a imbunatatii solutia ta la problema Teams, poti consulta solutia oficiala: http://infoarena.ro/junior-challenge/solutii


Titlul: Răspuns: 474 Teams
Scris de: A Cosmina - vechi din Iunie 17, 2009, 11:00:36
Ok,mersi  :)


Titlul: Răspuns: 474 Teams
Scris de: aladin aladinn din August 06, 2009, 17:52:48
am facut cu un vector de 36800 de elemente ,v[ i ]=nr de elemente <= i , am si parsat citirea dar iau 50 cu wa pe ultimele  5 teste .complexitatea e O(b) ,determin pt fiecare i cate perechi pot face cu nr mai mici ca el. poate sa ma ajute cineva ? nu stiu ce as putea sa gresesc , trb nr mari?


Titlul: Răspuns: 474 Teams
Scris de: Rosca Valentin din Octombrie 28, 2009, 09:47:50
cum as putea sa scurtez 2 foruri?
Cod:
	for(i=1;i<=n-q;i++)	
for(j=i+1;j<=n-q;j++)
if(v[i]+v[j]>=a&&v[i]+v[j]<=b)
cnt++;
](*,)
iau 70 pt.


Titlul: Răspuns: 474 Teams
Scris de: Emanuel Cinca din Octombrie 28, 2009, 18:42:29
Cautare binara.


Titlul: Răspuns: 474 Teams
Scris de: Rosca Valentin din Octombrie 29, 2009, 17:58:01
Si ceva mai putin complicat nu este? :-k
Pt. 80 de pt. ca sigur mai faceti un vector in care sa retineti nr.<=b-1,si citirea recursiva.


Titlul: Răspuns: 474 Teams
Scris de: UAIC.VlasCatalin din Ianuarie 05, 2012, 00:01:57
Se poate si fara cautare binara si intra mai bine in timp, chiar si fara parsare T_max=24 ms, trebue doar sa parcurgi de trei ori un vector de la valoarea minima pina la valoarea maxima a sirului  :D \:D/


Titlul: Răspuns: 474 Teams
Scris de: cius catalin din Ianuarie 10, 2012, 14:15:46
Ce nu-i bn ca iau numa 60
   
Cod:
 for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
    if((s[i]+s[j])>=a && (s[i]+s[j])<=b)
    c++;
    out<<c;
     ](*,) ](*,) ](*,)

Editat de admin: Foloseste tagul "code" cand postezi surse.


Titlul: Răspuns: 474 Teams
Scris de: Paul-Dan Baltescu din Ianuarie 10, 2012, 15:18:36
Nu-i bn complexitatea.


Titlul: Răspuns: 474 Teams
Scris de: Aiordachioaei Marius din Iunie 04, 2012, 16:20:25
de ce iau 0 puncte pe urmatorul cod?

Cod:
        scanf("%d%d%d",&n,&a,&b);cin.get();gets(s);
for(i=0,l=strlen(s),s[l]=' ';i<=l;i++)
if(s[i]!=' ')
aux=aux*10+s[i]-'0';
else
for(v[++st]=aux,aux=0,j=st-1;j>=1;j--)
if(v[st]+v[j]>=a&&v[st]+v[j]<=b)
st2++;
printf("%d",st2);


Titlul: Răspuns: 474 Teams
Scris de: Cosmin Rusu din Ianuarie 05, 2013, 18:34:47
Buna. Am incercat sa rezolv problema asta cu cautare binara. Am doua surse una care ia 90 de puncte cu TLE pe ultimul test, si una cu 0 puncte cu Incorect pe fiecare. Prima face citirea pe streamuri, iar a doua parsata. Am incercat si cu printf si scanf dar au avut acelasi rezultat ca streamurile.
Aici sunt cele doua surse
Cod:
#include<fstream>
using namespace std;
long long n, a[100001];
long long A,B,c,i,j;
void quickSort(long long arr[], long long left, long long  right) {
      long long i = left, j = right;
      long long tmp;
      long long pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}
int caz1(int b, int li)
{
    int  ls=n, mij, fin;
    while( li<=ls)
    {
        mij=(li+ls)/2;
        if (a[mij]<=b)
        {
            fin=mij;
            li=mij+1;
        }
        else
            ls=mij-1;
    }
    return fin;
}
 
int caz2(int b, int li)
{
    int ls=n,mij,fin;
    while(li<=ls)
    {
    mij=(li+ls)/2;
    if (a[mij]>=b)
    {
        fin=mij;
        ls=mij-1;
    }
    else
    li=mij+1;
    }
    return fin;
}
int main()
{
    ifstream cin("teams.in");
    ofstream cout("teams.out");
    cin>>n>>A>>B;
    for(i=1;i<=n;i++)
    cin>>a[i];
    cin.close();
    quickSort(a, 1, n);
    for(i=1;i<n;i++)
       if(a[i]+a[i+1]<=B) { //cout<<a[i]<< " "<<caz1(B-a[i], i+1)-caz2(A-a[i], i+1);
     c+=caz1(B-a[i], i+1)-caz2(A-a[i], i+1)+1 ;}
    cout<<c;
    cout.close();
    return 0;
}


Cod:
#include<fstream>
#include<string.h>
using namespace std;
long long n, a[100001];
char s[100005];
long long A,B,c,i,j;
void quickSort(long long arr[], long long left, long long  right) {
      long long i = left, j = right;
      long long tmp;
      long long pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}
int caz1(int b, int li)
{
    int  ls=n, mij, fin;
    while( li<=ls)
    {
        mij=(li+ls)/2;
        if (a[mij]<=b)
        {
            fin=mij;
            li=mij+1;
        }
        else
            ls=mij-1;
    }
    return fin;
}
 
int caz2(int b, int li)
{
    int ls=n,mij,fin;
    while(li<=ls)
    {
    mij=(li+ls)/2;
    if (a[mij]>=b)
    {
        fin=mij;
        ls=mij-1;
    }
    else
    li=mij+1;
    }
    return fin;
}
int main()
{
    ifstream cin("teams.in");
    ofstream cout("teams.out");
    cin>>n>>A>>B;
    char abc[100];
cin.getline(abc, 100);
    cin.getline(s,100005);
    long long x=0;
    n=0;
    long aux=0;
    long poz=0;
for (i=0;s[i];++i){
    if (s[i]==' '){
       a[++n]=aux;
       aux=0;
    }
    else
        aux=aux*10+s[i]-'0';
}
a[++n]=aux;
    //for(i=1;i<=n;i++)
    //  cout<<a[i]<<" ";
    cin.close();
    quickSort(a, 1, n);
    for(i=1;i<n;i++)
       if(a[i]+a[i+1]<=B) { //cout<<a[i]<< " "<<caz1(B-a[i], i+1)-caz2(A-a[i], i+1);
     c+=caz1(B-a[i], i+1)-caz2(A-a[i], i+1)+1 ;
  }
    cout<<c;
    cout.close();
    return 0;
}

Practic e aceeasi chestie, dar nu inteleg totusi de ce pe a doua sursa primesc incorect  ](*,). Va rog sa ma ajutati sa inteleg ce si unde gresesc. Multumesc anticiat.


Titlul: Răspuns: 474 Teams
Scris de: Sorin Rita din Ianuarie 05, 2013, 19:03:07
In loc sa te chinui sa parsezi ai putea sa incerci sa folosesti sort() din stl. Merge mai repede si cred ca asta e optimizarea de care ai tu nevoie.


Titlul: Răspuns: 474 Teams
Scris de: Cosmin Rusu din Ianuarie 05, 2013, 20:00:47
Nu, nu e aia. Am incercat si e la fel.
Cu quickSort: http://infoarena.ro/job_detail/848689
Cu sort din algorithm http://infoarena.ro/job_detail/848678
Cu parsare, care intra lejer in timp http://infoarena.ro/job_detail/848655.

In rest nu mai stiu ce sa-i fac sa mearga cu parsare bine. Mentionez ca pe exemplu merge.


Titlul: Răspuns: 474 Teams
Scris de: Simoiu Robert din Ianuarie 05, 2013, 20:06:55
Daca ai face int toate, ca nu trebuie long long, cred ca ti-ar intra in timp, si daca chiar vrei citire parsata, fa-o pe aia clasica cu fgets sau f.get din C/C++, care o face mai toata lumea.
[PS] Ca un sfat, lasa sort-ul din STL, isi face treaba cel mai bine.


Titlul: Răspuns: 474 Teams
Scris de: Alghisi Alessandro Paolo din Ianuarie 12, 2013, 17:17:24
Cod:
400 83 90
83 134 67 122 59 6 193 150 117 140 86 122 108 41 47 40 47 149 178 8 155 141 142 86 104 178 70 54 58 183 143 14 123 16 136 182 22 6 10 139 146 96 133 59 137 181 100 185 135 150 65 163 96 12 54 72 62 125 126 121 180 75 7 108 158 143 163 180 150 45 192 168 141 2 33 150 183 5 12 191 27 77 159 123 90 85 68 152 15 194 145 68 141 24 48 104 168 16 157 190 128 26 163 74 28 1 30 84 73 109 80 100 187 111 96 149 68 164 173 84 35 191 24 177 20 72 86 60 156 115 55 89 141 24 164 170 92 66 59 38 175 11 138 39 122 106 188 190 75 39 146 178 35 170 160 122 115 118 183 76 39 43 165 180 134 6 155 32 72 86 137 120 97 147 159 91 59 25 154 6 64 172 184 166 20 21 93 135 140 148 16 51 192 181 103 3 60 64 102 132 22 44 57 120 192 89 16 56 181 42 129 50 20 119 88 40 140 53 47 152 7 63 8 71 116 179 74 176 48 49 181 137 93 110 62 90 4 146 18 57 188 148 107 80 139 67 187 151 121 39 109 0 102 184 138 91 168 17 139 88 66 125 31 32 41 160 189 112 111 80 170 172 33 149 57 44 89 50 0 82 89 109 82 64 166 25 27 139 109 166 100 48 97 131 147 10 96 141 189 80 26 164 124 126 186 181 170 80 103 171 162 65 85 116 129 123 13 156 68 189 194 40 42 96 171 189 173 139 8 168 91 34 9 20 33 0 74 8 147 177 179 181 47 137 169 48 65 182 76 5 177 76 45 91 172 88 153 23 100 161 191 191 67 5 84 100 73 158 176 92 140 160 79 60 169 120 108 107 108 185 179 157 66 30 120 110 185 145 133 90 111 1 154 51 74 110 23 19 73 4

Pe testul asta cat va da ? 1308 ?  :?


Titlul: Răspuns: 474 Teams
Scris de: Salajan Razvan din Ianuarie 12, 2013, 17:24:17
Mie 1308.


Titlul: Răspuns: 474 Teams
Scris de: Alghisi Alessandro Paolo din Ianuarie 12, 2013, 17:36:00
Perfect .. atunci nu inteleg de ce iau 0  ](*,)

Dar pe testul acesta  :

Cod:
602 84 422
155 389 202 179 207 278 250 1 444 510 26 136 354 397 340 304 476 57 507 202 402 299 224 286 133 102 36 62 493 498 146 367 360 67 265 286 345 234 287 509 217 32 118 291 429 177 68 97 480 295 19 355 313 243 361 446 64 397 508 276 368 374 116 447 441 100 206 506 335 212 207 271 245 325 35 393 221 350 210 174 118 229 3 431 472 364 70 255 480 51 4 322 144 366 488 305 466 414 284 520 99 210 265 63 8 19 176 475 88 386 122 206 334 125 357 525 208 146 253 162 197 503 203 61 342 164 366 0 51 369 240 397 52 505 179 306 243 74 254 332 179 376 257 513 221 333 511 148 479 483 29 396 459 232 457 520 116 296 240 413 384 480 2 436 458 428 215 174 502 188 506 155 283 483 387 504 289 91 372 242 293 401 111 226 107 41 465 223 56 178 355 159 131 358 68 308 259 2 202 234 436 427 108 192 383 215 170 146 25 15 388 318 416 218 17 242 505 202 184 34 380 13 439 231 371 507 258 103 228 460 56 137 80 411 329 463 345 218 328 370 233 435 161 369 126 425 84 104 100 515 384 480 1 15 430 372 522 162 194 469 95 496 79 175 99 128 358 444 346 405 6 299 314 168 141 159 66 471 510 412 178 86 365 179 102 515 270 343 150 183 286 491 153 84 386 498 212 217 135 32 341 141 331 374 309 191 7 94 381 236 506 33 322 64 458 143 52 202 487 202 385 492 166 257 49 271 475 262 488 83 13 22 224 63 396 253 500 403 347 354 358 46 106 154 356 38 297 408 486 503 329 344 468 214 321 518 486 269 499 166 352 231 188 295 294 58 21 267 180 88 340 12 380 447 412 209 204 428 336 163 405 384 226 65 317 20 302 276 8 520 162 79 224 69 94 518 373 361 504 27 449 318 285 21 484 170 476 161 317 285 324 195 388 269 507 179 290 1 455 17 522 336 343 219 406 437 457 252 271 434 525 440 225 283 461 182 172 411 343 490 415 386 404 277 129 103 456 138 105 103 401 100 159 217 319 38 127 249 9 118 157 8 31 101 10 211 284 183 341 346 392 476 206 269 226 54 373 401 192 197 223 312 297 382 3 335 139 376 58 149 494 461 403 244 35 413 456 38 315 516 104 180 465 310 169 410 83 261 284 521 458 227 306 228 328 309 36 468 159 340 90 372 520 212 90 275 98 19 313 414 8 417 313 193 446 201 76 248 462 80 242 112 307 22 59 108 50 342 295 455 155 385 301 395 316 391 143 415 129 175 21 383 312 334 49 477 255 126 199 190 206 441 303 232 182 362 59 233 177 355 161 52 459 181 447 249 45 309 383 174 484 404 31 269 457 80 220 185 452 419 95 377

Ai putea sa-mi spui te rog cat iti da ? Cumva 54617 ?  :x


Titlul: Răspuns: 474 Teams
Scris de: Tudor Tiplea din Ianuarie 12, 2013, 17:37:17
Da 54617 da. :)


Titlul: Răspuns: 474 Teams
Scris de: Alghisi Alessandro Paolo din Ianuarie 12, 2013, 17:51:29
Ok , multumesc  :) in cazul acesta nu inteleg de ce iau incorect pe TOATE testele..


Titlul: Răspuns: 474 Teams
Scris de: Tudor Tiplea din Ianuarie 12, 2013, 18:01:56
Dupa f >> n >> a >> b pune getline(f,x) in loc de f.get() deoarece se pare ca sunt mai mult de 1 caracter dupa numerele n,a,b deci tu nu vei avea in string nici un numar. Vei lua 50 puncte daca faci asta. Bafta! :)


Titlul: Răspuns: 474 Teams
Scris de: Alghisi Alessandro Paolo din Ianuarie 12, 2013, 18:17:59
pff ... multumesc mult  :D stiu ce sa fac pentru 100  :)


Titlul: Răspuns: 474 Teams
Scris de: FMI Razvan Birisan din Martie 01, 2013, 19:14:03
Poate cineva să-mi arate o citire completă cu parsare ? :'( (de la declararea fișierelor)


Titlul: Răspuns: 474 Teams
Scris de: Silvia Andreea Robu din Martie 01, 2013, 19:32:07
Si eu sunt curioasa sa vad un program complet cu parsare :c
Ahh si cstdio este mai rapid decat fstream? o/


Titlul: Răspuns: 474 Teams
Scris de: FMI Razvan Birisan din Martie 04, 2013, 22:40:22
Si eu sunt curioasa sa vad un program complet cu parsare :c
Ahh si cstdio este mai rapid decat fstream? o/

Da,este mai rapid.Nu prea contează ,de obicei problemele de pe infoarena au o limită de timp în care se încadrează și citirea.

Parsare:
Cod:
# include <fstream>
# include <iostream>
using namespace std;

int v[100],n;
char sir[256];

int main()
{
    ifstream is("parsare.in");
    is.getline(sir,256,'\n'); // citesc numerele precum un sir de caractere

    int man=0,i;

    for( i = 0 ; sir[i] != '\0' ; ++i )
        if( sir[i] == ' ' )
        {
            v[++n] = man;
            man = 0;
        }
        else
            man = man*10 + sir[i]-'0';

    v[++n] = man; // pun ultimul element in vector

    //afisez vectorul
    for( i = 1 ; i <= n ; ++i )
        cout << v[i] << ' ';

    return 0;
}

PS: NU cred că discuția asta poate continua aici,acest topic e dedicat unei probleme din arhivă.


Titlul: Răspuns: 474 Teams
Scris de: fdproxy din Martie 05, 2013, 23:42:14
Poate cineva să-mi arate o citire completă cu parsare ? :'( (de la declararea fișierelor)

Ai mutat intrebarea. Incerc sa-ti raspund la intrebarea originala. Nu cunosc problema.

Parsarea unui fisier presupune utilizarea unui scanner (sau analizor lexical); scannerul sparge streamul de intrare in lexeme (token-uri sau cuvinte). De exemplu, sirul " 1234 test" poate fi vazut, din punct de vedere al lexemelor, astfel: "numar identificator".

Urmatorul exemplu foloseste un scanner ce intoarce doua tipuri de lexeme: intreg si caracter. Apoi scannerul este folosit pentru a afisa doar numerle.

Cod:
#include <fstream>
#include <string>
#include <iostream>

using namespace std;

// doua tipuri de lexeme (token): intreg si caracter plus sfarsit de stream
enum lexeme_kind { lexeme_eof, lexeme_char, lexeme_int };

// lexema contine tipul si valoarea
struct lexeme
{
  lexeme_kind k;
  union
  {
    int i;
    char c;
  } v;
  lexeme( int ai ) { k = lexeme_int; v.i = ai; }
  lexeme( char ac ) { k = lexeme_char; v.c = ac; }
  lexeme() { k = lexeme_eof; }
};

//
lexeme last_lexeme;

// "scanner" (citeste urmatoarea lexema din stream)
lexeme get_lexeme( istream& is )
{
  char c;
  
  // ignora whitespace
  ws( is );

  //
  is.get( c );
  if ( ! is )
    return last_lexeme = lexeme(); // eof sau error

  // daca este numar (ignoram numerele ce incep cu '+' sau '-')
  if ( isdigit( c ) )
  {
    string s;
    s += c;
    while ( is.get( c ) && isdigit( c ) )
      s += c;
    is.putback( c );
    return last_lexeme = lexeme( atoi( s.c_str() ) );
  }

  // nu e numar
  return last_lexeme = lexeme( c );
}

int main()
{
  //
  ifstream is( "test.txt" );
  if ( ! is )
    return -1;

  // citeste lexemele si afiseaza doar numerele
  while ( get_lexeme( is ).k != lexeme_eof )
    switch ( last_lexeme.k )
    {
    case lexeme_int: cout << last_lexeme.v.i << endl; break;
    case lexeme_char: break;
    default: return -2; // lexema necunoscuta
    }

  return 0;
}

P.S. Am citit enuntul. Sunt nedumerit. Cum s-a ajuns la probleme legate de parsare?!


Titlul: Răspuns: 474 Teams
Scris de: FMI Razvan Birisan din Martie 08, 2013, 22:20:18
Am ajuns la parsare foarte ușor,am încercat să rezolv problema și depășeam timpul limită pe ultimul test.
Pentru a reduce timpul am încercat o citire cu parsare...a durat ceva până când mi-am dat seama unde greșeam,dar am reușit. :winner1:


Titlul: Răspuns: 474 Teams
Scris de: fdproxy din Martie 18, 2013, 13:23:49
Am inteles.

Cred ca evaluarea tine cont de timpul de citire/scriere, asa ca un cod simplu, cum ar fi cel de mai jos, n-ar trebui sa afecteze evaluarea. Incadrarea in limitele impuse trebuie sa vina din algoritm.
Cod:
  // citire
  ifstream is( "teams.in" );
  is >> N >> A >> B;
  for ( i = 0; i < N; ++i )
  {
    is >> x;
    if ( x < B )
      ++c[ v[j++] = x ]; // aici lucrurile sunt amestecate putin: nu este numai citire; este implementata si o parte din algoritm
  }

  // algoritm
  // ...

  // scriere
  ofstream( "teams.out" ) << s / 2;
Desigur, se poate recurge la “parsare”, si am pus ghilimele pentru ca nu e o parsare adevarata, dar asta ar insemna ca a fost folosita o smecherie: nu a fost modificat algoritmul propriu-zis. Daca "parsarea" e folosita doar pentru a micsora timpul de executie, nu pentru a te incadra in timpul impus, atunci cred ca metoda poate fi acceptata.

Cred ca am inteles si care sunt standardele impuse pentru astfel de probleme: foarte relaxate. Intr-un mediu real ar trebui, de exemplu sa verifici limitele, sa folosesti alocare dinamica, tabele de asociere, etc. “Parsarea”, asa cum am vazut-o eu in codul din arhiva, e o smecherie: presupune ca datele de intrare sunt formate din cifre si spatii, lucru care in realitate este de neacceptat: in fisierul de intrare poate fi orice, nu ce ne imaginam noi ca ar trebui sa fie. Si ca sa vezi cat de reala e problema, cineva a postat mai sus un set de date de intrare presupus corect, dar care este in afara limitelor date de probleme: este inclusa si valoarea zero, desi valoarea minima este 1. Rezultatul obtinut de cel ce a postat setul a fost confirmat si de o alta persoana, desi setul este gresit.


Succes si mult sport.


Titlul: Răspuns: 474 Teams
Scris de: Potra Vlad din Februarie 06, 2014, 14:34:23
tare bizara problema asta... :thumbdown:

90:
Cod:
for (int i = 0; i < n; ++i)

100:
Cod:
for (int i = 0; i < n-1; ++i)


Titlul: Răspuns: 474 Teams
Scris de: Mocanu George din Februarie 09, 2014, 19:55:20
 :winner1:
Am ajuns sa cred ca problema asta e blestemata... Ce greseam eu la parsare(sau citire...)?Retin doar numerele mai mici ca b.
Cod:
freopen("teams.in","r",stdin);
    scanf("%d %d %d \n",&n,&a,&b);
    gets(s);fclose(stdin);n=0;
    for(i=0;s[i]!='\0';i++)
        if(s[i]==' ') {if(nr<=b)v[++n]=nr;nr=0;}
        else nr=nr*10+s[i]-'0';
    if(nr<=b)v[++n]=nr;nr=0;