PROBLEMAS CODEFORCES

Número da Lista: 18
Conteúdo da Disciplina: D&C

Alunos

Matrícula	Aluno
22/2006169	Natan da Cruz Almeida
22/1022408	Paulo Henrique Lamounier

Sobre

Este projeto consta com 4 desafios resolvidos do Codeforces, sendo eles:

• (Q1) - D. Permutation Transformation link: Dada uma permutação a de números inteiros de 1 a n, você deve transformá-la em uma árvore binária.
  • O maior elemento da permutação se torna a raiz da árvore.
  • Os elementos à esquerda do maior formam a subárvore esquerda.
  • Os elementos à direita do maior formam a subárvore direita.
  • Para cada elemento da permutação, calcule sua profundidade na árvore (o número de arestas do caminho da raiz até o nó).
• (Q2) - D. a-Good String link: Dada uma string s de letras minúsculas, você precisa transformar essa string em uma "c-good string" para o valor c = 'a'. A string é considerada c-good se pelo menos uma das seguintes condições for atendida:
  • Para a string s = "cdbbaaaa", ela é uma a-good string porque:
    • A segunda metade (aaaa) é composta apenas por a.
    • A primeira metade (cdbb) é uma b-good string.
    • A primeira metade de cdbb (cd) é uma c-good string.
  • Determinar o número mínimo de mudanças necessárias para transformar a string s em uma a-good string.
• (Q3) - D. Masha and a Beautiful Tree: link O problema pede para organizar as folhas de uma árvore binária completa em ordem crescente da esquerda para a direita. Masha pode inverter os filhos de qualquer nó interno da árvore. O objetivo é encontrar o número mínimo de inversões necessárias para alcançar essa organização ou indicar se é impossível.
• (Q4) - B. Equivalent Strings: link Verifique se duas strings de mesmo comprimento são equivalentes, podendo ser idênticas ou reorganizadas em metades equivalentes de forma recursiva. Retorne "YES" se forem equivalentes, caso contrário, "NO".

Vídeos

• Solução Q1 e Q2: link

• Solução Q3: link

• Solução Q4: link

Instalação

Linguagem: C++
Framework: Não possui frameworks
Para utilizar e testar os programas, primeiro é necessário ter um compilador de c/c++ instalado em sua máquina, caso não tenha, utilize esse fórum para baixar

acesse-aqui

Após instalar o compilador em sua máquina, clone o repositório utilizando

git clone <link do repisotório>

Uso

Após clonar o repositório, entre na pasta via terminal e compile os códigos utilizando

g++ -Wall -o <nome_arquivo_compilado> <arquivo_para_compilar>

ex:

g++ -Wall -o main Q1.cpp

Um arquivo executável (.exe) será criado, para realizar os testes, utilize

./main

Dessa forma será possível utilizar os casos de teste dos programas. Também é possível colocar os casos de teste em algum arquivo de texto e utilizar o comando cat para testá-los

cat <arquivo.txt> | ./main