1394 - Devt
De la Universitas MediaWiki
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
- devtin.txt
- 25 5
- 3 7
- 12 20
- 3 4
- 16 24
- 12 24
- devtout.txt
- 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
#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):
with open("devtout.txt", "w") as file_out:
file_out.write("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()