Mai jos veti gasi problema „Aeriana” data la Olimpiada Judeteana de Informatica in anul 2023 la clasa a V-a, iar dupa textul problemei veti gasi si rezolvarea mea.
Problema Aeriana:
O companie aeriana are planificate N zboruri. Fiecare zbor are asociate cate ¸sase numere naturale cu urmatoarea semnificatie: primul numar A1 identifica aeroportul de decolare, cel de-al doilea numar A2 identifica aeroportul de aterizare, urmatoarele patru numere naturale H1, M1, H2, si M2, reprezinta ın ordine ora si minutul decolarii, respectiv ora si minutul aterizarii. Aterizarea poate sa fie ın ziua curenta sau ın ziua urmatoare.
Un zbor poate sa dureze maximum 23 de ore ¸si 59 de minute. De exemplu, pentru H1 = 10, M1 = 5, H2 = 15, M2 = 20 aterizarea are loc ın aceeasi zi cu decolarea (zborul dureaza 5 ore si 15 minute), iar pentru H1 = 23, M1 = 5, H2 = 1, M2 = 15 aterizarea are loc ın ziua urmatoare (zborul dureaza 2 ore ¸si 10 minute).
Un virus informatic s-a infiltrat ın sistemele de calcul ale companiei ¸si a inversat momentul de decolare cu cel de aterizare al zborurilor pe care le considera speciale. Un zbor este considerat special de catre acest virus ın cazul ın care codul aeroportului de decolare, A1, este un numar prim, iar codul aeroportului de aterizare, A2, se divide cu suma cifrelor lui A1.
Cerinte:
Cunoscandu-se numarul de zboruri N si datele fiecaruia, inainte de interventia virusului, sa se determine:
1. Care este durata maxima a unui zbor, ınainte de interventia virusului.
2. Care este durata maxima a unui zbor, dupa interventia virusului. Se iau ın calcul atat duratele zborurilor inversate (speciale), cat ¸si duratele zborurilor neinversate (nespeciale).
Date de intrare:
Fisierul aeriana.in contine pe prima linie valoarea C (numarul cerintei, poate fi 1 sau 2), pe a doua linie valoarea N (numarul de zboruri). Pe fiecare dintre urmatoarele N linii sunt cate sase numere naturale A1, A2, H1, M1, H2, M2, ın aceasta ordine, despartite prin cate un spatiu, cu semnificatia din enunt.
Date de iesire:
Fisierul aeriana.out va contine pe prima linie doua numere naturale separate printr-un spatiu, reprezentand numarul de ore si respectiv numarul de minute ale zborului de durata maxima, ın conditiile cerintei specificate.
Restrictii si precizari:
– 1 <= N <= 1 000;
– 0 <= H1, H2 <= 23;
– 0 <= M1, M2 <= 59;
– 0 <= A1, A2 <= 1 000 000 000;
– Un zbor va dura cel putin un minut si cel mult 23 de ore si 59 de minute.
Exemplul 1:
aeriana.in:
1
3
47 55 0 0 23 59
1 437 23 43 10 34
11 457 10 43 10 23
aeriana.out:
23 59
Explicatii:
C=1, N=3. Duratele acestor zboruri sunt, ın ordine, 23 de ore si 59 de minute, 10 ore si 51 de minute, iar pentru ultimul zbor, 23 de ore si 40 de minute.
Exemplul 2:
aeriana.in:
2
3
47 55 0 0 23 59
1 437 23 43 10 34
11 457 10 43 10 23
aeriana.out:
23 40
Explicatii:
C = 2, N = 3. Pentru primul zbor A1=47 este numar prim, suma cifrelor sale este egala cu 11 si A2=55 se divide cu 11, deci primul zbor devine 23:59-00:00 si are o durata de 0 ore si 1 minut.
Al doilea zbor ramˆane nemodificat, deoarece 1 nu e prim.
Al treilea zbor ramane nemodificat. Chiar daca 11 este prim, 457 nu se divide cu 2 (suma cifrelor lui 11).
Zborul de durata maxima, dupa interventia virusului, este cel de-al treilea.
Mai jos veti gasi metoda mea de rezolvare a problemei:
#include <fstream>
#include <iostream>
#define MAXIMUM_NUMBER_OF_FLIGHTS 1001
typedef char strg[];
struct DurationOfFlight {
int minutes, flightNumber;
} durationOfFlightBefore[MAXIMUM_NUMBER_OF_FLIGHTS-1], durationOfFlightAfter[MAXIMUM_NUMBER_OF_FLIGHTS-1], temporaryDuration, maximumDurationBefore, maximumDurationAfter;
using namespace std;
int task, nflights, Flights[MAXIMUM_NUMBER_OF_FLIGHTS-1][6];
ifstream fin("aeriana.in");
ofstream fout("aeriana.out");
void read(), task1(), task2();
bool isPrime(int);
int sumOfDig(int);
int main() {
read();
if (task == 1) task1();
if (task == 2) task2();
}
void read() {
fin >> task;
fin >> nflights;
for (int i = 0; i < nflights; i++) {
fin >> Flights[i][0];
fin >> Flights[i][1];
fin >> Flights[i][2];
fin >> Flights[i][3];
fin >> Flights[i][4];
fin >> Flights[i][5];
}
}
void task1() {
int nofflight = 0;
for (; nofflight < nflights; nofflight++) {
if (Flights[nofflight][4]*60 + Flights[nofflight][5] < Flights[nofflight][2]*60 + Flights[nofflight][3]) {
temporaryDuration.minutes = (Flights[nofflight][4]*60 + Flights[nofflight][5] + 1440) -
(Flights[nofflight][2]*60 + Flights[nofflight][3]);
} else {
temporaryDuration.minutes = (Flights[nofflight][4]*60 + Flights[nofflight][5]) -
(Flights[nofflight][2]*60 + Flights[nofflight][3]);
}
temporaryDuration.flightNumber = nofflight;
durationOfFlightBefore[nofflight] = temporaryDuration;
}
nofflight = 0;
maximumDurationBefore.minutes = INT16_MIN;
for (; nofflight < nflights; nofflight++) {
if (durationOfFlightBefore[nofflight].minutes > maximumDurationBefore.minutes) {
maximumDurationBefore = durationOfFlightBefore[nofflight];
}
}
fout << maximumDurationBefore.minutes/60 << " " << maximumDurationBefore.minutes%60;
}
void task2() {
int nofflight = 0;
for (; nofflight < nflights; nofflight++) {
if (Flights[nofflight][4]*60 + Flights[nofflight][5] < Flights[nofflight][2]*60 + Flights[nofflight][3]) {
cout << nofflight << "=>> peste zi" <<endl;
temporaryDuration.minutes = (Flights[nofflight][4]*60 + Flights[nofflight][5] + 1440) -
(Flights[nofflight][2]*60 + Flights[nofflight][3]);
} else {
cout << nofflight << "=>> nu e peste zi" <<endl;
temporaryDuration.minutes = (Flights[nofflight][4]*60 + Flights[nofflight][5]) -
(Flights[nofflight][2]*60 + Flights[nofflight][3]);
}
temporaryDuration.flightNumber = nofflight;
durationOfFlightAfter[nofflight] = temporaryDuration;
}
nofflight = 0;
maximumDurationAfter.minutes = INT16_MIN;
//////////////////////////////////--VIRUS--//////////////////////////////////
nofflight = 0;
for (; nofflight < nflights; nofflight++) {
if ((Flights[nofflight][1] % sumOfDig(Flights[nofflight][0]) == 0) && isPrime(Flights[nofflight][0])) {
cout << nofflight << "=>> infectat" << endl;
int aux = Flights[nofflight][2];
Flights[nofflight][2] = Flights[nofflight][4];
Flights[nofflight][4] = aux;
aux = Flights[nofflight][3];
Flights[nofflight][3] = Flights[nofflight][5];
Flights[nofflight][5] = aux;
}
}
////////////////////////////////////////////////////////////////////////////
for (nofflight = 1; nofflight < nflights; nofflight++) {
if (durationOfFlightAfter[nofflight].minutes > maximumDurationAfter.minutes && durationOfFlightAfter[nofflight].minutes > durationOfFlightAfter[nofflight-1].minutes)
maximumDurationAfter = durationOfFlightAfter[nofflight];
}
cout << maximumDurationAfter.minutes;
fout << maximumDurationAfter.minutes/60 << " " << maximumDurationAfter.minutes%60;
}
bool isPrime(int number) {
int numberOfDiv = 2;
if (number <3) {
return false;
}
for (int i = 2; i <= number/2; i++) {
if (number%i==0) return false;
}
return true;
}
int sumOfDig(int number) {
short sum = 0; //byteforce
while (number>0) {
sum += number%10;
number /= 10;
}
return sum;
}
Sper sa va fie de folos, daca aveti intrebari, va rog sa lasati un mesaj mai jos in comentarii.
multumesc pentru rezolvare, ma blocasem undeva si nu i-am dat de capat si m-a ajutat rezolvarea ta.
Cu placere!