3860 - consecutive1

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

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>