1127 - Praslea - Revision history

Raul at 14:14, 14 December 2023

2023-12-14T14:14:33Z

← Older revision		Revision as of 14:14, 14 December 2023
Line 49:		Line 49:

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

	class Parcela {		class Parcela {

	constructor(indice, latime) {		constructor(indice, latime) {

	this.indice = indice;		this.indice = indice;

	this.latime = latime;		this.latime = latime;

	}		}

	}		}

	function cmp(a, b) {		function cmp(a, b) {

	return a.indice < b.indice;		return a.indice < b.indice;

	}		}

	function main() {		function main() {

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

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

	const C = [];		const C = [];

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

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

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

	}		}

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

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

	C.sort(cmp);		C.sort(cmp);

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

	let i = 0;		let i = 0;

	let ok = 0;		let ok = 0;

	let indice_precedent = 0;		let indice_precedent = 0;

	let Pom = 0;		let Pom = 0;

	while (i < M) {		while (i < M) {

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

	max_parcele = Math.max(max_parcele, alaturate);		max_parcele = Math.max(max_parcele, alaturate);

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

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

	ok = 1;		ok = 1;

	} else {		} else {

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

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

	Pom = C[i].indice;		Pom = C[i].indice;

	ok = 2;		ok = 2;

	} else {		} else {

	P = P - C[i].latime;		P = P - C[i].latime;

	}		}

	}		}

	indice_precedent = C[i].indice;		indice_precedent = C[i].indice;

	i++;		i++;

	}		}

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

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

	if (ok === 0) {		if (ok === 0) {

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

	}		}

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

	fout.end();		fout.end();

	}		}

			</syntaxhighlight>

Raul at 13:13, 10 December 2023

2023-12-10T13:13:15Z

← Older revision		Revision as of 13:13, 10 December 2023
Line 50:		Line 50:
	=== Lipește codul aici ===		=== Lipește codul aici ===
	1		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();

			}

Raul: Pagină nouă: 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...

2023-12-09T10:12:08Z

Pagină nouă: 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...

New page

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 ===
1