InfoAs Atlas

<- Go back View preview

Problema Toate egale Divide et Impera

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Examples

Default code

Summary

Editorial

Problema se rezolvă folosind metoda **Divide et Impera**. Această metodă de programare presupune împărțirea problemei curente _mari_ în probleme tot mai mici, până când ajungem la probleme elementare (cazuri de bază) care se pot rezolva instant. Ne folosim de o funcție auxiliară recursivă. Mai multe detalii în lecția: **https://infoas.ro/lectie/123/divide-et-impera-metoda-de-programare-c**.

Pentru această problemă, definim o funcție cu doi parametri care delimitează secvența curentă. Dacă secvența curentă are lungimea `1` (adică `st == dr`), atunci putem rezolva problema pe loc: răspunsul secvenței curente este `1` sau `0`, după valoarea singurului element din secvență `a[st]` (dacă este sau nu egal cu un element arbitrar, de pildă, `a[1]`).

Pentru secvențe mai mari, le vom împărți la mijloc și vom prelucra fiecare jumătate în parte. Mai precis, dacă `st != dr`, atunci luăm mijlocul `mij = (st + dr) / 2`, calculăm răspunsul pentru secvențele `(st, mij)` și `(mij + 1, dr)` și mai apoi setăm răspunsul în funcție de cele două răspunsuri.

Răspunsul final, pe care îl și afișăm pe ecran, se află apelând funcția pentru secvența `(1, n)`.

Solution

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	1 KB	View
0-toate-egale-divide-et-impera.in	/ 100	10 January 2025 21:26	16 B	View
0-toate-egale-divide-et-impera.ok	/ 100	10 January 2025 21:26	2 B	View
1-toate-egale-divide-et-impera.in	/ 100	10 January 2025 21:26	1 KB	View
1-toate-egale-divide-et-impera.ok	/ 100	10 January 2025 21:26	2 B	View
2-toate-egale-divide-et-impera.in	/ 100	10 January 2025 21:26	1 KB	View
2-toate-egale-divide-et-impera.ok	/ 100	10 January 2025 21:26	2 B	View
3-toate-egale-divide-et-impera.in	/ 100	10 January 2025 21:26	1 KB	View
3-toate-egale-divide-et-impera.ok	/ 100	10 January 2025 21:26	2 B	View
In total: 10 files 6 KB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Toate egale Divide et Impera

Identification properties

Content properties

Technical properties

Delete all files