1471 - maxdiv

Adrian este pasionat de matematică. El utilizează denumirea maxdiv pentru numărul care are cei mai mulţi divizori, dintre numerele unui şir dat. Adrian ştie că o secvenţă este un subşir de numere care apar pe poziţii consecutive într-un şir. El denumeşte secvenţă maxdiv o secvenţă din şir, formată din cel puţin două numere, ce începe şi se încheie cu un număr maxdiv şi nu conţine alte numere maxdiv în interior. Având la dispoziţie un şir de n numere naturale, doreşte să afişeze cea mai lungă secvenţă maxdiv şi numărul de secvenţe maxdiv din şir. Dacă şirul de numere dat conţine mai multe secvenţe maxdiv de aceeaşi lungime maximă, se va afişa prima secvenţă de acest tip din şir.

Cerința

Scrieţi un program care afişează, pentru un şir dat format din n numere naturale numărul de secvenţe maxdiv şi cea mai lungă secvenţă maxdiv.

Date de intrare

Fişierul de intrare maxdivin.txt conţine pe prima linie numărul n separat printr-un spaţiu de un număr natural t, care reprezintă cerinţa: 1, dacă se cere numărul de secvenţe maxdiv, respectiv 2 dacă se cere cea mai lungă secvenţă maxdiv. Linia a doua din fişier conţine cele n numere naturale ale şirului dat.

Date de ieșire

Fişierul de ieșire maxdivout.txt va conţine pe prima linie un număr natural ce reprezintă numărul de secvenţe maxdiv, pentru şirul de numere dat, dacă cerinţa este 1. Dacă cerinţa este 2, fişierul de ieşire va conţine un şir de numere naturale, separate între ele prin câte un spaţiu, ce reprezintă cea mai lungă secvenţă maxdiv din şirul dat.

Restricții și precizări

• 2 ≤ n ≤ 1000
• 2 ≤ x[i] ≤ 1.000.000, unde x[i] reprezintă un număr din şirul dat
• Şirul de numere conţine cel puţin o secvenţă care începe şi se încheie cu un număr maxdiv
• Pentru cerința 1 se acordă 40% din punctaj, iar pentru cerința 2 se acordă 60% din punctaj.

Exemplul 1

maxdivin.txt

7 1

22 60 64 125 315 24 150

maxdivout.txt

Datele introduse corespund restricțiilor impuse.

2

Explicație

Cerinţa 1: Şirul de numere dat conţine 3 numere maxdiv: 60, 315 şi 150 (au fiecare 12 divizori) și 2 secvenţe maxdiv : 60 64 125 315 şi 315 24 150.

Exemplul 2

maxdivin.txt

7 2

22 60 64 125 315 24 150

maxdiv.out

Datele introduse corespund restricțiilor impuse.

60 64 125 315

Explicație

Cerinţa 2: Şirul de numere dat conţine 2 secvenţe maxdiv: 60 64 125 315 şi 315 24 150. Cea mai lungă secvenţă este 60 64 125 315.

Exemplul 3

maxdivin.txt

7 2

22 60 64 125 315 24 15000000

maxdiv.out

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 1471 - maxdiv
def numar_divizori(n1):
    cnt = 0
    for i in range(1, int(n1 ** 0.5) + 1):
        if n1 % i == 0:
            if n1 / i == i:
                cnt += 1
            else:
                cnt += 2
    return cnt


def validare(nrs):
    if len(nrs) > 1000:
        raise ValueError
    for nr in nrs:
        if nr > 1000000:
            raise ValueError
    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def secvente_maxdiv(nrs, t1):
    maxdiv = max(nrs, key=numar_divizori)
    secvente = []
    secventa_curenta = []
    for nr in nrs:
        if nr == maxdiv:
            if secventa_curenta:
                secventa_curenta.append(nr)
                secvente.append(secventa_curenta)
            secventa_curenta = [nr]
        elif secventa_curenta:
            secventa_curenta.append(nr)
    if t1 == 1:
        fisier_iesire.write(str(len(secvente)))
    else:
        max_len = max(len(secventa) for secventa in secvente)
        for secventa in secvente:
            if len(secventa) == max_len:
                fisier_iesire.write(' '.join(map(str, secventa)))
                break


if __name__ == '__main__':
    fisier_intrare = open("maxdivin.txt", "r")
    fisier_iesire = open("maxdivout.txt", "w")

    try:
        n, t = map(int, fisier_intrare.readline().split())
        numere = list(map(int, fisier_intrare.readline().split()))

        validare(numere)
        secvente_maxdiv(numere, t)

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")