4137 - rgb

Ionuţ, tânăr programator, se lansează pe piaţa producătorilor de jocuri pe calculator. Jocul pe care l-a proiectat se numeşte RGB. În joc există N personaje extraterestre. Fiindcă Ionuţ nu este de acord cu teoria omuleţilor verzi, personajele lui sunt de trei culori:

• R extratereştri de culoare roşie;
• G extratereştri de culoare verde;
• B extratereştri de culoare albastră.

Fiecare extraterestru are o anumită putere, exprimată printr-un număr natural impar, puterile oricăror doi extratereştri fiind diferite. Pe parcursul jocului fiecare extraterestru va lupta cu fiecare dintre ceilalţi extratereştri. Rezultatul unei lupte între doi extratereştri depinde de puterea acestora, dar şi de culoarea lor. Într-o luptă dintre doi extratereştri de aceeaşi culoare, va câştiga cel cu puterea cea mai mare. Într-o luptă între doi extratereştri de culori diferite, puterile lor se modifică după cum urmează, iar după modificare lupta o va câştiga extraterestrul cu puterea mai mare:

• Puterea unui extraterestru roșu este dublată dacă adversarul este un extraterestru verde.
• Puterea unui extraterestru verde este dublată dacă adversarul este un extraterestru albastru.
• Puterea unui extraterestru albastru este dublată dacă adversarul este un extraterestru roșu.

După fiecare luptă, puterile extratereștrilor revin la valorile inițiale, în caz că s-au modificat.

Cerința

Scrieţi un program care, cunoscând culorile şi puterile extratereştrilor, rezolvă următoarele două cerinţe:

1) determină puterea extraterestrului care câştigă cele mai multe lupte; dacă există mai mulţi astfel de extratereştri, se va afişa puterea minimă;

2) determină pentru fiecare extraterestru numărul de lupte câştigate de acesta.

Date de intrare

Fișierul de intrare rgb.in conține pe prima linie numerele naturale C R G și B, unde C este cerinţa care trebuie să fie rezolvată (1 sau 2), R reprezintă numărul de extratereștri roșii, G numărul de extratereștri verzi, iar B numărul de extratereștri albaştri. Pe cea de a doua linie se află R numere naturale impare în ordine strict crescătoare, reprezentând puterile celor R extratereștri roșii. Pe cea de a treia linie se află G numere naturale impare în ordine strict crescătoare, reprezentând puterile celor G extratereștri verzi.

Pe cea de a patra linie se află B numere naturale impare în ordine strict crescătoare, reprezentând puterile celor B extratereștri albaştri. Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Pentru C = 1, fişierul de ieşire rgb.out va conţine o singură linie pe care va fi scrisă puterea extraterestrului care câştigă cele mai multe lupte; dacă există mai mulţi extratereştri care câştigă un număr maxim de lupte, se va afişa puterea minimă.Pentru C = 2, fişierul de ieşire rgb.out va conţine trei linii. Pe prima linie se va scrie numărul de lupte câştigate de fiecare extraterestru roșu. Pe a doua linie, se va scrie numărul de lupte câştigate de fiecare extraterestru verde. Pe a treia linie, se va scrie numărul de lupte câştigate de fiecare extraterestru albastru. Pentru fiecare culoare, valorile vor fi afişate considerând ordinea extratereştrilor din fişierul de intrare. Valorile scrise pe aceeaşi linie vor fi separate prin câte un spaţiu.

Restricții și precizări

• N = R + G + B, N ≤ 500.000
• 1 ≤ R, G, B ≤ N-2
• 1 ≤ puterea oricărui extraterestru ≤ 2 • N - 1
• Datorită dimensiunilor mari, unele teste nu au fost adăugate

Exemplul 1:

rgb.in

1 1 2 2
3
1 7
5 9

rgb.out

7

Explicație

C = 1, deci se va rezolva prima cerinţă. Există un extraterestru roşu, care are puterea 3, doi extratereştri verzi, având puterile 1, respectiv 7 şi doi extratereştri albaștri cu puterile 5, respectiv 9. Extraterestrul cu puterea 7 este singurul care va câştiga cele mai multe lupte (în cazul acesta, chiar toate):

• când luptă cu extraterestrul verde cu puterea 1 câştigă, pentru că are puterea mai mare;
• când luptă cu extraterestrul roşu cu puterea 3, acesta îşi va dubla puterea (va avea puterea 6), dar va fi insuficient pentru a câștiga lupta;
• când luptă contra extraterestrului albastru cu puterea 9, va avea puterea dublată (14), prin urmare va câştiga şi această luptă.

<syntaxhighlight lang="python" line="1"> def determine_winner_and_counts(N, colors, powers):

   # Initialize the win counts
   win_counts = [0] * N
   
   for i in range(N):
       for j in range(i + 1, N):
           power_i = powers[i]
           power_j = powers[j]
           
           # Adjust powers based on the colors
           if colors[i] == 'R' and colors[j] == 'G':
               power_i *= 2
           elif colors[i] == 'G' and colors[j] == 'R':
               power_j *= 2
           elif colors[i] == 'G' and colors[j] == 'B':
               power_i *= 2
           elif colors[i] == 'B' and colors[j] == 'G':
               power_j *= 2
           elif colors[i] == 'B' and colors[j] == 'R':
               power_i *= 2
           elif colors[i] == 'R' and colors[j] == 'B':
               power_j *= 2
           
           # Determine winner
           if power_i > power_j:
               win_counts[i] += 1
           else:
               win_counts[j] += 1
   
   # Determine the extraterrestrial with the most wins
   max_wins = max(win_counts)
   winners = [powers[i] for i in range(N) if win_counts[i] == max_wins]
   min_power_winner = min(winners)
   
   return min_power_winner, win_counts

1. Exemplu de utilizare

N = 5 colors = ['R', 'G', 'B', 'R', 'G'] powers = [5, 3, 7, 9, 1]

min_power_winner, win_counts = determine_winner_and_counts(N, colors, powers) print("Puterea extraterestrului cu cele mai multe lupte câștigate:", min_power_winner) print("Numărul de lupte câștigate de fiecare extraterestru:", win_counts) </syntaxhighlight>