3768 - taieri

Cerința

Avem la dispoziție n bare metalice cu aceeași grosime, dar lungimi diferite. Putem alege oricare bară și să o tăiem, obținând alte două bare de lungimi mai mici. Ne dorim ca, folosind doar această operație (deci fără să le putem suda), să obținem un număr de bare de anumite lungimi date. Mai exact, dându-se un set de patru numere a, b, c, d, trebuie să decidem dacă putem obține a bare de lungime 1, b bare de lungime 2, c bare de lungime 4 și d bare de lungime 8. Odată aplicată o tăiere de lungime L asupra unei bare, restul poate fi în continuare folosit pentru a tăia alte bare de oricare dintre lungimile dorite. Cunoscând n – numărul de bare metalice și lungimile celor n bare metalice avute la dispoziție, pentru fiecare din seturile de patru numere a, b, c, d date, determinați dacă, pornind de la cele n lungimi date se pot obține barele de lungimile dorite.

Date de intrare

Fișierul de intrare taieri.in conține pe prima linie numărul natural n. Pe linia a doua se află cele n numere naturale ce reprezintă lungimile barelor inițiale. Pe linia a treia se află un număr natural m ce reprezintă numărul de seturi de patru numere. Pe fiecare din următoarele m linii se află câte patru numere naturale a, b, c, d cu semnificația de mai sus. Numerele de pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire taieri.out va conține m valori 0 și 1, separate prin câte un spațiu. Pentru fiecare set de patru numere, în ordinea apariției lor în fișierul de intrare, se scrie în fișierul de ieșire valoarea 1, dacă se poate obține numărul dorit de bare pentru toate cele patru lungimi din setul corespunzător, respectiv 0 în caz contrar. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• Lungimile barelor sunt numere naturale nenule cel mult egale cu 10.000.000.
• 0 ≤ a, b, c, d ≤ 10.000.000

Exemple

Exemplul 1

taieri.in

5

10 12 8 3 1

3

2 3 2 2

31 0 0 0

1 13 0 1

ecran

Datele sunt introduse corect.

taieri.out

1 1 0

Exemplul 2

taieri.in

5

12 17 25 9 6

3

10 1 1 1

30 2 2 2

40 2 2 2

ecran

Datele sunt introduse corect.

taieri.out

1 0 0

Exemplul 3

taieri.in

6

1 2 3 4 5

3

2 2 2 2

1 1 1 1

0 0 0 0

ecran

Datele nu corespund restricțiilor impuse.

taieri.out

Rezolvare

# 3768 - taieri
from typing import List, Tuple

import sys

def validare_input(n: int, v: List[int], m: int, intervale: List[Tuple[int, int, int, int]]) -> bool:
    if not(1 <= n <= 10**5) or not(1 <= m <= 10**5):
        print("Datele nu corespund restricțiilor impuse.")
        sys.exit(0)
    if len(v) != n:
        print("Datele nu corespund restricțiilor impuse.")
        sys.exit(0)
    for elem in v:
        if not(1 <= elem <= 10000000):
            print("Datele nu corespund restricțiilor impuse.")
            sys.exit(0)
    for interval in intervale:
        if not all(0 <= i <= 10000000 for i in interval):
            print("Datele nu corespund restricțiilor impuse.")
            sys.exit(0)
    print("Datele sunt introduse corect.")
    return True


def rezolva_problema(n: int, v: List[int], m: int, intervale: List[Tuple[int, int, int, int]]) -> List[int]:
    rezultate = []
    for a, b, c, d in intervale:
        l1, l2, l4, l8 = 0, 0, 0, 0
        for i in range(n):
            l8 += v[i] // 8
            v[i] %= 8
            if v[i]:
                l4 += v[i] // 4
                v[i] %= 4
                if v[i]:
                    l2 += v[i] // 2
                    v[i] %= 2
                if v[i]:
                    l1 += v[i]
        daux, caux, baux, aaux = l8, l4, l2, l1
        for i in range(n):
            l8 += v[i] // 8
            v[i] %= 8
            if v[i]:
                l4 += v[i] // 4
                v[i] %= 4
                if v[i]:
                    l2 += v[i] // 2
                    v[i] %= 2
                if v[i]:
                    l1 += v[i]
        ok = 1
        if d > daux:
            ok = 0
        else:
            caux += (daux-d) * 2
            if c > caux:
                ok = 0
            else:
                baux += (caux-c) * 2
                if b > baux:
                    ok = 0
                else:
                    aaux += (baux-b) * 2
                    if a > aaux:
                        ok = 0
        if ok:
            fout.write("1 ")
        else:
            fout.write("0 ")

    return rezultate
if __name__ == "__main__":
    with open("taieri.in", "r") as fin, open("taieri.out", "w") as fout:
        n = int(fin.readline().strip())
        v = list(map(int, fin.readline().split()))
        m = int(fin.readline().strip())
        intervale = [tuple(map(int, fin.readline().split())) for _ in range(m)]
        if validare_input(n, v, m, intervale):
            rezultate = rezolva_problema(n, v, m, intervale)
            fout.write(" ".join(str(x) for x in rezultate))
        else:
            fout.write("Date de intrare invalide")

Explicatie

validare_input(n: int, v: List[int], m: int, intervale: List[Tuple[int, int, int, int]]) -> bool Această funcție este folosită pentru a valida datele de intrare. Parametrii acestei funcții sunt:

n: numărul de elemente din lista v v: lista cu dimensiunile barelor m: numărul de intervale de verificat intervale: o listă de tupluri care conțin valorile a, b, c și d pentru fiecare interval. Această funcție verifică dacă datele de intrare respectă restricțiile impuse, inclusiv dacă dimensiunile barelor și intervalele se încadrează în limitele admise. Dacă datele de intrare sunt corecte, se returnează True. În caz contrar, se afișează un mesaj corespunzător și se returnează False.

rezolva_problema(n: int, v: List[int], m: int, intervale: List[Tuple[int, int, int, int]]) -> List[int] Această funcție rezolvă problema descrisă în enunțul exercițiului. Parametrii acestei funcții sunt aceiași ca și la funcția validare_input(). Funcția începe prin a calcula numărul de bare de fiecare dimensiune necesare pentru a acoperi lista de bare v. Apoi, pentru fiecare interval din lista intervale, funcția calculează numărul de bare necesare pentru a acoperi acel interval și verifică dacă aceste bare sunt disponibile în lista de bare v. Dacă toate barele necesare sunt disponibile, funcția adaugă 1 într-o listă de rezultate. În caz contrar, funcția adaugă 0 în lista de rezultate. La final, funcția returnează lista de rezultate.

main() Această funcție citește datele de intrare din fișier, validează datele folosind funcția validare_input() și, dacă datele sunt valide, apelează funcția rezolva_problema() și afișează rezultatele în fișierul de ieșire taieri.out.