TOPIC
PROBLEM 1966 - URI Fórum 1.0
This topic was solved and cannot recieve new replies.
-
Lucas Berg replied 5 years ago
MODGabriel eu usei uma fórmula parecida com essa, só que quando eu fui deduzindo ela eu achei:
BlocosBase = (-1 + sqrt(1 + 8 * BlocosTotal)) / 2 <-- Sai de uma fórmula de PA
Eu consegui Accepted fazendo essa conta e considerando que o problema é quase um problema da mochila, só que neste aqui daria para eu "quebrar" os objetos.
-
João replied 4 years ago
Você não precisa pegar a peça de queijo inteira, pode pegar só o que você precisa. Esse exercício é guloso.
-
André Luiz Bittencourt replied 4 years ago
Amigo me explica o que seria a parte de "quebrar" os objetos ? Eu usei o algoritmo da mochila normal... e ganhei 50 %....
-
Gabriel Duarte replied 5 years ago
MODValeu! Acabei de passar aqui, realmente é o problema da mochila fracionário, o que estava faltando pra mim era essa fórmula. :D
EDIT: Na verdade estava certo o que eu pensei, só que eu esqueci que no denominador da primeira fórmula tinha um 2 xD. Se eu tivesse usado seria: BlocosBase = (-1 + sqrt(1 + 4 2 BlocosTotal)) / 2
-
Gabriel Duarte replied 5 years ago
MODExiste alguma fórmula matemática em que dado o numero de blocos ela me retorne o total da base ?
Consegui perceber que se eu tenho uma base com N elementos então o número total de blocos usados será: (N (N + 1)) / 2 - Tendo essa informação eu consigo pensar no inverso da fórmula que seria: BlocosBase = (-1 + sqrt(1 + 4 BlocosTotal)) / 2 Só que ela não tem um comportamento muito legal quando eu irei utilizar todos os blocos.
Alguma dica?