Editing 1394 - Devt

== 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 &les; a &les; b &les; n &les; 100000'''
*'''1 &les; k &les; 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.
<br>
== Exemplu 2 ==
;'''devtin.txt'''
:0 2
:-1 2
:-4 -2
;'''devtout.txt'''
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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()
</syntaxhighlight>