simulare OJI 2023 clasa 8 | hibrid

This was the problem page during the contest. Access the current page here.
Time limit: 0.3s Memory limit: 64MB Input: hibrid.in Output: hibrid.out

O mașină hibrid se deplasează pe o șosea rectilinie folosind, alternativ, fie motorul termic (pe benzină), fie motorul electric. Axa numerelor întregi poate fi folosită pentru a descrie coordonatele de pe șosea. Deplasarea mașinii folosind motorul electric se efectuează fără taxă, dar unele porțiuni din șosea necesită folosirea motorului termic, ceea ce impune plata anumitor taxe.
Se cunoaște lista celor PP porțiuni taxabile de șosea, numerotate de la 11 la PP, oricare două dintre ele fiind disjuncte. Fiecare porțiune este descrisă de trei numere întregi: stist_i, dridr_i și cic_i (1iP1 \leq i \leq P), cu semnificația că pe porțiunea de șosea situată între coordonatele stist_i și dridr_i (inclusiv la capetele stist_i și dridr_i) se va folosi motorul termic și se va achita taxa în valoare de cic_i lei. Această taxă se va plăti la fiecare traversare a porțiunii, indiferent de sensul deplasării.

Traseul pe care mașina hibrid îl are de străbătut conține NN borne amplasate pe șosea, numerotate de la 11 la NN, în ordinea în care acestea trebuie vizitate. Pentru fiecare dintre cele NN borne se cunoaște coordonata poziției sale pe șosea: x1,x2,x3,,xNx_1, x_2,x_3, \ldots, x_N. Deplasarea între două borne consecutive de pe traseu, adică între borna ii și borna (i+1)(i+1) (pentru fiecare ii: 1i<N1 \leq i < N), se face pe drumul cel mai scurt, respectiv pe segmentul de dreaptă ce unește punctele cu coordonatele xix_i și xi+1x_{i+1} de pe șosea. Mașina hibrid va începe traseul din dreptul bornei cu numărul de ordine 11, adică de la coordonata x1x_1 de pe șosea. De asemenea, se știe că nicio bornă de pe traseu nu se află în interiorul sau la capetele porțiunilor taxabile, unde se folosește deplasarea cu motorul termic.

Cerințe

Să se determine:

  1. numărul de ordine al porțiunii taxabile peste care se va trece de cele mai multe ori în călătorie (folosind motorul termic). Dacă există mai multe astfel de porțiuni, se va alege cea cu indicele minim, în funcție de ordinea dată în fișierul de intrare. De asemenea, în caz că nu se va trece peste nicio porțiune taxabilă, acest număr va fi egal cu 1-1.
  2. suma totală, exprimată în lei, care trebuie plătită pentru a parcurge traseul stabilit. În caz că nu se va trece peste nicio porțiune taxabilă, atunci această sumă va fi egală cu 00.

Date de intrare

Pe prima linie a fișierului de intrare hibrid.in se află, separate între ele prin câte un spațiu, trei numere naturale, CC, PP și NN, cu semnificațiile din enunț. CC poate avea fie valoarea 11, fie valoarea 22, în funcție de cerința care trebuie rezolvată. Pe următoarele PP linii se află, separate între ele prin câte un spațiu, câte trei numere întregi: stist_i, dridr_i și cic_i, cu semnificația de mai sus. Pe următoarea linie se află NN numere întregi, separate între ele prin câte un spațiu, reprezentând, în ordine, coordonatele bornelor ce trebuie vizitate: x1,x2,x3,,xNx_1, x_2,x_3, \ldots, x_N.

Date de ieșire

Fișierul de ieșire hibrid.out va conține, pe prima linie, un singur număr întreg, în funcție de cerința care trebuie rezolvată. Dacă C=1C = 1, atunci se va rezolva cerința 11, altfel, se va rezolva cerința 22.

Restricții și precizări

  • 2P100 0002 \leq P \leq 100 \ 000 și 2N200 0002 \leq N \leq 200 \ 000;
  • 300 000sti<dri300 000-300 \ 000 \leq st_i < dr_i \leq 300 \ 000 și 1ci100 0001 \leq c_i \leq 100 \ 000, pentru fiecare ii: 1iP1 \leq i \leq P;
  • 1 000 000xi1 000 000-1 \ 000 \ 000 \leq x_i \leq 1 \ 000 \ 000, pentru fiecare ii: 1iN1 \leq i \leq N;
  • Întrucât au dimensiuni neglijabile, pot exista și două sau mai multe borne situate la aceeași coordonată pe șosea;
  • Pe durata întregului traseu, motorul termic (pe benzină) este utilizat doar pentru parcurgerea porțiunilor taxabile peste care mașina hibrid trebuie să treacă. În rest, se folosește doar motorul electric, pentru a reduce poluarea;
  • Pentru teste în valoare de 4949 de puncte, C=1C = 1, iar pentru restul de teste, C=2C = 2;
  • Pentru 1111 puncte, pentru efectuarea traseului nu se va trece peste nicio porțiune taxabilă;
  • Pentru 88 puncte, 0sti0 \leq st_i, xjx_j și dri,xj70dr_i, x_j \leq 70, pentru fiecare ii și jj: 1iP1 \leq i \leq P, 1jN1 \leq j \leq N;
  • Pentru 1212 puncte, xi+1xi70|x_{i+1} - x_i| \leq 70, pentru fiecare ii: 1i<N1 \leq i < N și xi300 000|x_i| \leq 300 \ 000, pentru fiecare ii: 1iN1 \leq i \leq N;
  • Pentru 4040 de puncte, P,N3 000P, N \leq 3 \ 000;
  • Pentru 2929 de puncte, nu există restricții suplimentare.

Exemplul 1

hibrid.in

1 2 4
4 8 10
-10 -9 22
-14 20 -14 0

hibrid.out

2

Explicație (C=1C = 1)

Există două porțiuni taxabile (P=2P=2):

  • porțiunea 11 cuprinde coordonatele: 44, 55, 66, 77, 88 și are taxa de 1010 lei la fiecare trecere;
  • porțiunea 22 cuprinde coordonatele: 10-10, 9-9 și are taxa de 2222 de lei la fiecare trecere.

Traseul pe care mașina hibrid îl are de parcurs este alcătuit din N=4N = 4 borne, situate la coordonatele: 14-14 (prima bornă, din dreptul căreia se începe traseul), 2020 (a doua bornă), 14-14 (a treia bornă; de remarcat că este situată la aceeași coordonată ca și prima bornă!), respectiv 00 (a patra bornă).
Peste prima porțiune taxabilă se va trece de două ori, iar peste cea de a doua se va trece de trei ori. Prin urmare, se va afișa 22.

Exemplul 2

hibrid.in

2 2 4
4 8 10
-10 -9 22
-14 20 -14 0

hibrid.out

86

Explicație (C=2C = 2)

Conform explicației de mai sus, se va afișa 8686 (22 treceri ×10\times 10 lei/trecere +3+ 3 treceri ×22\times 22 lei/trecere =86= 86 de lei, adică suma totală plătită pentru efectuarea traseului).

Log in or sign up to be able to send submissions!