AjM: Pagină nouă: == Enunt == Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive). == Cerinţa == Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se o...

2024-06-03T16:40:02Z

Pagină nouă: == Enunt == Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive). == Cerinţa == Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se o...

New page

== Enunt ==
Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive).
== Cerinţa ==
Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se obține o secvență de numere consecutive veți afișa valoarea 1, iar în caz contrar veți afișa valoarea 0.
== Date de intrare ==
De la tastatură, de pe prima linie se citește numărul natural n. Pe linia a doua se află n numere naturale reprezentând elementele șirului. Pe a treia linie se află numărul Q, iar pe următoarele Q linii se găsesc câte două numere naturale x și y, 1 ≤ x ≤ y ≤ n, reprezentând câte o interogare.
== Date de ieșire ==
La ecran se vor afișa pe o singură linie, fără spații, Q cifre din mulțimea {0, 1} reprezentând răspunsurile la fiecare întrebare.
== Restricţii şi precizări ==
* Pentru 10 puncte, 3 ≤ n ≤ 50, 1 ≤ Q ≤ 100
* Pentru 30 puncte, n ≤ 300, Q ≤ 10.000
* Pentru 60 puncte, 10.000 ≤ n ≤ 100.000, Q ≤ 200.000
== Exemplu ==
; Intrare
9
4 1 3 4 2 1 6 5 4
5
1 4
3 5
3 6
5 9
7 9
; Ieșire
01101
<br>

== Explicație ==
Sunt 5 interogări.
Întrebarea 1: 4 1 3 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 2: 3 4 2 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 3: 3 4 2 1 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 4: 2 1 6 5 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 5: 6 5 4 obține o secvență de numere consecutive, deci răspunsul este 1.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_form_consecutive_sequence(arr, x, y):
sorted_arr = sorted(arr[x-1:y])
for i in range(1, len(sorted_arr)):
if sorted_arr[i] != sorted_arr[i-1] + 1:
return False
return True

def main():
n = int(input())
arr = list(map(int, input().split()))
Q = int(input())

result = ""
for _ in range(Q):
x, y = map(int, input().split())
result += "1" if can_form_consecutive_sequence(arr, x, y) else "0"

print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3860 - consecutive1 - Revision history