Olimpiada Judeteana de Informatica 2020. Rezolvare problema „Cartonase” in C++, clasa a V-a

Mai jos veti gasi problema „Cartonase” data la Olimpiada Judeteana de Informatica in anul 2020 la clasa a V-a, iar dupa textul problemei veti gasi si rezolvarea mea.

Problema Cartonase:

Ionel are N cartonase. Fiecare cartonas are ınscrise doua numere (un numar, s, ın partea stanga, si celalalt numar, d, ın partea dreapta).
El a asezat cartonasele ıntr-un sir, lipite unul de celalalt, astfel ıncat numarul din partea dreapta a primului cartonas este lipit de numarul din partea stanga a celui de-al doilea cartonas, numarul din partea dreapta a celui de al doilea cartonas este lipit de numarul din partea stanga a celui de-al treilea cartonas etc.
Spunem ca doua cartonase alaturate ”se potrivesc” daca numarul din dreapta al primului cartonas este egal cu numarul din stanga al celui de al doilea cartonas.
Ionel observa ca sunt perechi de cartonase alaturate care ”se potrivesc” si chiar secvente de mai multe cartonase alaturate, ın care primul ”se potriveste” cu al doilea, al doilea ”se potriveste” cu al treilea etc.

Cerinte:

Scrieti un program care sa citeasca numarul N de cartonase, numerele inscrise pe fiecare cartonas si determina:

  1. Numarul de perechi de cartonase care ”se potrivesc”.
  2. Numarul de cartonase din cea mai lunga secventa ın care fiecare doua cartonase alaturate ”se potrivesc”.
  3. Numarul de secvente cu numar maxim de cartonase care ”se potrivesc”.

Date de intrare:

Fisierul de intrare cartonase.in contine doar numere naturale nenule:
– pe prima linie se gaseste numarul C care poate avea doar valorile 1, 2 sau 3 si reprezinta cerinta care urmeaza a fi rezolvata. Pe a doua linie a fisierului se gaseste numarul natural N, cu semnificatia din enunt.
– pe fiecare dintre urmatoarele N linii se afla, ın acesta ordine, cate doua numere naturale s si d, separate printr-un spatiu, cu semnificatia din enunt pentru un cartonas. Perechile de numere sunt date ın ordinea ın care cartonasele corespunzatoare lor apar ın sirul lui Ionel.

Date de iesire: 

Fisierul de iesire cartonase.out va contine pe prima linie un numar natural reprezentˆand raspunsul la cerinta specificata.

Restrictii si precizari:

  1. 1 <= N <= 500
  2. 1 <= s <= 10 000
  3. 1 <= d <= 10 000
  4. Pentru rezolvarea fiecarei cerinte se obtin cate 30 de puncte.

Exemplul 1:

cartonase.in:
1
5
2 10
10 5
10 2
2 10
37 5

cartonase.out:
2

Explicatii:

Sunt 2 perechi de cartonase alaturate care ”se potrivesc”:

  • primul cu al doilea (2 10 si 10 5)
  • al treilea cu al patrulea (10 2 si 2 10)

Exemplul 2:

cartonase.in:
2
5
2 10
10 5
5 2
2 10
37 5

cartonase.out:
4

Explicatii:

Primele patru cartonase formeaza o secventa ın care fiecare doua cartonase alaturate ”se potrivesc”:

  • primul cartonas cu al doilea (2 10 ¸si 10 5)
  • al doilea cartonas cu al treilea (10 5 ¸si 5 2)
  • al treilea cartonas cu al patrulea (5 2 ¸si 2 10)

Exemplul 3:

cartonase.in:
3
6
2 10
10 5
2 8
6 2
2 10
37 5

cartonase.out:
2

Explicatii:

Sunt maximum doua cartonase alaturate care se potrivesc. In fisier exista doua secvente de cate doua cartonase care ”se potrivesc”: primele doua cartonase si al patrulea cu al cincilea cartona¸


Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>

using namespace std;

ifstream fin("cartonase.in");
ofstream fout("cartonase.out");
int task, numberonumbers, lastRight, currentLeft, $temp, task1, task2 = 0, task3 = 0, index = 0;
int pairs[500];

int main() {
   fin >> task >> numberonumbers;
   if (task == 1) {
      fin >> $temp >> lastRight;
      for (int pair = 1; pair < numberonumbers; pair++) {
         fin >> currentLeft;
         if (lastRight == currentLeft) task1++;
         fin >> lastRight;
      }
      fout << task1;
   } else if (task == 2) {
      fin >> $temp >> lastRight;
      for (int pair = 1; pair < numberonumbers; pair++) {
         fin >> currentLeft;
         if (lastRight == currentLeft) {
            pairs[index++] = pair;
         }
         fin >> lastRight;
      }
      int k = 0;
      for (int i = 1; i < index; i++) {
         if (pairs[i] - pairs[i - 1] == 1) k++;
         else k = 0;
         if (k > task2) task2 = k;
      }
      fout << task2 + 2;
   } else {
      fin >> $temp >> lastRight;
      for (int pair = 1; pair < numberonumbers; pair++) {
         fin >> currentLeft;
         if (lastRight == currentLeft) {
            pairs[index++] = pair;
         }
         fin >> lastRight;
      }
      int k = 0, maxi = 0;
      for (int i = 1; i < index; i++) {
         if (pairs[i] - pairs[i - 1] == 1) k++;
         else k = 0;
         if (k > maxi) maxi = k;
         else if (k == maxi) task3++;
      }
      fout << task2 + 2;
   }
   return 0;
}

Sper sa va fie de folos. 😉

Daca aveti intrebari, va rog sa lasati un mesaj mai jos in comentarii.

Ma numesc Sebastian, am 10 ani si sunt pasionat de: programare in Python, C++, Raspberry Pi, citit, astronomie, astrofizica, chimie, sport, fotografie si Xbox. Ma gasesti si pe: Instagram, Youtube, Facebook

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *