0031-jogo-varetas

id: 0031 name: Jogo das Varetas slug: jogo-das-varetas idBeecrowd: 1318 authorSlugProblem: beecrowd origin: Beecrowd 1318 (Varetas) description: | A princesa está entediada e pede para o Bob criar um jogo. Bob propõe um jogo com varetas de diferentes comprimentos. A princesa deve escolher duas varetas para formar um par. Se as varetas tiverem o mesmo comprimento, elas formam um par válido e são removidas. O objetivo é formar o maior número possível de pares. editorial: | A chave para resolver este problema é entender que a ordem das varetas não importa. O que importa é a contagem de cada comprimento de vareta. Para maximizar o número de pares, para cada comprimento de vareta, se houver um número par de varetas desse comprimento, todos elas formam pares. Se houver um número ímpar, (N-1) varetas formam pares, e uma sobra. Portanto, podemos usar um mapa de frequência ou um array (se os comprimentos forem limitados) para contar a ocorrência de cada comprimento. Para cada comprimento, o número de pares que podem ser formados é `count / 2` (divisão inteira). A soma de `count / 2` para todos os comprimentos nos dará o número total de pares. timeComplexity: O(N) timeLimitSegs: 1 memoryLimitMb: 256 defaultStatement: | Dada uma lista de N varetas, cada uma com um comprimento. Determine o número máximo de pares de varetas que podem ser formados, onde um par consiste em duas varetas de mesmo comprimento. skills: - array - map - counting statements: - id: pt-br statement: | Dada uma lista de N varetas, cada uma com um comprimento. Determine o número máximo de pares de varetas que podem ser formados, onde um par consiste em duas varetas de mesmo comprimento. - id: en-us statement: | Given a list of N sticks, each with a length. Determine the maximum number of pairs of sticks that can be formed, where a pair consists of two sticks of the same length. solutions: - id: cpp language: C++ code: | #include <iostream> #include <map> int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; while (std::cin >> N && N != 0) { std::map<int, int> counts; for (int i = 0; i < N; ++i) { int L, C; std::cin >> L >> C; // L is length, C is number of sticks of that length counts[L] += C; } int total_pairs = 0; for (auto const& [length, count] : counts) { total_pairs += count / 2; } std::cout << total_pairs << "\n"; } return 0; } - id: python language: Python code: | while True: N = int(input()) if N == 0: break counts = {} for _ in range(N): L, C = map(int, input().split()) counts[L] = counts.get(L, 0) + C total_pairs = 0 for length, count in counts.items(): total_pairs += count // 2 print(total_pairs) testScenarios: - id: exemplo-1 input: | 3 10 2 20 3 30 4 0 output: | 4 description: | Para varetas de comprimento 10, temos 2. Formamos 1 par. Para varetas de comprimento 20, temos 3. Formamos 1 par e sobra 1. Para varetas de comprimento 30, temos 4. Formamos 2 pares. Total = 1 + 1 + 2 = 4 pares. - id: exemplo-2 input: | 2 5 1 5 1 0 output: | 1 description: | Duas varetas de comprimento 5. Formamos 1 par. thematicSkills: - math - data-structures