InfoAs Atlas

<- Go back View preview

Problema Asortat

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

Pune un lingvist și un programator unul lângă celălalt și întrebă-i ce înseamnă cuvântul _asortat_. Lingvistul ar putea să aducă până și definiția din DEX, căci programatorului nu o să îi pese și o va ține cu a lui: „Asortat înseamnă un lucru care nu este sortat”.  
  
Că tot veni vorba de lucruri sortate sau asortate, să presupunem că avem un șir oarecare de numere naturale, de lungime `n`. Definim următoarea operație: luăm un număr natural `i` de la `1` la `n`, iar pentru toate valorile cu indici de la `1` la `i`, le vom crește cu `1`.

## Cerință

Se dă un șir de `n` numere naturale. Să se determine numărul minim de operații de tipul celui descris mai sus astfel încât șirul să devină asortat.
## Date de intrare

Fișierul de intrare `asortat.in` conține pe prima linie numărul natural `n`. Pe a doua linie se află `n` numere naturale separate prin câte un spațiu, reprezentând elementele șirului dat.
## Date de ieșire

Fișierul de ieșire `asortat.out` conține un singur număr natural, reprezentând numărul minim de operații necesare pentru a transforma șirul într-unul asortat.
## Restricții și precizări

* `2 ≤ n ≤ 1.000.000`
  * `1 ≤ cele n numere ≤ 1.000.000.000`
  * Prin _șir sortat_ ne referim că fiecare element după primul este cel puțin egal cu cel anterior lui

### Subtaskuri

#| Descriere| Punctaj  
---|---|---  
1| `n = 2`| 5 puncte  
2| Șirul este deja asortat| 15 puncte  
3| Șirul este sortat și există cel puțin două numere egale| 10 puncte  
4| Fără restricții suplimentare| 70 de puncte

Examples

[{"input": "5\n1 5 10 14 16", "output": "3", "explanation": "Pentru primul exemplu. Num\u0103rul minim de opera\u021bii necesare este <code>3</code>; de exemplu, una dintre solu\u021bii ar fi s\u0103 aplic\u0103m opera\u021bia pe pozi\u021bia <code>4</code> (num\u0103rul <code>14</code>), de trei ori, astfel ajung\u00e2nd la \u0219irul <code>4 8 13 17 16</code>, asortat. Cu doar <code>0</code>, <code>1</code> sau <code>2</code> opera\u021bii nu putem transforma \u0219irul \u00eentr-unul asortat. Pentru al doilea exemplu. \u0218irul este deja asortat, a\u0219adar r\u0103spunsul este <code>0</code>."}, {"input": "4\n1 4 2 5", "output": "0", "explanation": "Pentru primul exemplu. Num\u0103rul minim de opera\u021bii necesare este <code>3</code>; de exemplu, una dintre solu\u021bii ar fi s\u0103 aplic\u0103m opera\u021bia pe pozi\u021bia <code>4</code> (num\u0103rul <code>14</code>), de trei ori, astfel ajung\u00e2nd la \u0219irul <code>4 8 13 17 16</code>, asortat. Cu doar <code>0</code>, <code>1</code> sau <code>2</code> opera\u021bii nu putem transforma \u0219irul \u00eentr-unul asortat. Pentru al doilea exemplu. \u0218irul este deja asortat, a\u0219adar r\u0103spunsul este <code>0</code>."}]

Default code

Summary

Editorial

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	3 KB	View
0-asortat.in	/ 100	10 January 2025 21:26	5 B	View
0-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
1-asortat.in	/ 100	10 January 2025 21:26	2 KB	View
1-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
2-asortat.in	/ 100	10 January 2025 21:26	482 KB	View
2-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
3-asortat.in	/ 100	10 January 2025 21:26	9 MB	View
3-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
4-asortat.in	/ 100	10 January 2025 21:26	5 KB	View
4-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
5-asortat.in	/ 100	10 January 2025 21:26	5 MB	View
5-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
6-asortat.in	/ 100	10 January 2025 21:26	594 B	View
6-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
7-asortat.in	/ 100	10 January 2025 21:26	28 KB	View
7-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
8-asortat.in	/ 100	10 January 2025 21:26	468 KB	View
8-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
9-asortat.in	/ 100	10 January 2025 21:26	193 KB	View
9-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
10-asortat.in	/ 100	10 January 2025 21:26	75 KB	View
10-asortat.ok	/ 100	10 January 2025 21:26	1 B	View
11-asortat.in	/ 100	10 January 2025 21:26	7 KB	View
11-asortat.ok	/ 100	10 January 2025 21:26	3 B	View
12-asortat.in	/ 100	10 January 2025 21:26	764 B	View
12-asortat.ok	/ 100	10 January 2025 21:26	5 B	View
13-asortat.in	/ 100	10 January 2025 21:26	762 B	View
13-asortat.ok	/ 100	10 January 2025 21:26	5 B	View
14-asortat.in	/ 100	10 January 2025 21:26	765 B	View
14-asortat.ok	/ 100	10 January 2025 21:26	5 B	View
15-asortat.in	/ 100	10 January 2025 21:26	32 KB	View
15-asortat.ok	/ 100	10 January 2025 21:26	2 B	View
16-asortat.in	/ 100	10 January 2025 21:26	7 KB	View
16-asortat.ok	/ 100	10 January 2025 21:26	4 B	View
17-asortat.in	/ 100	10 January 2025 21:26	7 KB	View
17-asortat.ok	/ 100	10 January 2025 21:26	4 B	View
18-asortat.in	/ 100	10 January 2025 21:26	7 KB	View
18-asortat.ok	/ 100	10 January 2025 21:26	4 B	View
19-asortat.in	/ 100	10 January 2025 21:26	7 KB	View
19-asortat.ok	/ 100	10 January 2025 21:26	3 B	View
In total: 42 files 16 MB

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 Asortat

Identification properties

Content properties

Technical properties

Delete all files