OpenLLM-France/wikimedia huggingface dataset:
# Resolução de problemas/Avaliações dos juízes on-line
## Avaliações dos juizes on-line

Quando você submete seu programa a um juiz on-line, ele julgará seu programa à partir de um conjunto de entradas. As saídas serão então comparadas com as saídas esperadas pelo juiz. De acordo com a sua saída, você receberá uma avaliação. Abaixo estão explicadas as avaliações usadas pelo juiz do site do Valladolid.

## Accepted

Quando seu programa produz as respostas corretamente e as apresenta da forma especificada no problema, o juiz avaliará seu programa como "Accepted".

## Presentation error

"Presentation Error" ocorre quando seu programa produz as respostas corretamente mas não as apresenta da forma exigida pelo problema. Esteja sempre atento à saída exigida: linhas em branco, espaços, indentações, acentos e outros detalhes esquecidos são causas comuns de "Presentation Error".

## Wrong answer

Quando o seu programa não produz corretamente as respostas esperadas pelo juiz, você receberá a notificação de "Wrong Answer". Esteja sempre atento na hora de ler o problema. Muitas informações ou dicas importantes podem passar desapercebidas.

## Runtime error

"Runtime Error" são erros que ocorrem durante a execução do programa. São erros comuns: overflow, acesso a posições de memória inválidas, erros de aritmética etc.

## Time limit exceeded

Para cada problema, o juiz estipulará um tempo limite máximo. Caso seu programa extrapole esse limite, você recebera a notificação de "Time Limit Exceeded". Tenha sempre muito cuidado com algoritmos de alta complexidade e a possibilidade de loops infinitos.

## Memory limit exceeded

Da mesma forma que o tempo, há um limite para a memória. No site do Valladolid, o limite máximo de memória é de 32MB. Mas tenha cuidado: esse limite é para toda a memória. Isso quer dizer que essa memória é compartilhada entre o heap e a pilha. Portanto, você não poderá alocar 32MB de variáveis no seu programa. Se o fizer, receberá "Memory Limit Exceeded".

## Output limit exceeded

Há também um limite para o tamanho da sua saída. Se você o ultrapassar, receberá a notificação de "Output Limit Exeeded".

## Compile error

Quando o juiz recebe o seu programa, ele o compilará. Caso algum erro de compilação ocorra, você receberá "Compile Error".

## Restricted function

Tenha sempre cuidado ao usar funções que não fazem parte da biblioteca padrão da sua linguagem. Se fizer uso de alguma delas, o juiz acusará "Restricted Function".
# Resolução de problemas/Cubos coloridos
## O problema

O problema requer a elaboração de um programa que recebe como entrada as faces dos cubos, e gera como saida a quantidade de cubos iguais para cada caso de teste.

## Como resolver
### A entrada

Neste programa, as cores dos cubos são representadas por números. A ordem em que as cores são colocadas na entrada são descritas no problema. Admito que 0,1,2,3,4,5 correspondem as posições em que as cores são inseridas. No exemplo da questão a entrada:
a cor 7 estará na posicão 0, a cor 2 na posicão 1, a cor 1 na posicão 2, a cor 4 na posicão 3, a cor 3 na posicão 4 e a cor 6 na posicão 5.

### Como representar um cubo?

Uma maneira de representarmos o cubo, seria criarmos um registro com as posições numeradas do cubo, como foi explanado acima, e uma variável que diz se esse cubo já é igual a algum outro do conjunto dado na entrada (será importante na hora de contar o número de cubos diferentes). Minha sugestão é a seguinte:

### O principal desafio

O principal desafio deste programa consiste em comparar dois cubos e saber se eles são iguais. Para isso teremos que realizar em cada cubo as possíveis rotações e comparar com outro cubo para saber se eles são iguais. As rotações possíveis são na horizontal, na vertical e no eixo.

### Detalhes de implementação

