2445 - Turnuri 1

Într-un laborator cibernetic se fac experimente cu roboţi. Pe o bandă de lucru se află aşezate unul lângă altul, N cuburi galbene şi albastre, numeroate în ordine cu valori de la 1 la N. Pentru fiecare cub se cunoaşte latura acestuia, exprimată în centimetri, şi culoarea, codificată prin simbolul g (pentru galben) sau a (pentru albastru). Un robot inteligent este programat să construiască turnuri prin aşezarea cuburilor unul peste altul. El se află în faţa benzii de lucru, analizează fiecare cub în ordine, de la primul la ultimul, şi procedează astfel :

• dacă este primul cub, îl lasă la locul lui pe bandă;
• aşează cubul numerotat cu K peste cubul numerotat cu K-1 doar dacă el are culoarea diferită şi latura mai mică decât cubul K-1. Această operaţie se efectuează în cazul în care cubul K-1 se află deja într-un turn constuit anterior sau dacă el a rămas în poziția inițială. În cazul în care cubul K nu poate fi aşezat peste cubul K-1, el rămâne la locul lui.

Cerința

Ştiind că un turn poate fi format din cel puţin un cub, scrieţi un program care să determine:

1. numărul final T al turnurilor de pe bandă şi H, înălţimea celui mai înalt turn care se poate forma, exprimată în centimetri;

2. cel mai mare număr de cuburi Nmax ce pot forma un turn, dacă cele N cuburi ar putea fi rearanjate inițial pe bandă, unul lângă altul.

Date de intrare

Fişierul turnuri1.in conţine:

- pe prima linie un număr natural C care reprezintă numărul cerinţei şi poate fi 1 sau 2.

- pe cea de-a doua linie un număr natural N ce reprezintă numărul cuburilor de pe bandă;

- pe fiecare dintre următoarele N linii, câte un număr natural care reprezintă latura unui cub, urmat de un spaţiu şi simbolul g sau a, pentru codificarea culorii cubului.

Date de ieșire

Fișierul de ieșire turnuri1.out va conţine pentru cerința 1 (C=1) pe prima linie două valori, separate printr-un spațiu, ce reprezintă T și H. Pentru cerința 2 (C=2) fișierul va conține pe prima linie numărul Nmax.

Restricții și precizări

• 1 ≤ N ≤ 10 000 şi 1≤ latura unui cub ≤ 500 000;
• nu există două cuburi cu laturi egale;
• Pentru rezolvarea corectă a primei cerințe se acordă 30 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.
• În concurs s-au acordat 10 din oficiu. Aici se acordă 10 puncte pentru exemplele din enunț.

Exemplul 1:

turnuri1.in

1
6
18 a
13 g
15 a
10 a
8 g
2 a

turnuri1.out

3 31

Încărcare soluție

Lipește codul aici

# Framework and technology stack: C++ with standard library
import sys
from typing import List

fin = open("turnuri1.in", "r")
fout = open("turnuri1.out", "w")
C: int
n: int
n1: int
n2: int
nr_turnuri: int
max_turn: int
v1: List[int] = [0] * 10003
v2: List[int] = [0] * 10003
v3: int

def citire() -> None:
    global C, n, n1, n2, nr_turnuri, max_turn
    l1: int
    l2: int
    h_turn: int
    cul1: str
    cul2: str

    data = fin.readline().split()
    C = int(data[0])
    n = int(data[1])

    data = fin.readline().split()
    l1 = int(data[0])
    cul1 = data[1]
    nr_turnuri = 1
    h_turn = l1
    if cul1 == 'g':
        n1 += 1
        v1[n1] = l1
    else:
        n2 += 1
        v2[n2] = l1

    for i in range(n - 1):
        data = fin.readline().split()
        l2 = int(data[0])
        cul2 = data[1]

        if l2 < l1 and cul2 != cul1:
            h_turn += l2
        else:
            nr_turnuri += 1
            h_turn = l2
        if h_turn > max_turn:
            max_turn = h_turn
        l1 = l2
        cul1 = cul2

def cmp(a: int, b: int) -> bool:
    return a > b

def main() -> None:
    global n1, n2, v1, v2
    i: int
    j: int
    k: int
    p: int
    citire()
    if C == 1:
        fout.write(str(nr_turnuri) + ' ' + str(max_turn) + '\n')
    else:
        v1 = sorted(v1[1:n1 + 1], reverse=True)
        v2 = sorted(v2[1:n2 + 1], reverse=True)
        v1.append(500003)
        v2.append(500002)
        i = 1
        j = 1
        k = 0
        if v1[i] > v2[j]:
            k += 1
            v3 = v1[i]
            i += 1
            p = 1
        else:
            k += 1
            v3 = v2[j]
            j += 1
            p = -1
        while i <= n1 and j <= n2:
            if p == 1:
                while j <= n2 and v2[j] >= v3:
                    j += 1
                if j <= n2:
                    k += 1
                    v3 = v2[j]
                    j += 1
                    p = -p
            else:
                while i <= n1 and v1[i] >= v3:
                    i += 1
                if i <= n1:
                    k += 1
                    v3 = v1[i]
                    i += 1
                    p = -p
        if p == -1:
            for i in range(i, n1 + 1):
                if v1[i] < v3:
                    k += 1
                    v3 = v1[i]
                    break
        if p == 1:
            for j in range(j, n2 + 1):
                if v2[j] < v3:
                    k += 1
                    v3 = v2[j]
                    break
        fout.write(str(k) + '\n')

    fin.close()
    fout.close()

if __name__ == "__main__":
    main()