Óxido, 929 923 caracteres
use std::io;use std::str::FromStr;static C:&'static [i32]=&[-2,-1,2,5,10,15];fn main(){let mut z=String::new();io::stdin().read_line(&mut z).unwrap();let n=(&z.trim()[..]).split(' ').map(|e|i32::from_str(e).unwrap()).collect::<Vec<i32>>();let l=*n.iter().min().unwrap();let x=n.iter().max().unwrap()-if l>1{1}else{l};let s=g(x as usize);println!("{}",p(1,n,&s));}fn g(x:usize)->Vec<i32>{let mut s=vec![std::i32::MAX-9;x];for c in C{if *c>0&&(*c as usize)<=x{s[(*c-1)as usize]=1;}}let mut i=1us;while i<x{let mut k=i+1;for c in C{if(i as i32)+*c<0{continue;}let j=((i as i32)+*c)as usize;if j<x&&s[j]>s[i]+1{s[j]=s[i]+1;if k>j{k=j;}}}i=k;}s}fn p(r:i32,n:Vec<i32>,s:&Vec<i32>)->i32{if n.len()==1{h(r,n[0],&s)}else{(0..n.len()).map(|i|{let mut m=n.clone();let q=m.remove(i);p(q,m,&s)+h(r,q,&s)}).min().unwrap()}}fn h(a:i32,b:i32,s:&Vec<i32>)->i32{if a==b{0}else if a>b{((a-b)as f32/2f32).ceil()as i32}else{s[(b-a-1)as usize]}}
¡Esto fue divertido!
Comentario sobre la implementación
Así que obviamente no estoy muy contento con el tamaño. Pero Rust es absolutamente terrible en el golf de todos modos. El rendimiento, sin embargo, es maravilloso.
El código resuelve cada uno de los casos de prueba correctamente en una cantidad de tiempo casi instantánea, por lo que el rendimiento obviamente no es un problema. Por diversión, aquí hay un caso de prueba mucho más difícil:
1234567 123456 12345 1234 123 777777 77777 7777 777
para lo cual la respuesta es 82317, que mi programa pudo resolver en mi computadora portátil (rendimiento medio) en 1.66 segundos (!), incluso con el algoritmo recursivo de ruta Hamiltoniana de fuerza bruta.
Observaciones
Primero deberíamos construir un gráfico ponderado modificado, con los nodos siendo cada número "afortunado" y los pesos son cuántos cambios se necesitan para pasar de un nivel de reputación a otro. Cada par de nodos debe estar conectado por dos bordes, ya que subir no es lo mismo que bajar en valor de reputación (puede obtener +10, por ejemplo, pero no -10).
Ahora necesitamos descubrir cómo encontrar la cantidad mínima de cambios de un valor de repetición a otro.
Para pasar de un valor más alto a un valor más bajo, es simple: simplemente tome ceil((a - b) / 2)donde aestá el valor más alto y bel valor más bajo. Nuestra única opción lógica es usar el -2 tanto como sea posible, y luego el -1 una vez si es necesario.
Un valor bajo a alto es un poco más complicado, ya que usar el mayor valor posible no siempre es óptimo (por ejemplo, de 0 a 9, la solución óptima es +10 -1). Sin embargo, este es un problema de programación dinámica de un libro de texto, y un DP simple es suficiente para resolverlo.
Una vez que hemos calculado los cambios mínimos de cada número a cualquier otro número, esencialmente nos queda una ligera variante de TSP (problema de vendedor ambulante). Afortunadamente, hay un número suficientemente pequeño de nodos (un máximo de 5 en el caso de prueba más difícil) que la fuerza bruta es suficiente para este paso.
Código no protegido (muy comentado)
use std::io;
use std::str::FromStr;
// all possible rep changes
static CHANGES: &'static [i32] = &[-2, -1, 2, 5, 10, 15];
fn main() {
// read line of input, convert to i32 vec
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let nums = (&input.trim()[..]).split(' ').map(|x| i32::from_str(x).unwrap())
.collect::<Vec<i32>>();
// we only need to generate as many additive solutions as max(nums) - min(nums)
// but if one of our targets isn't 1, this will return a too-low value.
// fortunately, this is easy to fix as a little hack
let min = *nums.iter().min().unwrap();
let count = nums.iter().max().unwrap() - if min > 1 { 1 } else { min };
let solutions = generate_solutions(count as usize);
// bruteforce!
println!("{}", shortest_path(1, nums, &solutions));
}
fn generate_solutions(count: usize) -> Vec<i32> {
let mut solutions = vec![std::i32::MAX - 9; count];
// base cases
for c in CHANGES {
if *c > 0 && (*c as usize) <= count {
solutions[(*c-1) as usize] = 1;
}
}
// dynamic programming! \o/
// ok so here's how the algorithm works.
// we go through the array from start to finish, and update the array
// elements at i-2, i-1, i+2, i+5, ... if solutions[i]+1 is less than
// (the corresponding index to update)'s current value
// however, note that we might also have to update a value at a lower index
// than i (-2 and -1)
// in that case, we will have to go back that many spaces so we can be sure
// to update *everything*.
// so for simplicity, we just set the new index to be the lowest changed
// value (and increment it if there were none changed).
let mut i = 1us; // (the minimum positive value in CHANGES) - 1 (ugly hardcoding)
while i < count {
let mut i2 = i+1;
// update all rep-values reachable in 1 "change" from this rep-value,
// by setting them to (this value + 1), IF AND ONLY IF the current
// value is less optimal than the new value
for c in CHANGES {
if (i as i32) + *c < 0 { continue; } // negative index = bad
let idx = ((i as i32) + *c) as usize; // the index to update
if idx < count && solutions[idx] > solutions[i]+1 {
// it's a better solution! :D
solutions[idx] = solutions[i]+1;
// if the index from which we'll start updating next is too low,
// we need to make sure the thing we just updated is going to,
// in turn, update other things from itself (tl;dr: DP)
if i2 > idx { i2 = idx; }
}
}
i = i2; // update index (note that i2 is i+1 by default)
}
solutions
}
fn shortest_path(rep: i32, nums: Vec<i32>, solutions: &Vec<i32>) -> i32 {
// mercifully, all the test cases are small enough so as to not require
// a full-blown optimized traveling salesman implementation
// recursive brute force ftw! \o/
if nums.len() == 1 { count_changes(rep, nums[0], &solutions) } // base case
else {
// try going from 'rep' to each item in 'nums'
(0..nums.len()).map(|i| {
// grab the new rep value out of the vec...
let mut nums2 = nums.clone();
let new_rep = nums2.remove(i);
// and map it to the shortest path if we use that value as our next target
shortest_path(new_rep, nums2, &solutions) + count_changes(rep, new_rep, &solutions)
}).min().unwrap() // return the minimum-length path
}
}
fn count_changes(start: i32, finish: i32, solutions: &Vec<i32>) -> i32 {
// count the number of changes required to get from 'start' rep to 'finish' rep
// obvious:
if start == finish { 0 }
// fairly intuitive (2f32 is just 2.0):
else if start > finish { ((start - finish) as f32 / 2f32).ceil() as i32 }
// use the pregenerated lookup table for these:
else /* if finish > start */ { solutions[(finish - start - 1) as usize] }
}
<!-- language-all: lang-rust -->. ;)floor((a-b)/15)+{0,2,1,2,2,1,3,2,2,2,1,3,2,2,2}[(a-b)%15]. Su solución probablemente podría beneficiarse de esto.Pyth -
4342 bytesUtiliza un enfoque de fuerza bruta completa con todas las permutaciones y combinaciones.
No busco más golf porque se traducirá a Pyth.Traducido.Esto es incluso más lento que la versión de Python porque uso filtro en lugar de un ciclo while. Explicación próximamente, ahora mira el código de Python.
Pruébalo aquí en línea .
Funciona en los pequeños, no dejó que se ejecute hasta su finalización en los grandes.
fuente
y5para ahorrar en espacios en blanco?K=5C ++ - 863 bytes, sin golf
Esto funciona bastante rápido, en el mismo estadio que la solución escrita en Rust (aproximadamente 6 veces más rápido cuando se compila con la optimización activada). Jugaré golf más tarde esta tarde (tarde en Suecia, claro).
fuente