Sugiro dividir as tarefas. Podemos criar 3 funções, que recebem como entrada um vetor com as cores, cada uma realizando um tipo de rotação.
A primeira função seria a de rotação na horizontal. Basta que troquemos as posições das cores no cubo.
A segunda função será a de rotação na vertical.
A terceira será a de rotação no eixo.
Também é interessante usarmos uma função que compara dois vetores e verifica se eles são iguais:
Com as funções de rotação prontas, só falta criar uma função que pega dois cubos e os compara. Podemos fazer isso por rotacionar apenas um deles e comparar com o outro, até achar dois vetores iguais.
Podemos agora contar o numero de cubos diferentes, usando para isso uma função que recebe como entrada um vetor de cubos. É importante nos lembrarmos de atualizar o valor de igual quando acharmos um cubo igual a outro:
A nossa função main agora terá que ler as cores do cubo e armazenar num vetor. Depois disso armazenar os cubos em um vetor de cubos. Essas estruturas servirão de entradas para as funções sobre as quais explanamos acima:
Com isso o problema está resolvido.
Contribuído por Ricardo José Sales Júnior - Ciências da Computação - DIMAp - UFRN
Veja este problema em: Maratona de Programação (pdf).
# Resolução de problemas/Introdução

Índice

## Introdução

Esse wikilivro tem como objetivo ser uma coletânea de soluções para problemas de propostos em competições de programação como a Olimpíada Brasileira de Informática, a Maratona de Programação da SBC (Sociedade Brasileira de Computação) , a ACM International Collegiate Programming Contest, o TopCoder , entre outros.
O objetivo dessas competições é medir a capacidade dos competidores a desenvolver e implementar soluções para problemas. O formato de cada tipo de competição é diferente e pode exigir estratégias específicas.
Cada competição permite a utilização de certas linguagens de programação pré-estabelecidas. Algumas competições são até orientadas para uma determinada linguagem. É importante ter facilidade em uma linguagem de programação "popular", como C, C++ ou Java para poder participar do maior número possível de competições de forma competitiva. É especialmente importante conhecer, além dos recursos básicos da linguagem, todas as funcionalidades oferecidas nas linguagens padrão, pois aumentam consideravelmente o leque de construções pré-definidas e o uso das mesmas torna mais rápida a implementação de suas soluções.
Resolvemos organizar a apresentação dos problemas e de propostas de solução em ordem de dificuldade e, dentro de cada grau de dificuldade, de forma temática. Essa abordagem tem como objetivo incentivar o leitor a se desenvolver em todas as áreas e não ser apenas bom para resolver, digamos, problemas numéricos.
A leitura desse wikilivro por si só não tornará o leitor uma fera em competições de programação. Para isso, é necessário praticar essa atividade de forma intensiva. Para tanto, recomendamos o sítio que disponibiliza um repertório de centenas de problemas, organiza competições em linha, etc.
Índice
# República da China/Natureza

O país é constituído pela Ilha de Formosa e por mais 77 ilhas menores. Localiza-se 160 quilômetros a leste da República Popular da China, da qual se separa pelo Estreito de Formosa. A Ilha de Formosa pode ser dividida em duas porções: a porção leste, montanhosa, que abriga o ponto culminante do país (o Pico Yü Shan, com 3 997 metros de altura) e a porção oeste, composta por uma planície que abriga a maior parte da população do país. O país é cortado pelo Trópico de Câncer. O clima é tropical no sul e subtropical no norte, com ocorrência frequente de terremotos e tufões.
* Mapa do país. As zonas vermelhas e verdes são as mais altas e a zona azul é a mais baixa.
* Pico Yü Shan (traduzido do mandarim, "montanha de jade"): o ponto culminante do país
* Ursus thibetanus formosanus Swinhoe, 1864: um dos muitos animais endêmicos da Ilha de Formosa
* Azaleia (Rhododendron peryclimenoides), uma flor típica do país
* Flor de cerejeira-do-japão (Prunus serrulata), outra espécie muito comum no país
* Mictyris brevidactylus no Pântano Kaomei, em Taichung
* Naso unicornis em um recife de coral perto da Ilha Verde
* Muntiacus reevesi, endêmico do país

