Lista de EDA no beecrowd

Prévia do material em texto

beecrow 1195 Árvore Binária de Busca Por Neilor Tonin, URI Brasil Timelimit: 1 Em computação, a árvores binária de busca ou árvore de pesquisa é uma estrutura baseada em nós (nodos), onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (e assim sucessivamente). o objetivo desta é estruturar os dados de forma flexível, permitindo a busca de um elemento qualquer da A grande vantagem das árvores de busca binária sobre estruturas de dados convencionais é que os algoritmos de ordenação (percurso infixo) e pesquisa que as utilizam são muito eficientes. Para este problema, você receberá vários conjuntos de números e a partir de cada um dos conjuntos, deverá construir uma árvore de busca. Por exemplo, a sequência de valores: 8 10 1 resulta na seguinte binária de busca: 8 3 10 1 6 14 4 7 13 Entrada A entrada contém vários casos de teste. A primeira linha da entrada contém um inteiro C 1000), indicando número de casos de teste que virão a seguir. Cada caso de teste é composto por 2 linhas. A primeira linha contém um inteiro N (1 que indica a quantidade de números que deve compor cada árvore e a segunda linha contém N inteiros distintos e não negativos, separados por um espaço em branco. Saída Cada linha de entrada produz 3 linhas de saída. Após construir a árvore binária de busca com os elementos de entrada, você deverá imprimir a mensagem "Case onde n indica número do caso de teste e fazer os três percursos da árvore: prefixo, infixo e posfixo, apresentando cada um deles em uma linha com uma mensagem correspondente conforme exemplo abaixo, separando cada um dos elementos por um espaço em branco. Obs: Não deve haver espaço em branco após último item de cada linha e há uma linha em branco após cada caso de teste, inclusive após último. Exemplo de Entrada Exemplo de Saída 2 Case 1: 3 Pre 7 5 7 In. 7 9 Post: 5 8 3 14 6 4 13 7 1 Case 2: 14 Post: 7 6 3 13 14 10 8 *Primeiro Dicionário de Andy Autor Desconhecido Timelimit: 1 Andy de apenas 8 anos tem um sonho ele deseja criar seu próprio dicionário. Isto não é uma tarefa fácil para ele, pois conhece poucas palavras. Bem, ao invés de pensar nas palavras que sabe, ele teve uma idéia A partir do seu livro de histórias favorito, ele vai criar um dicionário com todas as palavras distintas que existem nele. Ordenando estas palavras em ordem alfabética, trabalho estará feito. É claro, isso é uma tarefa que toma um certo tempo e portanto, a ajuda de um programador de computador como você é muito Você foi convidado a escrever um programa que liste todas as diferentes palavras que existem em um texto. Neste caso, uma palavra é definida como uma de letras, maiúsculas ou Palavras com apenas uma letra também deverão ser consideradas. Portanto, seu programa deverá ser "CaSe Por exemplo, palavras como "Apple", "apple" ou deverão ser consideradas como a mesma palavra. Entrada A entrada contém no máximo 10000 linhas de texto, cada uma delas com no máximo 200 caracteres. o fim de entrada é determinado pelo EOF. Saída Você deve imprimir uma lista de diferentes palavras que aparecem no texto, uma palavra por linha. Todas as palavras devem ser impressas com letras em ordem alfabética. Deverá haver no máximo 5000 palavras distintas. Exemplo de Entrada Exemplo de Saída Ex a adventures Adventures in Disneyland blondes came Two blondes were going to Disneyland when they came to a fork in the road. The sign read: "Disneyland LEFT." disneyland e So they went home ex fork going home in left mpl read road sign the they to two went were whenbeecrowd 1252 Sort! Sort!! e Sort!!! Por Shahrian Bangladesh Timelimit: 2 Hmm! Aqui você foi solicitado a fazer uma simples ordenação. A você serão dado N números e um inteiro positivo M. Você terá que ordenar estes N números em ordem ascendente de seu módulo M. Se houver um empate entre um número e um número par (para os quais seu módulo M dá mesmo valor) então número impar irá preceder número par. Se houver um empate entre dois números impares (para os quais O seu módulo M dá mesmo valor), então maior número impar irá preceder menor número impar. Se houve um empate entre dois números pares (para os quais seu módulo M dá mesmo valor), então menor número par irá preceder maior número par. Para resto de valores negativos siga regra de linguagem de programação número negativo nunca pode ter módulo maior do que zero. Por exemplo, -100 MOD 3 -1,-100 MOD 4 0, etc. Entrada A entrada contém vários casos de teste. Cada caso de teste inicia com dois inteiros N (0beecrowd 1256 Tabelas Hash Por Tonin, URI Brasil Timelimit: 1 m conhecidas como tabelas de dispersão, armazenam elementos com base no valor absoluto de suas chaves e em técnicas de tratamento de colisões. Para cálculo do endereço onde deve ser armazenada uma determinada chave, utiliza-se uma função denominada função de ma a chave em um dos endereços disponíveis na tabela. ação utilize uma tabela de dispersão com 13 endereços-base (índices de 0 a 12) e empregue a função de dispersão h(x) = x mod 13, em que representa a chave do elemento cujo endereço-base deve ser calculado. 49, a função de dispersão retornará o valor 10, indicando o local onde esta chave deverá ser armazenada. Se a mesma aplicação considerar a inserção da chave 88, o cálculo retornará mesmo valor 10, ocorrendo neste caso uma colisão. o Tratamento de colisões serve para casos onde mais de uma chave é mapeada para um mesmo endereço-base da tabela. Este tratamento pode considerar, ou recálculo do endereço da chave ou encadeamento externo ou exterior. que você o auxiliasse com um programa que calcula endereço para inserções de diversas chaves em algumas tabelas, com funções de dispersão e tratamento de colisão por encadeamento exterior. casos de teste. A primeira linha de entrada contém um inteiro N indicando a quantidade de casos de teste. Cada caso de teste é composto por duas linhas. A primeira linha contém um valor M (1 100) que indica a quantidade de endereços-base na tabela (normalmente uido por um espaço e um valor C (1 200) que indica a quantidade de chaves a serem A segunda linha contém cada uma das chaves (com valor entre 1 e 200), separadas por um espaço em branco. ressa conforme os exemplos fornecidos abaixo, onde a quantidade de linhas de cada caso de teste é determinada pelo valor de M. Uma linha em branco deverá separar dois conjuntos de Exemplo de Entrada Exemplo de Saída 92 97 95 2 3 88 86 4 -> 95 5 -> 44 -> 70 7 9 11 1 -> \ 2 *beecrowd 1257 Array Hash Por EUA Timelimit: Você terá como uma entrada linhas cada uma com uma string valor de cada caracter é computado como segue: Valor (Posição no alfabeto) (Elemento de entrada) (Posição do elemento) Todas posições são baseadas em 'A' tem posição no 'B' posição no de hash retornado soma de todos os caracteres da Por exemplo se entrada for: CBA DDD então cada caractere deverá ser computado como 2 + 0 'C' no elemento 0 posição 'B' no elemento posição 1 no elemento posição 2 + 1 'D' no elemento posição 0 'D' no elemento posição 1 6 'D' no elemento 1 posição 2 cálculo final de hash será 2+2+2+4+5+6 21. Entrada A entrada contém vários casos de teste A primeira linha de entrada contém um inteiro N que indica quantidade de casos de teste Cada caso de teste inicia com um inteiro que indica quantidade de linhas que vem seguir Cada uma destas linhas contém uma string com até 50 maiúsculas Saída Para cada caso de teste imprima valor de hash que calculado conforme exemplo apresentado acima Exemplo Entrada Saída 5 21 2 25 CBA 30 DDD 4290 295 A * E F Saída Para cada caso de teste imprima valor de hash que é calculado conforme exemplo apresentado Exemplo Entrada Exemplo 5 21 25 CBA 30 DDD 4290 1 295 6 1 ZZZZZZZZZZ TooCode * problema TopCoderbeecrowd 1282 Organizando Pacotes Por Ray Williams Robinson Valiente E Cuba Timelimit: 3 Uma empresa de mineração extrai um metal raro usado para construção de partir de areia de rio. Eles mineram um grande rio em pontos de mineração cada um deles identificado por sua distância partir da origem do rio. Em cada ponto de uma pequena pilha ou amontoado de minério mineral altamente valorizado extraido do rio. Para recolher minério mineral empresa reagrupa os N amontoados produzidos em um menor de pilhas ou montes cada um localizado num dos pontos de extração inicial Os montes são então recolhidos por Para reagrupar os N montes eles usam uma barca que na pode levar qualquer quantidade de minério mineral por ser bem barcaca começa na origem do rio somente pode viajar rio de modo que amontoado de mineral produzido em um ponto de mineração pode ser levado para um ponto de mineração somente se Cada monte movimentado completamente para outro ponto de mineração, ou não se move custo de um monte com peso W partir de um ponto de mineração para um ponto Y de mineração custo total do agrupamento soma dos custos de cada movimento de um Nota-se que um monte que não movido não tem influência sobre custo total Dados os valores de os de peso da pilha ou amontoado produzido de cada ponto de mineração, escreva um programa que calcule custo total mínimo para reagr upar estes N montinho iniciais em pilhas ou montes Entrada Cada caso de teste descrito usando varias linhas A primeira linha contém dois inteiros quais denotam espectivamente, de montes ou pilhas iniciais numero desejado de montes após reagrupamento (1 1000). Cada uma das seguintes N linhas descrevem um dos montes iniciais com dois inteiros indicando que ponto de mineração produziu um amontoado com peso de 106) Dentro de cada caso de teste, os montes ou pilhas são dados estritamente em ordem ascendente, considerando os seus pontos de Saída Para cada caso teste de saída terá uma linha com um inteiro representando mínimo custo total para reagrupar os N amontoados iniciais em K montes maiores Exemplo Entrada Exemplo 30 20 1 30 1 278 40 1 86 3 1 11 3 12 2 13 1 6 2 10 15 12 17 16 18 18 13 30 10 32 1 6 3 10 15 12 17 16 18 Saída Para cada caso teste de saída uma linha com um inteiro representando mínimo custo para reagrupar os N amontoados iniciais em K montes Exemplo Entrada Exemplo 30 20 1 8 30 1 278 40 1 86 11 3 12 2 13 1 6 2 10 15 12 17 16 18 18 13 30 10 32 1 6 3 10 15 12 17 16 18 18 13 30 10 32 1 Americabeecrowd 1675 Construção de Procura Binária de Heap Contest Local, Universidade de Ulm Alemanha Timelimit: 2 Leia enunciado do problema G para as definições sobre heaps. A seguir nós definimos a terminologia básica de heaps. Uma heap é uma árvore cujos nós internos tem, cada um, uma prioridade (definida por um número) sendo que a prioridade de cada nó interno é menor que a prioridade de seu pai. Como consequência, a rais será o nó de maior prioridade da Isso é uma das razões pelas quais heaps podem comumente ser usadas para a implemantação de filas de prioridade e para ordenações. Uma árvore binária na qual cada nó interno tem ambos um rótulo e uma prioridade, e é tanto uma arvore binária de busca com atenção para rótulos; quanto uma fila com atenção para prioridades, é chamada de treap(árvore-heap). A sua tarefa é: Dado um conjunto de pares de rótulos e prioridades, com rótulos únicos e prioridades construir uma treap com essas informações. Entrada A entrada contém vários casos de teste. Cada caso de teste começa com um inteiro n. Você pode assumir que n 50000. Então segue n pares de strings e números As strings são não-nulas e em caixa-baixa, e os números são inteiros não-negativos. o último caso de teste é seguido por um zero. Saída Cada linha de cada caso de teste deve conter uma treap com os nós especificados. Uma treap é impressa como () As sub-treaps são impressas recursivamente e omitidas se forem Exemplo de Entrada Exemplo de Saída 7 a/7 b/6 c/5 d/4 e/3 f/2 g/1 7 a/1 b/2 c/3 d/4 e/5 g/7 7 a/3 b/6 c/ 4 d/7 e/2 f/5 g/1 0 of Contest 2004/2005beecrowd 1851 Como Treinar Seu Dragão Por Leandro Zatesko, UFFS Brazil Timelimit: 1 Após seu dragão Smaug fracassar na missão de tomar conta de Erebor, Sauron ficou muito aborrecido, e seu Olho começou a procurar por toda parte um treinador de dragões profissional, a fim de que seus demais dragões não falhassem em suas missões. Foi assim que Sauron conheceu Daenerys Targaryen. Impressionado com a reputação dela, Sauron a contratou imediatamente. Sauron envia dragões a Daenerys quase diariamente. Alguns dragões levam mais tempo para serem treinados, outros menos, e ela sempre treina um dragão de cada vez, nunca mais de um no mesmo dia, até que ele esteja pronto para ser retornado a Sauron. Nos dias em que se dedica ao treinamento de um dragão, Daenerys deixa os demais dragões enviados por Sauron hibernando num alojamento até que chegue a vez de cada um deles. Mas o caráter de Sauron, embora de notável perseverança, não é famoso por sua paciência. Para cada dia que um dragão seu passa dormindo no alojamento, Sauron, cujo Olho enxerga tranquilamente tudo que se passa nos domínios de Daenerys, cobra dela uma multa, que pode variar de dragão para dragão, dependendo dos planos de Sauron para seus dragões. Sauron envia exatamente um dragão por dia, e o dragão sempre chega bem no início do dia, de modo que Daenerys já pode começar a treiná-lo imediatamente. Ainda, se há dragões dormindo no alojamento e nenhum sendo treinado, Sauron envia um para matar Daenerys. Daenerys Targaryen deseja minimizar a multa total a pagar a Sauron e está pedindo sua ajuda. Você já lhe disse que não pode prever futuro e que o melhor que você pode fazer é: toda vez em que ela não estiver trabalhando com um dragão e quiser escolher um no alojamento para começar a treinar, você pode dizer a ela qual dragão escolher de modo que a escolha seria ótima se nenhum dragão mais viesse nos dias seguintes. Entrada A i-ésima linha da entrada diz respeito ao i-ésimo dragão enviado por Sauron a Daenerys e consiste de dois inteiros: representando respectivamente de dias necessários para treinar o i-ésimo dragão e a multa cobrada por dia que dragão passa dormindo. Para quaisquer i j distintos, A entrada possui no máximo 105 linhas e termina em fim de arquivo. Saída Imprima uma linha contendo unicamente o valor mínimo total da multa que Daenerys pagará a Sauron se seguir seus conselhos. Exemplo de Entrada Exemplo de Saída 4 1 2060 3 4 1 1000 2 2 6 Escola de Inverno da Maratona Erechim RS-2015beecrowd 2065 Fila do Supermercado Por Cristhian Bonilha, UTFPR Brazil Timelimit: 1 Hoje é a inauguração de um grande supermercado em sua cidade, e todos estão muito excitados com os baixos preços prometidos. Este supermercado tem N funcionários que trabalham no caixa, identificados por números de 1 N, onde cada funcionário leva um determinado tempo para processar um item de um cliente. Ou seja, se um cliente tem itens em sua cesta, um determinado funcionário levará segundos para processar todos os itens deste cliente. Quando um cliente entra na fila para ser atendido ele espera até que um funcionário esteja livre para atendê-lo. Se mais de um funcionário estiverem livres ao mesmo tempo, o cliente será atendido pelo funcionário de menor número de identificação. Tal funcionário só estará livre novamente após processar todos os itens deste cliente. Há M clientes na fila para serem atendidos, cada um com um determinado número de itens na sua cesta. Dadas as informações sobre os funcionários nos caixas e os clientes, gerente pediu sua ajuda para descobrir quanto tempo levará para que todos os clientes sejam atendidos. Entrada A primeira linha conterá dois inteiros Ne M, indicando número de funcionários no caixa e número de clientes, respectivamente Em seguida haverá N inteiros indicando quanto tempo leva para i-ésimo funcionário processar um item (1 para todo N). Em seguida haverá M inteiros indicando quantos itens j-ésimo cliente tem em sua cesta (1beecrowd 2460 Fila Por OBI Olimpiada Brasileira de 2014 Brazil Timelimit: 1 Com a proximidade da Copa do Mundo, fluxo de pessoas nas filas para compra de ingressos aumentou Como as filas estão cada vez maiores, pessoas menos pacientes tendem a desistir da compra de ingressos e acabam deixando as filas, liberando assim vaga para outras pessoas. Quando uma pessoa deixa a fila, todas as pessoas que estavam atrás dela dão um passo a frente, sendo assim nunca existe um espaço vago entre duas pessoas. A fila inicialmente contém N pessoas, cada uma com um identificador diferente. Joãozinho sabe estado inicial dela e os identificadores em ordem das pessoas que deixaram a fila. Sabendo que após estado inicial nenhuma pessoa entrou mais na fila, Joãozinho deseja saber estado final da fila. Entrada A primeira linha contém um inteiro N (1