1394 - Devt: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == Enunt == Într-o zi, Gigel a găsit pe masa tatălui său o foaie A4 pe care era trecut șirul denumit “devt” sub forma 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, ... , n. Dedesubtul acestui șir găsește un text alcătuit din k întrebări de forma a, b cu semnificația “Câte numere din acest șir se află în intervalul [a,b]?”. == Cerința == Ajutați-l pe Gigel să răspundă corect la toate cele k întrebări. == Date de intrare == Fișierul...
 
Line 9: Line 9:
== Restricții și precizări ==
== Restricții și precizări ==
*0 ⩽ a ⩽ b ⩽ n ⩽ 100000
*0 ⩽ a ⩽ b ⩽ n ⩽ 100000
*1 &les k ⩽ 5000
*1 ⩽ k ⩽ 5000
*n aparține șirului devt
*n aparține șirului devt
== Exemplu 1 ==
== Exemplu 1 ==
;devt.in
;devt.in

Revision as of 17:19, 12 December 2023

Enunt

Într-o zi, Gigel a găsit pe masa tatălui său o foaie A4 pe care era trecut șirul denumit “devt” sub forma 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, ... , n. Dedesubtul acestui șir găsește un text alcătuit din k întrebări de forma a, b cu semnificația “Câte numere din acest șir se află în intervalul [a,b]?”.

Cerința

Ajutați-l pe Gigel să răspundă corect la toate cele k întrebări.

Date de intrare

Fișierul de intrare devtin.txt conține pe prima linie numerele naturale n și k, iar pe următoarele k linii numerele a, b cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire devtout.txt va conține k linii, pe fiecare linie i aflându-se un număr natural, reprezentând răspunsul întrebării i.

Restricții și precizări

  • 0 ⩽ a ⩽ b ⩽ n ⩽ 100000
  • 1 ⩽ k ⩽ 5000
  • n aparține șirului devt

Exemplu 1

devt.in
25 5
3 7
12 20
3 4
16 24
12 24
devt.out
2
6
1
6
9
Explicație
În intervalul [3,7] se află 2 numere din șir.
În intervalul [12,20] se află 6 numere din șir.
În intervalul [3,4] se află 1 număr din șir.
În intervalul [16,24] se află 6 numere din șir.
În intervalul [12,24] se află 9 numere din șir.


Exemplu 2

devtin.txt
0 2
-1 2
-4 -2
devtout.txt
Nu au fost respectate cerintele impuse


Rezolvare

<syntaxhighlight lang="python" line>

  1. 1394 - Devt

def is_valid_input(n, k, intervals):

   if not (0 <= k <= 5000):
       return False
   if not (1 <= n <= 100000):
       return False
   for a, b in intervals:
       if not (0 <= a <= b <= n):
           return False
   return True

def count_numbers_in_interval(a, b, sequence):

   count = 0
   for num in sequence:
       if a <= num <= b:
           count += 1
   return count

def main():

   # Citirea datelor de intrare
   with open("devtin.txt", "r") as file:
       n, k = map(int, file.readline().split())
       intervals = [list(map(int, file.readline().split())) for _ in range(k)]
   # Verificare restricții
   if not is_valid_input(n, k, intervals):
       print("Nu au fost respectate cerintele impuse")
       return
   # Calculul răspunsurilor
   answers = []
   sequence = [1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25]  # Acesta este șirul "devt"
   for interval in intervals:
       a, b = interval
       result = count_numbers_in_interval(a, b, sequence)
       answers.append(result)
   # Scrierea rezultatelor în fișierul de ieșire
   with open("devtout.txt", "w") as file:
       for answer in answers:
           file.write(str(answer) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>