## Referências

* ↑ Almanaque Abril 2004. São Paulo: Abril, 2004. p.652
# Resolução de problemas
## Índice

Este livro tem uma coleção para a criação de versões nos formatos HTML, PDF, ODT, ZIM, ePUB ou para encomendas para a PediaPress.
* Introdução
* Estratégias
* Linguagens de programação
* Standard template library
* Avaliações dos juízes on-line
* Problemas de complexidade baixa
   * Geométricos
   * Numéricos
      * Problem 348: Optimal array multiplication sequence
      * Problem 369: Combination
      * Problem 424: Integer inquiry
      * Problem 10699: Count the factors
   * Diversos
      * Problem 10661: The perspectographer
      * Problema D (ACM ICPC 2005 - Seletiva Regional): Cubos coloridos
* Problemas de complexidade média
   * Geométricos
   * Numéricos
   * Diversos
      * A node too far
      * Specialized four-digit numbers
      * Maratona de programação
      * Matrix chain multiplication
* Problemas de complexidade alta
   * Geométricos
   * Numéricos
   * Diversos
# Resolução de problemas/Combination
## Combinação

Na análise combinatória, a combinação C(n, k) (lê-se: n elementos tomados k a k vezes) define um subconjunto de n com k elementos. O número de combinações é o coeficiente binomial:
Problemas que envolvem a formação de subconjuntos à partir de um determinado espaço amostral podem ser resolvidos usando-se combinação. Por exemplo:
    Dado grupo de 100 pessoas, deseja-se formar comissões de 20 pessoas cada. Quantas comissões diferentes podem ser formadas?
    R: C(100,20)
    Numa escolinha de basquete 30 alunos estão inscritos. Sabendo-se que uma equipe de basquete é composta por 5 atletas, quantas equipes diferentes podemos formar (independente das posições)?
    R: C(30, 5)
Perceba que nos problemas de combinação a ordem dos elementos dentro de um subconjunto não importa.
Para calcularmos computacionalmente o valor exato de n elementos tomados k a k vezes usando a fórmula binomial acima pode tornar-se impossível quando trabalhamos com valores de n e k muito grandes, visto que estamos trabalhando com fatoriais. Tome por exemplo o valor exato de 100!:
Um valor que certamente não caberá em um long long int do C. Mesmo que o valor final da combinação caiba em uma variável do tipo long long int, perceba que no denominador da fração há uma multiplicação de fatoriais! Assim, os valores intermediários podem ultrapassar a faixa de valores desse tipo de dados, causando um overflow. Vale salientar que na resolução desse problema a utilização de tipos ponto-flutuante não é permitida.
Então, como fazemos para calcularmos combinações com valores de n e k muito grandes? Por exemplo, C(100, 10)?
Uma possível solução é usarmos o Triângulo de Pascal: um triângulo numérico infinito formados por binômios , em que n representa o número da linha e k o número da coluna.
Calculando o valor dos binômios, temos o seguinte triângulo:
Agora, se quisermos calcular C(100,10) basta calcularmos o elemento que está na 100ª linha e 10ª coluna. Todavia, não é necessário calcularmos o valor de todos os binômios, apenas precisamos conhecer a Relação de Stiffel: cada número do Triângulo de Pascal é igual à soma do número imediatamente acima e seu antecessor.
Abaixo segue uma possível implementação em C para o cálculo de combinações à partir do Triângulo de Pascal:
No primeiro trecho do programa, preenchemos o Triângulo de Pascal conforme a Relação de Stiffel. Observe que a 1ª coluna e a diagonal principal devem ser sempre preenchidas com 1.
Em seguida, apenas imprimos na tela a combinação de N tomados K a K vezes.
Veja esse problema em: http://acm.uva.es/p/v3/369.html
# Resolução de problemas/Estratégias

Dicas para os iniciantes:
# Resolução de problemas/Count the factors
## Conte os fatores
### O Problema

