Rouille, 929 923 caractères
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]}}
C'était amusant!
Commentaire sur la mise en œuvre
Donc je ne suis évidemment pas trop satisfait de la taille Mais Rust est absolument terrible au golf de toute façon. La performance, cependant, est magnifique.
Le code résout correctement chacun des cas de test en un temps quasi instantané, donc les performances ne sont évidemment pas un problème. Pour le plaisir, voici un cas de test beaucoup plus difficile:
1234567 123456 12345 1234 123 777777 77777 7777 777
pour laquelle la réponse est 82317, que mon programme a pu résoudre sur mon ordinateur portable (de performance moyenne) en 1,66 seconde (!), même avec l'algorithme récursif de chemin hamiltonien à force brute.
Observations
Nous devons d'abord construire un graphique pondéré modifié, les nœuds étant chaque numéro "chanceux" et les poids étant le nombre de changements nécessaires pour passer d'un niveau de réputation à un autre. Chaque paire de nœuds doit être connectée par deux fronts, car monter n'est pas la même chose que descendre en valeur de réputation (vous pouvez obtenir +10, par exemple, mais pas -10).
Maintenant, nous devons trouver comment trouver le minimum de changements d'une valeur de répétition à l'autre.
Pour passer d'une valeur supérieure à une valeur inférieure, c'est simple: il suffit de prendre ceil((a - b) / 2)où aest la valeur supérieure et bla valeur inférieure. Notre seule option logique est d'utiliser le -2 autant que possible, puis le -1 une fois si nécessaire.
Une valeur faible à élevée est un peu plus compliquée, car l'utilisation de la plus grande valeur possible n'est pas toujours optimale (ex. Pour 0 à 9, la solution optimale est +10 -1). Cependant, il s'agit d'un problème de programmation dynamique de manuels, et un simple DP suffit pour le résoudre.
Une fois que nous avons calculé les changements minimums de chaque numéro à chaque autre numéro, nous nous retrouvons essentiellement avec une légère variante de TSP (problème du voyageur de commerce). Heureusement, il y a un nombre suffisamment petit de nœuds (un maximum de 5 dans le cas de test le plus difficile) que la force brute est suffisante pour cette étape.
Code non golfé (fortement commenté)
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]. Votre solution pourrait probablement en bénéficier.Pyth -
4342 octetsUtilise une approche complètement brutale avec toutes les permutations et combinaisons.
Ne cherchez plus à jouer au golf car cela se traduira par Pyth.Traduit.C'est encore plus lent que la version python car j'utilise un filtre au lieu d'une boucle while. Explication à venir, regardez maintenant le code Python.
Essayez-le ici en ligne .
Fonctionne sur les petits, ne l'a pas laissé se terminer sur les grands.
la source
y5pour économiser sur les espaces?K=5C ++ - 863 octets, non golfé
Cela fonctionne assez rapidement, dans le même stade que la solution écrite en Rust (environ 6 fois plus rapide lors de la compilation avec l'optimisation activée). Je jouerai au golf plus tard ce soir (soirée en Suède, c'est-à-dire).
la source