Executando verificação de segurança...
1
rodriguesxxx
3 min de leitura ·

[AJUDA] Ansiedade por NÃO conseguir resolver Algoritmos SIMPLES

contexto: Estou estudando para a OBI e tenho resolvido algoritmos de todas as edições. No entanto, estou enfrentando o seguinte problema: consigo conceber a solução logicamente, mas ao tentar implementá-la, travo completamente. Já se passaram 4 horas, estou tentando resolver esse algoritmo, que é bastante simples, e não consigo. Isso tem causado uma ansiedade intensa, a ponto de não sentir fome mais.

Escada perfeita - OBI2006

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de vários pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem re-arranjadas no formato de “escada“ . Para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha c outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Dada uma sequência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro N que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída

Seu programa deve imprimir uma única linha, contendo um único inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

Exemplos

Entrada

5
5 4 5 4 2		Saída

5
Entrada

6
9 8 7 6 5 4		Saída

9
Entrada

2
1 5		Saída

-1

Minha Solução

Sabemos que a escada perfeita aumenta de 1 em 1. Isso significa que ela é uma PAde razão 1.

Um pouco sobre Progressão Aritmética - PA

Uma prograssão aritmética é uma sequência númerica em que cada termo, partir do segundo é a soma do termo anterior com uma constante R

  • Exemplo de PA

    {2, 3, 4, 5, 6} O primeiro termo é o 2e a razão é 1.

  • Fórmula

      `an = a1 + (n - 1).r`
  
  {2, 3, 4, 5, 6} = 2 + (3...n - 1) . 1

  • Soma de PA

    Para encontrarmos a soma de determinado intervalo em uma PA podemos utilizar a fórmula

      `Sn = n/2 . (a1 + an)`
    • n = Tamanho intervalo.
    • a1 = Posição do inicial na PA.
    • an = Posição do intervalo na PA.

    Exemplo de soma:

    Dada a seguinte PA= {2, 4, 6, 8, 10}, de razãoigual a 2.
    Determine a soma dos 3 primeiros valores dessa PA.

    Valores = {2, 4, 6}
    n = 3
    a1 = 2
    a3 = 6
    s = 3/2 . (2 + 6) -> 12

Lógica da Solução

  • Sabemos quanto vale o n(o numero de pilhas) a partir dele conseguimos calcular a soma dessa PA, basta realizar um loop.

  • Sabemos que a razão é 1. Pois a escada deve aumentar de 1em 1degrau.

  • Utilizaremos as seguintes equações para calcularmos o valor iniciale finalda PA

    somaPA = Utilizar for()
    valorFinal = ( ( somaPA . 2 / n ) + n - 1 ) / 2
    valorInicial = valorFinal - n + 1

Travei.

Carregando publicação patrocinada...
2
DeividSouSan

Essa foi a solução que eu encontrei. Testei apenas para os valores informados e não está muito bem escrito. Porém, espero que possa ajudar a entender como encontrar a sua solução.

Obs.: eu acho que o problema da sua solução é que você não sabe quantos blocos vai na primeira coluna, caso soubesse era, de fato, ir somando 1 à cada coluna. Além disso, se encontrar algum erro na minha solução seria ótimo saber.

def minBlocks(columns):
    min_blocks = 0
    for i in range(columns):
        min_blocks += i + 1

    return min_blocks


def buildStair(columns: int, block_list: list):
    min_blocks = minBlocks(columns)
    block_count = sum(block_list)
    blocksLeft = block_count - min_blocks

    if block_count < min_blocks or not (blocksLeft % columns == 0):
        print("Impossível montar escada")
        return

    stair = []
    for i in range(columns):
        if (i == 0):
            stair.append(1)
        else:
            stair.append(stair[i-1] + 1)

    leftForEachColumn = blocksLeft // columns
    stair = list(map(lambda x: x + leftForEachColumn, stair))

    return stair


def movedBlocks(block_list: list, stair: list):
    movedBlocks = 0
    columns = len(stair)

    for column in range(columns):
        movedBlocks += abs(block_list[column] - stair[column])

    return movedBlocks // 2


blockList = [5, 4, 5, 4, 2]
stair = buildStair(5, blockList)
print(stair)
if stair:
    print(movedBlocks(blockList, stair))

blockList = [9, 8, 7, 6, 5, 4]
stair = buildStair(6, blockList)
print(stair)
if stair:
    print(movedBlocks(blockList, stair))

blockList = [1, 5]
stair = buildStair(2, blockList)
print(stair)
if stair:
    print(movedBlocks(blockList, stair))
2
raf

Resolvi experimentar. Estou praticando Java funcional, então não estou utilizando os loops tradicionais, mas sim os range no lugar deles.

class EscadaPerfeita {
    static int calcular(final List<Integer> escada) {
        var escadaPerfeita = escadaPerfeita(escada);
        if (escadaPerfeita.isEmpty()) {
            System.out.println(escada + " -> -1");
            return -1;
        }

        var numeroDeMovimentos = range(0, escada.size())
                .map(i -> escada.get(i) - escadaPerfeita.get(i))
                .filter(i -> i > 0)
                .sum();
        System.out.println(escada + " -> " + escadaPerfeita + " -> " + numeroDeMovimentos);
        return numeroDeMovimentos;
    }


    private static List<Integer> escadaPerfeita(List<Integer> escada) {
        Function<Integer, List<Integer>> gerarProjecaoLinear =
                (inicio) -> range(inicio, inicio + escada.size())
                        .boxed()
                        .toList();

        int somaDasAlturas = escada.stream().mapToInt(Integer::intValue).sum();
        return rangeClosed(0, somaDasAlturas)
                .boxed()
                .map(gerarProjecaoLinear)
                .filter(projecaoLinear -> projecaoLinear
                        .stream()
                        .mapToInt(Integer::intValue)
                        .sum() == somaDasAlturas)
                .findFirst()
                .orElse(List.of());
    }
}

Testes de unidade

class EscadaPerfeitaTest {
    @ParameterizedTest
    @MethodSource("dadosDeTeste")
    void numeroDeMovimentosParaEscadaPerfeita(List<Integer> escada, int expectativa) {
        assertEquals(expectativa, EscadaPerfeita.calcular(escada));
    }

    static Stream<Arguments> dadosDeTeste() {
        return Stream.of(
                // Dados do artigo
                arguments(List.of(5, 4, 5, 4, 2), 5),
                arguments(List.of(9, 8, 7, 6, 5, 4), 9),
                arguments(List.of(1, 5), -1),
                // Meus dados adicionais
                arguments(List.of(0), 0),
                arguments(List.of(7), 0),
                arguments(List.of(1, 2, 3), 0),
                arguments(List.of(4, 1, 1), 3),
                arguments(List.of(7, 1, 1), 5),
                arguments(List.of(10, 9, 8), 2),
                arguments(List.of(14, 13, 7, 16, 10), 9),
                arguments(List.of(15, 1, 2), 10),
                arguments(List.of(5, 5), -1),
                arguments(List.of(5, 6, 5), -1)
        );
    }
}

A saida do console (ajuda a visualizar):

[5, 4, 5, 4, 2] -> [2, 3, 4, 5, 6] -> 5
[9, 8, 7, 6, 5, 4] -> [4, 5, 6, 7, 8, 9] -> 9
[1, 5] -> -1
[0] -> [0] -> 0
[7] -> [7] -> 0
[1, 2, 3] -> [1, 2, 3] -> 0
[4, 1, 1] -> [1, 2, 3] -> 3
[7, 1, 1] -> [2, 3, 4] -> 5
[10, 9, 8] -> [8, 9, 10] -> 2
[14, 13, 7, 16, 10] -> [10, 11, 12, 13, 14] -> 9
[15, 1, 2] -> [5, 6, 7] -> 10
[5, 5] -> -1
[5, 6, 5] -> -1
2
raf

Eu decidi enviar minha resposta anterior na página da contudo, mas não ultrapassou o limite de tempo de execução. Optei por reescrever utilizando os valores primitivos para tornar o processo mais rápido. Agora, todos os testes foram bem-sucedidos.

public class escada {
	public static int[] lerEntrada() {
		Scanner scanner = new Scanner(System.in);
		int tamanho = Integer.parseInt(scanner.nextLine()); // Nao preciso da primeira linha contendo o tamanho dos numeros
		String linha = scanner.nextLine();
		String[] inputArray = linha.split("\\s+");
		try {
			int[] resultado = new int[tamanho];
			for (int i = 0; i < tamanho; i++) {
				resultado[i] = Integer.parseInt(inputArray[i]);
			}
			return resultado;
		} catch (NumberFormatException e) {
			System.err.println("Entrada invalida " + e.getMessage());
			System.exit(-1);
		}
		return new int[0];
	}

	public static void main(String[] args) {
		int[] escada = lerEntrada();
		System.out.println(EscadaPerfeitaFast.calcular(escada));
	}

	static class EscadaPerfeitaFast {
		static int calcular(final int[] sequencia) {
			var progressaoAritimetica = progressaoAritimetica(sequencia);
			if (progressaoAritimetica == null) {
				return -1;
			}
			return calcularNumeroDeMovimentos(sequencia, progressaoAritimetica);
		}

		private static int calcularNumeroDeMovimentos(int[] escada, int[] escadaPerfeita) {
			int soma = 0;
			for (int i = 0; i < escada.length; i++) {
				int movimentos = escada[i] - escadaPerfeita[i];
				if (movimentos > 0) {
					soma += movimentos;
				}
			}
			return soma;
		}

		private static int[] progressaoAritimetica(int[] sequencia) {
			long somaSequencia = somarSequencia(sequencia);
			int primeiroTermoProgressaoAritimetica = calcularPrimeiroTermoProgressaoAritimetica(sequencia);
			if (somarProgressaoAritimetica(primeiroTermoProgressaoAritimetica, sequencia.length) == somaSequencia) {
				return gerarProgressaoLinear(primeiroTermoProgressaoAritimetica, sequencia.length);
			}
			return null;
		}

		private static int calcularPrimeiroTermoProgressaoAritimetica(int[] escada) {
			int s = (int) somarSequencia(escada);
			int n = escada.length;
			return (2 * s - (n * n) + n) / (2 * n);
		}

		private static int[] gerarProgressaoLinear(int inicio, int tamanho) {
			var resultado = new int[tamanho];
			for (int i = 0; i < tamanho; i++) {
				resultado[i] = inicio + i;
			}
			return resultado;
		}

		private static long somarProgressaoAritimetica(int primeiroTermo, int tamanho) {
			double n = tamanho;
			double a = primeiroTermo;
			double sum = (n/2) * ((2 * a ) + (n - 1));
			return (long) sum;
		}


		private static long somarSequencia(int[] sequencia) {
			long soma = 0;
			for (int i = 0; i < sequencia.length; i++) {
				soma += sequencia[i];
			}
			return soma;
		}
	}
}