InfoAs Atlas

<- Go back View preview

Problema Parola

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

Iulian este foarte speriat de hoți și îl terifiază gândul că peste câteva zile, de Crăciun, Moș Crăciun va intra prin efracție în casa lui. Din acest motiv, acesta și-a instalat pe ușă un sistem care funcționează cu un cod PIN. Fricos de fel, se întreabă cât de sigur este sistemul de securitate. 
 
Codul este format din `n` numere naturale care trebuie să fie distincte două câte două. Primul număr poate fi orice număr de la `1` la `a1`, al doilea număr poate fi orice de la `1` la `a2` și așa mai departe până la al `n`-lea număr (numerele `a1`, `a2`, …, `an` nu sunt neapărat în ordine crescătoare).

## Cerință

Se dau `n` și cele `n` numere `a1`, `a2`, …, `an`. Să se determine câte coduri există care să respecte condițiile impuse de codul PIN, pentru a-l ajuta pe Iulian.
## Date de intrare

Programul citește de la tastatură, de pe prima linie, numărul natural `n`, iar de pe următoarea linie, cele `n` numere naturale separate prin câte un spațiu.
## Date de ieșire

Programul afișează pe ecran un singur număr natural reprezentând numărul de coduri care se pot forma în condițiile date. Deoarece acest număr poate fi foarte mare, se cere afișarea răspunsului `modulo 1.000.000.007`.
## Restricții și precizări

* `1 ≤ n ≤ 100.000`
  * `1 ≤ cele n numere ≤ 1.000.000.000`

Examples

[{"input": "3\n1 2 3", "output": "1", "explanation": "Pentru primul exemplu: singurul cod valid este <code>(1, 2, 3)</code>, deoarece primul num\u0103r poate fi doar <code>1</code>, al doilea poate fi doar <code>2</code> (pentru c\u0103 trebuie s\u0103 difere de primul num\u0103r), iar al treilea num\u0103r poate fi doar <code>3</code> (ca s\u0103 difere de celelalte dou\u0103 numere). \r\nPentru al doilea exemplu: singurele dou\u0103 coduri care respect\u0103 condi\u021biile date sunt <code>(1, 3, 2)</code> \u0219i <code>(2, 3, 1)</code>."}, {"input": "3\n2 3 2", "output": "2", "explanation": "Pentru primul exemplu: singurul cod valid este <code>(1, 2, 3)</code>, deoarece primul num\u0103r poate fi doar <code>1</code>, al doilea poate fi doar <code>2</code> (pentru c\u0103 trebuie s\u0103 difere de primul num\u0103r), iar al treilea num\u0103r poate fi doar <code>3</code> (ca s\u0103 difere de celelalte dou\u0103 numere). \r\nPentru al doilea exemplu: singurele dou\u0103 coduri care respect\u0103 condi\u021biile date sunt <code>(1, 3, 2)</code> \u0219i <code>(2, 3, 1)</code>."}]

Default code

Summary

Editorial

Să analizăm un exemplu pentru a ne putea da seama cum s-ar putea rezolva problema. Să zicem că numerele sunt `(2, 3, 2)` (al doilea exemplu). Dacă primul număr este `1`, atunci al treilea număr trebuie neapărat să fie `2`, deoarece nu există vreo altă alternativă. Implicit, al doilea număr trebuie să fie `3` în acest caz. Așadar, `(1, 3, 2)` este o soluție. Similar și `(2, 3, 1)` este o soluție.

Observăm că cel mai ușor ar fi să luăm cumva numerele în ordine crescătoare (în exemplul anterior, înainte să procesăm ce valori poate avea al doilea număr cu valoarea maximă `3`, am văzut ce valori poate avea primul și al treilea număr cu valoarea maximă `2`). Așadar, dacă luăm numerele în ordine crescătoare:

* ne asigurăm că putem determina corect toate valorile pe care le pot lua numerele din șir;
  * nu ne încurcă faptul că nu luăm numerele în ordinea dată, deoarece vor fi același număr de soluții.

Prin urmare, începem prin a sorta șirul (folosind funcția `sort()` din biblioteca `<algorithm>`, pentru viteză). Mai apoi, numărăm câte valori poate avea fiecare număr în parte în șirul sortat: primul număr poate avea orice valoare de la `1` la `a1`; al doilea număr poate avea orice valoare de la `1` la `a2`, minus `1` (primul număr ales, care se află între `1` și `a1`, adică implicit între `1` și `a2`, pentru că `a1 ≤ a2`); al treilea număr poate avea orice valoare de la `1` la `a3`, minus `2`; și așa mai departe.

Înmulțind aceste numere, observăm că rezultatul este `(a1 - 0) * (a2 - 1) * (a3 - 2) * … * (an - n + 1) modulo 1.000.000.007`.

Calculăm acest număr cu `modulo` și având grijă ca nicio înmulțire să iasă din tipul de date ales (se recomandă operații cu `long long` pentru a evita ieșirea din tipurile de date). Numărul se afișează pe ecran.

**Observație.** Dacă vreunul dintre numere `ai - (i - 1)` este negativ sau `0`, atunci rezultatul este `0`, pentru că nu există nicio combinație de numere care să respecte parola. Un exemplu ar fi șirul `(1, 1, 1, 1)`, unde nu există nicio combinație validă, deoarece numerele trebuie să fie distincte, dar toate trebuie să aibă valoarea `1` (caz imposibil): aici, avem produsul `1 * 0 * (-1) * (-2)`, cu numere negative (și `0`), caz care nu merge.

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-parola.in	/ 100	10 January 2025 21:26	7 B	View
0-parola.ok	/ 100	10 January 2025 21:26	1 B	View
1-parola.in	/ 100	10 January 2025 21:26	7 B	View
1-parola.ok	/ 100	10 January 2025 21:26	1 B	View
2-parola.in	/ 100	10 January 2025 21:26	389 B	View
2-parola.ok	/ 100	10 January 2025 21:26	9 B	View
3-parola.in	/ 100	10 January 2025 21:26	5 KB	View
3-parola.ok	/ 100	10 January 2025 21:26	9 B	View
4-parola.in	/ 100	10 January 2025 21:26	106 KB	View
4-parola.ok	/ 100	10 January 2025 21:26	1 B	View
5-parola.in	/ 100	10 January 2025 21:26	321 KB	View
5-parola.ok	/ 100	10 January 2025 21:26	9 B	View
6-parola.in	/ 100	10 January 2025 21:26	781 KB	View
6-parola.ok	/ 100	10 January 2025 21:26	9 B	View
7-parola.in	/ 100	10 January 2025 21:26	65 KB	View
7-parola.ok	/ 100	10 January 2025 21:26	1 B	View
8-parola.in	/ 100	10 January 2025 21:26	770 KB	View
8-parola.ok	/ 100	10 January 2025 21:26	9 B	View
9-parola.in	/ 100	10 January 2025 21:26	965 KB	View
9-parola.ok	/ 100	10 January 2025 21:26	9 B	View
In total: 22 files 2 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 Parola

Identification properties

Content properties

Technical properties

Delete all files