Pentru a putea rula codul, te rugăm să te autentifici.

Autentifică-te
main.cpp

ID #795 · BlitzCode, ediția 1 · Parcurgerea vectorilor

Problema Asortat

Medie · 4

Memorie: 16 MB / 8 MB

Timp: 0.05 secunde

I/O: Fișiere

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

Exemple

asortat.in

5
1 5 10 14 16

asortat.out

3

Explicație

Pentru primul exemplu. Numărul minim de operații necesare este 3; de exemplu, una dintre soluții ar fi să aplicăm operația pe poziția 4 (numărul 14), de trei ori, astfel ajungând la șirul 4 8 13 17 16, asortat. Cu doar 0, 1 sau 2 operații nu putem transforma șirul într-unul asortat.

Pentru al doilea exemplu. Șirul este deja asortat, așadar răspunsul este 0.

asortat.in

4
1 4 2 5

asortat.out

0

Explicație

Pentru primul exemplu. Numărul minim de operații necesare este 3; de exemplu, una dintre soluții ar fi să aplicăm operația pe poziția 4 (numărul 14), de trei ori, astfel ajungând la șirul 4 8 13 17 16, asortat. Cu doar 0, 1 sau 2 operații nu putem transforma șirul într-unul asortat.

Pentru al doilea exemplu. Șirul este deja asortat, așadar răspunsul este 0.

ID #795 Autor Dominic Satnoianu
Set BlitzCode, ediția 1 Adăugată de Alexis Alexis lexington
Capitol Clasa a IX-a/Vectori (tablouri unidimensionale)/Parcurgerea vectorilor
Licență

Problema aceasta a fost publicată sub licența CC BY-SA 4.0. Indicațiile sunt publicate sub licența InfoAs Standard License, iar rezolvarea sub licența InfoAs Standard License. Licența InfoAs Standard License nu permite copierea sau modificarea fără acordul scris al autorilor. Platforma și toate funcționalitățile ei rămân în continuare proprietatea intelectuală Aspire Education Labs SRL. © 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Indicații oficiale de rezolvare a problemei

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

Lorem:

Pentru a vizualiza indicațiile problemei, te rugăm să te autentifici.

Indicații oficiale de rezolvare a problemei

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

Lorem:

Pentru a vizualiza rezolvarea problemei, te rugăm să te autentifici.

Soluții trimise la problema Asortat

Soluții trimise 48
Soluții de 100 de puncte 17
Soluții de luna aceasta La fel de multe ca luna trecută. 0 +0
Rata de succes Rata dintre numărul de persoane care au obținut 100 de puncte și numărul total de persoane care au încercat problema. 88.24%

Autentifică-te pentru a vedea soluțiile tale.

Autentifică-te
  • Toate soluțiile tale le găsești aici. Găsești toate detaliile evaluării mai târziu, precum punctaje și sfaturi primite.
  • Poți să editezi soluțiile tale și să le retrimiți. Reia mai târziu de unde ai rămas, pentru că poți modifica soluții și să le reevaluezi.
  • Profesorii pot să vadă soluțiile tale și să îți trimită sugestii. Astfel, îți este mai ușor să înveți informatica, primind sfaturi bune chiar de la școală.

Ultimele soluții trimise 48

100 10 1000000 1000 1000
1000 100000 100 10 10000000
10 10 10000000 1000000 10
10000000 100000 10000 1000 1000
10000 100000 10000000 1000000 10000
10000000 10 100 100000 1000
10000 100 1000000 10 100
10 100 10 1000000 1000
100000 100000 10 10000000 10
10000 1000000 1000 1000000 100000
Tabelul se actualizează în timp real. ?? / ??

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te