Imagine que você precisa encontrar os diferentes fatores primos de um número natural. Por exemplo:
$60=2*2*3*5$
O número 60 pode ser formado pelo produto de três números primos distintos. No entanto 60 é um número muito pequeno e nós precisamos computar números grandes como 1000000 no máximo. Portanto não podemos usar qualquer algoritmo para achar os números primos e testar quais deles são fatores do número natural em questão.

### A Solução

Um algoritmo possível para solucionar o problema usa o crivo de Eratóstenes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
O algoritmo trabalha da seguinte maneira, ele seleciona cada elemento e marca seus múltiplos como não primos, note que não precisamos mais procurar pelos múltiplos de um número que já foi marcado como não primo. Por exemplo para o 2, no exemplo acima, marcariamos todos os números pares como não primos.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Depois para o três:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
O quatro já foi marcado, vamos para o cinco:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
E assim por diante, assumimos que o número 1 não é primo:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Assim temos todos o números primos menores que 25.
Uma implementação possível para o crivo de Eratóstenes:
No final do algoritmo acima teremos todos os primos menores que MAX no vetor primos. Depois disso é só testar quais primos são fatores do número em questão e contar sempre que encontrarmos um fator diferente. Assim temos:
Em que n é o número em questão, c o contador e pri o vetor de primos.
Veja esse problema em: http://acm.uva.es/p/v106/10699.html
# Manual de CVS/Dentro do software de CVS

Agora você precisa editar nas preferências do software a localização do arquivo .bat, chave pública e da chave privada. Devido a atualizações de software, somente é necessário o CVSROOT correto.
# Manual de CVS/Pondo arquivos no repositório

No caso da colocação de um novo arquivo no repositório é necessário adicioná-lo ao cadastro do repositório antes, com a opção add. Caso se trate da colocação de um arquivo já existente anteriormente, que estejamos apenas atualizando, seria preciso apenas realizar o commit.
O último comando poderia também ser apenas:
e neste caso o comando realizaria o commit de tudo o que tiver sido alterado no diretório corrente. Se não for isso o que se quer deve se optar pela primeira forma, especificando o que se quer atualizar no servidor.
Mesmo que apenas uma pessoa esteja alterando determinado código é recomendável que se realize commits periódicos, diariamente, semanalmente ou no período que se achar necessário. Quanto mais commits forem realizado mais detalhadamente as alterações progressivas no código poderão ser rastreadas. Fazer commit a cada pequena alteração, porém, pode também ser ruim, criando muitas revisões no código e também dificultando o mapeamento de alterações funcionais. Por exemplo, se um programador está mexendo num código HTML para implementar um detalhe de layout de uma página, pode ser adequado realizar o commit apenas quando terminar. Se assim o fizer poderá comparar detalhadamente todas as mudanças no código referentes a esta mudança. Se o trabalho for longo, porém, ele pode preferir realizar commit diariamente, de modo a não esquecer o que foi mudando aos poucos, podendo comparar mudanças diárias.
# Manual de CVS/Importando os fontes

Caso os fontes do projeto já existam (antes de se criar o repositório CVS), importe seus fontes: Entre no diretório onde se encontra seu projeto e digite
Caso não seja utilizada a opção -m para descrever o projeto, o CVS abrirá um editor de texto para que isso seja feito.
Note que o termo importar no contexto CVS deve ser interpretado do ponto de vista do servidor. No cliente, a impressão que se tem é que algo está saindo da máquina dele e entrando na máquina do servidor. Para o cliente, e conseqüentemente o usuário, faria mais sentido se o nome da função fosse exportar.
# Manual de CVS/Pegando os arquivos

Para obter um arquivo ou toda uma estrutura de diretórios de um repositório CVS é preciso utilizar a opção "checkout". Normalmente as opções do comando tem uma forma abreviada. A abreviação usada para checkout é co. Podemos especificar o diretório de um projeto, obtendo ele e todo o seu conteúdo, ou podemos especificar um subdiretório qualquer dentro de sua estrutura ou mesmo um único arquivo que queiramos obter:
ou
Isso criará um diretório com o nome do projeto localmente.
Se mais de um usuário for trabalhar no mesmo projeto ao mesmo tempo, cada um deve rodar esse comando em um diretório distinto. É interessante que haja uma boa comunicação entre pessoas trabalhando num mesmo projeto para que seja mais fácil juntar depois alterações num mesmo projeto. Alguns outros tipos de sistemas de controle de versão possibilitam que o usuário reserve os arquivos que está editando, evitando que outro usuário mexa neles ao mesmo tempo. Esta não é a filosofia do CVS.
Se for um diretório num servidor remoto:
# Manual de CVS/Conceitos básicos

O CVS, ou Concurrent Version System (Sistema de Versões Concorrentes) é um software que tem por objetivo permitir o controle da criação e modificação de arquivos, normalmente em formato texto, organizando as diversas versões do mesmo, em um diretório localizado na máquina local ou em um servidor remoto, mantendo-se suas versões antigas e o histórico de quando e por quem foram manipulados. É especialmente útil para se controlar versões de um software durante seu desenvolvimento, ou para composição colaborativa de um documento.
Os arquivos são reunidos em projetos, os quais podem ser recuperados por diversas pessoas que têm acesso ao local de armazenamento do projeto, que é denominado repositório.
O acesso ao repositório acontece por meio de seu endereço e login, com a necessidade ou não de uma senha de proteção.
A exemplo de outros softwares desenvolvidos colaborativamente, o CVS pode ser baixado gratuitamente e tem o seu código aberto.
# Manual de CVS/Exportando a variável de ambiente CVSROOT

Para usar o comando cvs é necessário que o mesmo saiba onde se encontra o repositório que se deseja acessar no momento em que executamos o comando. Isso pode ser passado a ele através de uma variável ambiente (CVSROOT) ou na própria linha de comandos.
Para o shell bash (o mais comum nos Linuxes) defina a variável CVSROOT como abaixo:
ou
Caso esteja usando o csh ou tcsh faça assim:
ou
Caso prefira pode usar a opção -d do comando "cvs" em cada execução do mesmo:
No exemplo acima o comando cvs é utilizado para obter o arquivo chamado arquivo_exemplo.txt do repositório CVS a partir de uma pasta chamada diretorio_do_projeto.
# Manual de CVS/Observações

O CVS realiza um controle muito eficiente de versões e é capaz, inclusive, de realizar alterações no mesmo arquivo, caso duas pessoas editem o mesmo arquivo ao mesmo tempo.
Se houver conflito, entretanto, o sistema deixará a decisão para ser tomada pelos humanos.
Será dado um aviso que o mesmo ponto do arquivo foi alterado, com um log do que foi feito por cada usuário, e alguém vai ter que usar o discernimento e escolher qual das duas alterações deverá ser efetivada.
# Manual de CVS/Criando um arquivo .bat

Este arquivo é necessário para que o plink.exe encontre a sua chave. (Geralmente é colocado dentro do C:/ junto com o plink.exe), não é necessário editar o script acima, somente adicione a senha.
# Manual de CVS/Gerando a chave criptografada

Rode o puttygen.exe, gere as chaves pública e privada e salve-as.
# Nós matemáticos/História

A teoria dos nós começa a aparecer em 1771, quando Alexandre-Theóphile Vandermonde (músico, quimico e matemático francês) relaciona a topologia dos nós com a geometria de posição.Porém, foi no século XIX que a teoria começa a ser desenvolvida e estudada por matemáticos da época. Gauss teve a sua participação no desenvolvimento através de sua definição de números de enlaces.
Em 1860, William Thomson cria uma teoria que dizia que os átomos eram nós pertencentes ao éter. Após essa teoria, ele e Peter Guthrie Tait, escrevem o livro Treatise on Natural Philosophy, publicado por Oxford University Press, onde contribuía e iniciava o processo de construção da topologia algebrica dos nós, além também, de contribuir para outras particularidades da física.
Peter Guthrie Tait, publicou em 1885 uma tabela de nós de até dez cruzamentos, algo que ainda não tinha sido proposta por matemáticos da época. Com isso, Tait ficou conhecido por inspirar topólogos do fim do século XIX e início do século XX.
Os matemáticos Max Dehn e J. W. Alexander passaram boa parte de suas vidas estudando nós, com um olhar mais profundo para grupo de nós e nós invariantes, com a criação do polinômio de Alexander.
Em 1970 ocorre a introdução da geometria hiperbólica por William Thurston através do teorema de hiperbolização, na qual revolucionou o meio matemático. Através desse teorema, muitos nós se encaixaram na categoria de nós hiperbólicos, além da criação de novos nós invariantes.
No fim do século XX, talvez tenha sido o ápice da teoria dos nós, com grandes trabalhos de diversos matemáticos e a descoberta do polinômio de Jones pelo matemático Vaughan Jones, a ciência pode relacionar a teoria dos nós com diversas aplicações da física, como por exemplo o campo da física quântica.
# Nós matemáticos/Invariantes de nó

Um invariante de nó é apenas uma forma de distinguir e ordenar por classes os diversos nós existentes.Citaremos abaixo, alguns invariantes para que se possa ter uma maior noção desse tipo de "medida" dos nós.
Alguns exemplos de invariantes:
* Número de cruzamento;
* Número de desenlace ou Górdio;
* Número de coloração;
* Número de ponte.
Apenas esses quatros exemplos são capazes de diferenciar muitos nós, você verá a seguir, uma lista de nós que foram classificados a partir desse invariantes;
# Nós matemáticos/Dowker

Assim como a notação Alexander-Briggs vista na seção anterior, a notação Dowker, também conhecida como notação Dowker-Thistlethwaite é uma notação para indicar a forma de um nó. É construída como uma sequência finita de números inteiros pares. Os números são determinados ao se "seguir" o desenho de um nó e marcando os cruzamentos com números inteiros consecutivos. Pode ser observado que cada cruzamento é visitado duas vezes, uma vez por cima e outra por baixo (sobre e subcruzamento, respectivamente), o que gera um pareamento entre os números inteiros ímpares e os números inteiros pares. Um sinal apropriado é dado para indicar o tipo de cruzamento, mas como o diagrama tem mais de uma notação Dowker possível e como a notação é insensível a espelhos, o sinal é arbitrário e serve apenas para diferenciar os cruzamentos. Por exemplo, o nó da figura ao lado tem os cruzamentos numerados de 1 a 12, que por sua vez têm os sobrecruzamentos pares atribuídos de um sinal negativo. Os pares de cruzamentos são $(1,6)$, $(3,-12)$, $(5,2)$, $(7,8)$, $(9,-4)$ e $(11,-10)$. Logo, a representação desse nó segundo a notação Dowker é a sequência $6$ $-12$ $2$ $8$ $-4$ $-10$.
# Nós matemáticos/Invariante hiperbólico

William Thurston provou que muitos nós são nós hiperbólicos, o que significa que o complemento de nó, isto é, o conjunto de pontos no $\mathbb {R} ^{3}$, admite uma estrutura geométrica, em particular da geometria hiperbólica. A estrutura hiperbólica depende apenas do nó, então qualquer quantidade calculada a partir da estrutura hiperbólica é portanto um invariante de nó.
# Nós matemáticos/Diagramas de nós

Um diagrama de nó é método mais comum de descrever um nó. Um diagrama é formado pela projeção de um nó (que pertence ao R³, como já visto) em um plano no R². Essa projeção permite que o plano mostre características úteis, como por exemplo, a visualização do nó com apenas pontos duplos e esse pontos se apresentam apenas no interior do nó.
É necessário nessa projeção, descrever qual segmento está "passando por baixo ou por cima", para que o leitor consiga classificar o nó.
Como ja visto no capítulo de equivalência de nós, um diagrama é equivalente ao outro, se um pode ser transformado no outro. Veja abaixo um exemplo.