InfoAs Atlas

<- Go back View preview

Problema Invartire paranteze

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

**Observație.** Deoarece lungimea șirului este mereu pară, mereu va exista o soluție.

**Soluție.** Soluția optimă pentru această problemă este una greedy. Mai precis, de fiecare dată când ajungem în punctul în care este o paranteză închisă fără vreo pereche mai devreme (deci astfel o parantezare greșită), atunci o transformăm în paranteză deschisă, iar în caz contrar, păstrăm parantezele așa cum sunt.

Creăm o variabilă de tip contor numită `crt`, inițial egală cu `0`. Valoarea acestui contor reține, pe fiecare poziție, nivelul de parantezare curent (mai precis, câte paranteze sunt momentan deschise). La începutul șirului, `crt = 0`, iar în timp ce parcurgem șirul de paranteze, incrementăm `crt` cu `1` (`crt++`) la o paranteză deschisă și analog, decrementăm `crt` cu `1` (`crt--`) la o paranteză închisă.

Dacă, vreodată, ajungem cu contorul egal cu `-1` (adică mai precis toate parantezele care au fost deschise s-au închis și acum a apărut o paranteză închisă care nu are pereche), atunci o transformăm în paranteză deschisă, astfel:

* numărăm o operație de învârtire de paranteză;
  * setăm `crt` egal cu `1` (adică în loc să fie paranteză închisă în care `crt` a scăzut de la `0` la `-1`, avem paranteză deschisă, unde `crt` a crescut de la `0` la `1`).

La final, trebuie să mai verificăm dacă există vreo paranteză deschisă care încă nu a fost închisă. Pentru o parantezare corectă, `crt` ar trebui să aibă valoarea finală `0` (toate parantezele deschise au fost închise), iar dacă are o valoare pozitivă, garantat o să fie un număr par de paranteze deschise, dintre care jumătate trebuie închise. Așadar, adunăm la răspuns `crt / 2`.

Afișăm răspunsul pe ecran.

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	956 B	View
0-invartire-paranteze.in	/ 100	10 January 2025 21:26	4 B	View
0-invartire-paranteze.ok	/ 100	10 January 2025 21:26	1 B	View
1-invartire-paranteze.in	/ 100	10 January 2025 21:26	444 B	View
1-invartire-paranteze.ok	/ 100	10 January 2025 21:26	1 B	View
2-invartire-paranteze.in	/ 100	10 January 2025 21:26	7 KB	View
2-invartire-paranteze.ok	/ 100	10 January 2025 21:26	2 B	View
3-invartire-paranteze.in	/ 100	10 January 2025 21:26	48 KB	View
3-invartire-paranteze.ok	/ 100	10 January 2025 21:26	3 B	View
In total: 10 files 57 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 Invartire paranteze

Identification properties

Content properties

Technical properties

Delete all files