Grade 12 · Baccalaureate exam reviewCitește în română
File: the longest run of terms with the same parity
Original: Fișier — cea mai lungă secvență de termeni cu aceeași paritate
The idea
The task (exam part III.3 style): the file date.in holds a sequence of at most 10^6 natural numbers with at most 9 digits. A parity run is a run of consecutive terms that all have the same parity. Print the maximum length of a parity run and the number of parity runs that have this length and cannot be extended. Efficiency: we read the numbers one by one and keep only the parity of the previous term and the length of the current run; when the parity changes, the current run has ended and we compare it with the maximum. No array is used, so memory is constant.
Original description (Romanian)
Cerința (tip subiectul III.3): fișierul date.in conține un șir de cel mult 10^6 numere naturale de cel mult 9 cifre. O secvență paritară este o secvență de termeni consecutivi care au toți aceeași paritate. Afișați lungimea maximă a unei secvențe paritare și numărul de secvențe paritare care au această lungime și nu pot fi prelungite. Eficiența: citim numerele pe rând și ținem doar paritatea termenului anterior și lungimea secvenței curente; la schimbarea parității secvența curentă s-a încheiat și o comparăm cu maximul. Nu folosim niciun tablou, deci memoria este constantă.
- Complexity
- O(n) timp, O(1) memorie
- Grade
- Grade 12 (Clasa a XII-a)
- Chapter
- Baccalaureate exam review
Examples
Input (date.in)
3 5 8 2 4 7 9 11 6
Expected output
3 2
Input (date.in)
10
Expected output
1 1
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* Titlu: Fișier — cea mai lungă secvență de termeni cu aceeași paritate
* Clasa: 12
* Capitol: Recapitulare pentru bacalaureat
* Descriere: Cerința (tip subiectul III.3): fișierul date.in conține un șir de cel
* mult 10^6 numere naturale de cel mult 9 cifre. O secvență paritară
* este o secvență de termeni consecutivi care au toți aceeași paritate.
* Afișați lungimea maximă a unei secvențe paritare și numărul de
* secvențe paritare care au această lungime și nu pot fi prelungite.
* Eficiența: citim numerele pe rând și ținem doar paritatea
* termenului anterior și lungimea secvenței curente; la schimbarea
* parității secvența curentă s-a încheiat și o comparăm cu maximul.
* Nu folosim niciun tablou, deci memoria este constantă.
* Complexitate: O(n) timp, O(1) memorie
*
* Exemplu
* Intrare: 3 5 8 2 4 7 9 11 6
* Ieșire: 3 2
*
* Exemplu
* Intrare: 10
* Ieșire: 1 1
*/
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream fin("date.in");
long long x;
int paritateAnt = -1, lung = 0, lungMax = 0, cate = 0;
while (fin >> x)
{
int p = x % 2;
if (p == paritateAnt)
lung++;
else
{
// s-a încheiat secvența anterioară (dacă exista una)
if (lung > lungMax)
{
lungMax = lung;
cate = 1;
}
else if (lung == lungMax && lung > 0)
cate++;
lung = 1;
paritateAnt = p;
}
}
// ultima secvență se încheie la sfârșitul fișierului
if (lung > lungMax)
{
lungMax = lung;
cate = 1;
}
else if (lung == lungMax && lung > 0)
cate++;
cout << lungMax << ' ' << cate << '\n';
return 0;
}
Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.