474 Teams

[•Flameingo]

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

[•CosminRusu]

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.

[•soriyn]

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.

[•CosminRusu]

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.

[•SpiderMan]

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.

[•alexalghisi]

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 ? 

[•vendetta]

Mie 1308.

[•alexalghisi]

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 ? 

[•tzipleatud]

Da 54617 da.

[•alexalghisi]

Ok , multumesc  in cazul acesta nu inteleg de ce iau incorect pe TOATE testele..

[•tzipleatud]

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!

[•alexalghisi]

pff ... multumesc mult  stiu ce sa fac pentru 100 

[•TheNechiz]

Poate cineva să-mi arate o citire completă cu parsare ? (de la declararea fișierelor)

[•Methus]

Si eu sunt curioasa sa vad un program complet cu parsare :c
Ahh si cstdio este mai rapid decat fstream? o/

[•TheNechiz]

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ă.

[•fdproxy]

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?!

[•TheNechiz]

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.

[•fdproxy]

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.

[•japjappedulap]

tare bizara problema asta...

90:

Cod:

for (int i = 0; i < n; ++i)

100:

Cod:

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

[•BaTDucK]

 
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;