Gincana - Programação

[Brandt]

@Hudell quase, mas ainda não foi a solução correta. Por exemplo, com { 1, 2, 3, 6, 13 } o seu programa particiona em { 2, 3, 6 } e { 1, 13 }, fica 11/14, que não é ótimo (o melhor seria { 1, 2, 3, 6 } e { 13 }, com 12/13 e uma diferença de apenas 1).

Fiz uma solução recursiva em haskell aqui pra demonstrar como faria com bruteforce:

partition :: [Int] -> ([Int], [Int])
partition p = partitionRec p 0
    where
        s = sum p
        upperHalf = s - s `div` 2
       
        partitionRec :: [Int] -> Int -> ([Int], [Int])
        partitionRec [] _ = ([], [])
        partitionRec (x:xs) s
            | x + s > upperHalf = ignore
            | sum (fst ignore) > sum (fst pick) = ignore
            | otherwise = pick
            where
                ignore = case partitionRec xs s of
                    (a, b) -> (a, x:b)

                pick = case partitionRec xs (s + x) of
                    (a, b) -> (x:a, b)

main = putStrLn $ show $ partition [1, 2, 3, 6, 13]

Dá pra otimizar bem: o sum ali percorre a lista toda, dava pra fazer em tempo constante, mas é só pra passar a ideia mesmo. Pra fazer do jeito mais performático os tipos das funções iam ficar meio conturbados :d

A ideia é, pra cada elemento, decidir se ele vai ou não na primeira lista de forma a maximizar o valor da primeira lista sem estourar o limite de metade da soma (arredondado pra cima ou pra baixo, tanto faz, só muda qual das partições fica maior em caso de não ser possível dividir por igual). Por isso a complexidade é O(2^n), é equivalente a gerar todas as combinações de True e False para cada elemento da lista e fazer um teste (idealmente, em tempo constante, que não é o caso da minha ali, mas enfim...). Como tem 2^n possíveis combinações de 0 e 1 pra n "bits", fica a complexidade exponencial aí.

 

[Hudell]

Esqueci de considerar essa possibilidade, mas foi só um pequeno ajuste no meu código mesmo.

Pra eu não ficar atrapalhando ainda mais a thread, esse é o desafio mais recente aqui:

TEMA: Faça um programa que te solicita a inserir uma nota de 0 a 10 para cada bimestre. O sistema não deve permitir notas abaixo de 0 e acima de 10 fornecidas pelo usuário. Caso isso aconteça, o sistema deve solicitar novamente um outra nota até que a mesma for validada dentro desta regra.
Feito isso, o sistema deve calcular a média aritmética ponderada e escrever a nota média do aluno naquele ano.

 

[Brandt]

Esqueci de considerar essa possibilidade, mas foi só um pequeno ajuste no meu código mesmo.

Nah, tem bastante coisa lá que não faz parte da solução (ordenar, máximo e mínimo, umas condições aqui e ali), e continua incorreta: com P = [1, 2, 5, 5, 19, 21, 52, 17], você divide em [1, 2, 5, 5, 19, 21] e [52, 17], fica 53/69, com diferença de 16. Uma partição melhor seria [1, 2, 5, 52], [5, 19, 21, 17], com separação 60/52, e diferença 8.

Também tem a questão da complexidade, como você repete a recursão pra cada elemento à frente do atual no vetor (estou assumindo que o return incondicional ali foi engano, btw), sua relação de recorrência fica T = O(1) + (n - 1) T(n - 1) (estou deixando O(1) ali ao invés de O pelo reduce pra pegar a soma porque fiz a mesma coisa na análise da minha ali em cima, e a assintótica fica igual anyway), fica em O(n!), que ainda é exponencial, mas cresce bem mais rápido que O(2^n).

A lógica até que está parecida (por isso disse que foi quase), mas não está bem certa.

Eu acho que comentar as soluções faz parte da ideia da gincana (apesar que ter trazido um problema NP-difícil talvez tenha sido um pouco anti-esportivo, justo haha), então nem vou pedir desculpa por postar sem fazer um tema não. Mas pra não ficar atrapalhando a thread, esse é o desafio mais recente aqui:

TEMA: Faça um programa que te solicita a inserir uma nota de 0 a 10 para cada bimestre. O sistema não deve permitir notas abaixo de 0 e acima de 10 fornecidas pelo usuário. Caso isso aconteça, o sistema deve solicitar novamente um outra nota até que a mesma for validada dentro desta regra.
Feito isso, o sistema deve calcular a média aritmética ponderada e escrever a nota média do aluno naquele ano.

 

[Hudell]

Ah, realmente. A ideia que eu tinha na cabeça era pra testar todas as possibilidades e ver qual a mais próxima, mas do jeito que eu implementei ele tá pulando algumas.

 

[Takki]

Resetando o desafio já que bem chegamos a um impasse.

TEMA: Anagramas, pegue uma palavra ou frase e gere todos os anagramas possíveis o resultado deve ser mostrado em múltiplas linhas.

 

[Brandt]

@Dr.XGB PHP é sacanagem hein. Faltou o ?> no final, e PHP não é compilado, então QUASE COMPILA. (Peguei a pegadinha? auehaueh)

TEMA: Faça um programa que te solicita a inserir uma nota de 0 a 10 para cada bimestre. O sistema não deve permitir notas abaixo de 0 e acima de 10 fornecidas pelo usuário. Caso isso aconteça, o sistema deve solicitar novamente um outra nota até que a mesma for validada dentro desta regra.
Feito isso, o sistema deve calcular a média aritmética ponderada e escrever a nota média do aluno naquele ano.

PESOS = [1, 2, 3]
notas = []

for i in range(1, 4):
  print i, "semestre"
  while True:
    n = int(input())
    if not 0 <= n <= 10:
      print("Nota invalida")
      continue
    notas.append(n)
    break

media = sum(p * x for (p, x) in zip(PESOS, notas)) / float(sum(PESOS))
print "Media:", media

Deixei os pesos numa constante ali e fiz trimestral, mas acho que tá valendo haha

---

Resetando o desafio já que bem chegamos a um impasse.

TEMA: Anagramas, pegue uma palavra ou frase e gere todos os anagramas possíveis o resultado deve ser mostrado em múltiplas linhas.

@Takkun

puts gets.chomp.chars.permutation.map(&:join).map(&:strip).to_a

---

TEMA: Ctrl + Z, Ctrl + Shift + Z