21

Navegando pela internet a procura de desafios (para serem resolvidos com programação), achei o "Treze homens e um carregamento", onde dito que faz parte dos desafios aleatórios da NSA (link).


O desafio

Após sua última viagem, os 13 piratas do navio Turing se reúnem em sua taberna favorita para discutir como irão dividir um baú de moedas de ouro. Depois de muito debate, o capitão Códigus diz: “Arrrrrrrgh, o carregamento precisa ser distribuído igualmente entre nós”. E assim é feito. O capitão dá as moedas, uma por uma, e cada pirata aguarda ansioso sua recompensa. Conforme o capitão se aproxima do final da pilha, porém, ele percebe que há três moedas a mais.

Após um silencio breve e constrangedor, um dos piratas diz: “eu mereço uma moeda extra porque eu carreguei o navio enquanto o resto de vocês dormia”. Outro afirma: “Bem, eu mereço uma moeda extra porque cozinhei toda a comida ao longo da viagem”. Logo começa uma intensa troca de chutes, socos e garrafadas pela posse do dinheiro restante. O dono do estabelecimento, irritado com a bagunça, expulsa um pirata particularmente violento que havia quebrado uma mesa, e ele é obrigado a devolver todas as suas moedas para o grupo. É dado o aviso: “ou vocês ficam em paz ou todos serão expulsos daqui!”.

Os piratas voltam a seus lugares e o capitão, que ficou com apenas 12 piratas, continua a distribuir as moedas. “Uma para você... Outra para você.” Agora, quando a pilha está próxima do fim, ele percebe que há cinco moedas sobrando. Começa uma nova briga. O capitão, com medo de que sejam expulsos do local, manda o pirata mais estressado embora. Agora, com apenas 11 membros, a divisão dá certo, cada um recebe a mesma quantidade de moedas e todos vão dormir em paz.

Considerando que houvesse menos de 1000 moedas, quantas moedas os piratas dividiram entre si? Só há uma resposta possível para um valor abaixo de 1000.


Partindo da ideia em resolver e sabendo que haveriam vários valores a serem calculados, brevemente fiz em php para tentar a solução (claro, sem ler o resultado, para não perder a graça), e felizmente deu certo:

<?php

// 11 piratas, sobra 0
$piratas_11 = array();

$max_moedas = 1000;
while($max_moedas > 0) {

    if($max_moedas%11 == 0){
    
        array_push($piratas_11, $max_moedas);
    }

    $max_moedas--;
}


// 12 piratas, sobra 5
$piratas_12 = array();

foreach($piratas_11 as $v) {
    
    if($v%12 == 5){
    
        array_push($piratas_12, $v);
    }
}


// 13 piratas, sobra 3
$piratas_13 = array();

foreach($piratas_12 as $v) {
    
    if($v%13 == 3){
    
        array_push($piratas_13, $v);
    }
}

echo '<pre>';
print_r($piratas_13);

Resultado:

Array
(
    [0] => 341
)

Não tentei fazer de outras formas, então:

O que gostaria, é saber como vocês fariam, se há uma forma de solução mais curta e eficiente, usando ou não outras funções, etc.

Acredito que sempre há uma forma de dar mais eficiência ao código, e nisso sempre aprendo bastante.

2
  • Haha, só um momento, vou tentar aqui também 19/03/2018 às 1:38
  • Eu não consegui ver uma implementação melhor, pois, você pega os valores possíveis menores que 1000 de 11 piratas que restarão 0. E a partir de então você consegue descobrir o número exato testando por outros valores dos outros pitaras. Ótima ideia! Parabéns! 19/03/2018 às 2:07

3 Respostas 3

23

Você consegue fazer isso com apenas um laço de repetição. Considerando que eles possuem N moedas, quando é dividido entre 13 piratas, sobram 3 moedas, o que significa que N-3 é múltiplo de 13 e, portanto, N-3 % 13 = 0; quando dividido por 12 piratas, sobram 5 moedas, portanto N-5 é múltiplo de 12, o que implica em N-5 % 12 = 0; por fim, quando dividido em 11 piratas, não sobram moedas, e, portanto, N é múltiplo de 11, N % 11 = 0. O valor de N será aquele que satisfaz as três condições e é menor que 1000.

foreach(range(0, 1000, 11) as $i) {
    if (($i - 3) % 13 == 0 and ($i - 5) % 12 == 0 and ($i % 11) == 0) {
        echo $i, PHP_EOL;
        break;
    }
}

Veja funcionando no Repl.it | Ideone

Perceba que, sabendo que o resultado será, necessariamente, múltiplo de 11, não precisamos percorrer todos os valores de 0 a 1000, mas apenas os múltiplos de 11, por isso o terceiro parâmetro de range foi definido como tal.

5
  • 1
    Bem pensado.. +1 19/03/2018 às 2:27
  • Muito bom, na hora nem me passou usar o and. Fiz update na pergunta.
    – rbz
    19/03/2018 às 12:07
  • +1 pela sacada de usar um step de 11. 28/09/2018 às 21:14
  • 1
    Talvez seja micro-otimização, mas se o range já usa um step de 11, não precisa testar $i % 11 (sempre será zero). E como sabemos que com 12 e 13 piratas sobraram moedas, então dá para assumir que há mais que 11 moedas (senão teria faltado e não sobrado), e por isso o range poderia começar em 22 :-)
    – hkotsubo
    5/04/2021 às 13:31
  • 1
    @hkotsubo exato, lembro que na época eu cheguei a cogitar isso, mas optei em deixar o código mais de acordo com o texto possível para simplificar o entendimento.
    – Woss
    5/04/2021 às 13:40
7

Por enquanto a minha versão melhorada com base no geral, com foco no mínimo de variáveis e funções:

for ($c = 1000; $c > 0; $c--)
    if (($c%11 == 0) && ($c%12 == 5) && ($c%13 == 3))
        echo $c;
4

$max = 1000;

while ($max > 0) {

    if($max%11 == 0 && ($max-5)%12 == 0 && ($max-3)%13 == 0){
        echo $max;
    }

    $max--;
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .