Editing 1127 - Praslea

A fost odată ca niciodată un împărat puternic  care avea o grădină minunată, situată pe un teren de formă dreptunghiulară din jurul palatului. În grădină creştea  un măr cu  mere de aur, dar împăratul nu a putut să se bucure vreodată de merele din pom deoarece grădina a fost mereu atacată de tâlhari şi merele au fost furate. Cu toate că aceasta a fost păzită zi şi noapte de cei mai viteji ostaşi din împărăţie, ei nu au putut face faţă tâlhăriilor. Deznădăjduit, împăratul şi-a pus în gând să taie pomul cu mere de aur, dar fiul său cel mic, Prâslea, l-a rugat să-l lase şi pe el să-şi încerce norocul. Prâslea a cugetat foarte bine la cele întâmplate şi a procedat astfel:

* a delimitat în grădină, de-a lungul acesteia, <code>N</code> parcele alăturate, numerotate de la stânga la dreapta cu valori în ordine, de la <code>1</code> la <code>N</code>. Dintre acestea, a dat spre pază fraţilor şi verişorilor săi <code>M</code> parcele, iar restul de <code>N-M</code> parcele oştenilor din împărăţie. Cele <code>N-M</code> parcele date oştenilor sunt identice şi au fiecare lăţimea <code>L</code>.
* a măsurat distanţa <code>D</code> la care se află pomul cu merele de aur faţă de marginea din stânga a grădinii, pentru a întări chiar el paza parcelei în care e situat acesta.

Cerinţă

'''a)''' Cunoscând lăţimea fiecărei parcele, determinaţi cel mai mare număr de parcele alăturate, de lăţime <code>L</code> fiecare, date spre pază oştenilor ; 

'''b)''' Determinaţi numărul de ordine al parcelei în care se află pomul cu merele de aur.

= Date de intrare =
Fișierul de intrare <code>praslea.in</code> conține

* pe prima linie trei numere naturale <code>N</code>, <code>M</code> şi <code>L</code>, în această ordine, despărţite prin câte un spaţiu, având semnificaţia din enunţ;
* pe următoarele <code>M</code> linii, câte două numere naturale <code>Pi</code> şi <code>L<sub>i</sub></code>, despărţite prin câte un spaţiu, reprezentând numărul de ordine, respectiv lăţimea fiecărei parcele dintre cele <code>M</code>, dată spre pază fraţilor şi verişorilor;
* pe următoarea linie un număr natural <code>D</code>, care reprezintă distanţa la care se află pomul cu merele de aur faţă de marginea din stânga a grădinii.

= Date de ieșire =
Fișierul de ieșire <code>praslea.out</code> va conține pe prima linie un singur număr natural determinat conform cerinţei '''a)''', iar pe cea de-a doua linie a fişierului un singur număr natural determinat conform cerinţei '''b)'''.

= Restricții și precizări =

* <code>1 ≤ N ≤ 500 000</code> şi <code>1 ≤ M ≤ 10 000</code> şi <code>M<N</code>;
* <code>1 ≤ L,L<sub>i</sub> ≤ 4 000 000 000</code>;
* Nicio parcelă dintre cele <code>M</code> nu are lăţimea egală cu <code>L</code>;
* Dacă  <code>D</code> este exact  pe linia ce desparte două parcele alăturate se consideră că pomul e situat în parcela din stânga
* Pentru rezolvarea corectă a cerinţei a) se acordă 20% din punctajul fiecărui test, iar pentru rezolvarea corectă a cerinţei b) se acordă 80% din punctajul fiecărui test.

= Exemplu: =
<code>praslea.in</code>
 8 3 2
 2 1
 5 4
 1 1
 7
<code>praslea.out</code>
 3
 5

= Explicație =
Sunt <code>8</code> parcele: <code>3</code> dintre ele au fost împărţite fraţilor şi verişorilor. Parcelele rămase pentru oşteni au toate lăţimea <code>2</code>. Dintre cele <code>3</code> parcele: parcela <code>2</code> are lăţimea <code>1</code>, parcela <code>5</code> are lăţimea <code>4</code> şi parcela <code>1</code> are lăţimea <code>1</code>. Pomul cu mere de aur se află la distanţa <code>7</code>  faţă de marginea din stânga a grădinii.

Sunt <code>3</code> parcele alăturate care au lăţimea egală cu <code>2</code> (parcelele numerotate cu <code>6</code>,@7@ şi <code>8</code>).

Pomul se află în parcela cu numărul de ordine <code>5</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
const fs = require('fs');

class Parcela {

  constructor(indice, latime) {

    this.indice = indice;

    this.latime = latime;

  }

}

function cmp(a, b) {

  return a.indice < b.indice;

}

function main() {

  const input = fs.readFileSync('praslea.in', 'utf8').split('\n');

  const [N, M, L] = input[0].split(' ').map(Number);

  const C = [];

  for (let i = 1; i <= M; i++) {

    const [indice, latime] = input[i].split(' ').map(Number);

    C.push(new Parcela(indice, latime));

  }

  const P = Number(input[M + 1]);

  C.push(new Parcela(N + 1, 0));

  C.sort(cmp);

  let max_parcele = N - C[M - 1].indice;

  let i = 0;

  let ok = 0;

  let indice_precedent = 0;

  let Pom = 0;

  while (i < M) {

    const alaturate = C[i].indice - indice_precedent - 1;

    max_parcele = Math.max(max_parcele, alaturate);

    if (!ok && P <= alaturate * L) {

      Pom = indice_precedent + Math.ceil(P / L);

      ok = 1;

    } else {

      if (alaturate > 0) P = P - alaturate * L;

      if (!ok && P <= C[i].latime) {

        Pom = C[i].indice;

        ok = 2;

      } else {

        P = P - C[i].latime;

      }

    }

    indice_precedent = C[i].indice;

    i++;

  }

  const fout = fs.createWriteStream('praslea.out');

  fout.write(`${max_parcele}\n`);

  if (ok === 0) {

    Pom = C[M - 1].indice + Math.ceil(P / L);

  }

  fout.write(`${Pom}\n`);

  fout.end();

}

</syntaxhighlight>