Rust, 929 923 karakter
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]}}
Ini sangat menyenangkan!
Komentar tentang implementasi
Jadi saya jelas tidak terlalu senang dengan ukurannya. Tetapi Rust juga sangat buruk dalam bermain golf. Namun, kinerjanya luar biasa.
Kode memecahkan setiap kasus uji dengan benar dalam waktu yang hampir seketika, sehingga kinerja jelas bukan masalah. Untuk bersenang-senang, inilah ujian yang jauh lebih sulit:
1234567 123456 12345 1234 123 777777 77777 7777 777
jawabannya adalah 82317, yang dapat diselesaikan oleh program saya pada laptop (kinerja sedang) saya dalam 1,66 detik (!), bahkan dengan algoritma jalur Hamiltonian brute-force rekursif.
Pengamatan
Pertama, kita harus membuat grafik berbobot yang dimodifikasi, dengan simpulnya masing-masing angka "beruntung" dan bobotnya adalah berapa banyak perubahan yang diperlukan untuk berpindah dari satu tingkat reputasi ke tingkat lainnya. Setiap pasangan node harus dihubungkan oleh dua sisi, karena naik tidak sama dengan turun dalam nilai reputasi (Anda bisa mendapatkan +10, misalnya, tetapi tidak -10).
Sekarang kita perlu mencari cara untuk menemukan jumlah minimum perubahan dari satu nilai rep ke yang lain.
Untuk mendapatkan dari nilai yang lebih tinggi ke nilai yang lebih rendah, itu sederhana: ambil saja di ceil((a - b) / 2)mana anilai lebih tinggi danb yang lebih rendah. Satu-satunya pilihan logis kami adalah menggunakan -2 sebanyak mungkin, dan -1 jika perlu.
Nilai rendah ke tinggi sedikit lebih rumit, karena menggunakan nilai terbesar yang mungkin tidak selalu optimal (mis. Untuk 0 hingga 9, solusi optimal adalah +10 -1). Namun, ini adalah masalah pemrograman buku dinamis, dan DP sederhana sudah cukup untuk menyelesaikannya.
Setelah kami menghitung perubahan minimum dari setiap angka ke setiap angka lainnya, kami pada dasarnya dibiarkan dengan sedikit varian TSP (masalah salesman keliling). Untungnya, ada jumlah node yang cukup kecil (maksimum 5 pada test case yang paling sulit) sehingga brute force cukup untuk langkah ini.
Kode tidak dikunci (banyak komentar)
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]. Solusi Anda mungkin dapat mengambil manfaat dari ini.Pyth -
4342 byteMenggunakan pendekatan brute force sepenuhnya dengan semua permutasi dan kombinasi.
Tidak ingin bermain golf lagi karena akan menerjemahkan ke Pyth.DiterjemahkanIni bahkan lebih lambat daripada versi python karena saya menggunakan filter daripada loop sementara. Penjelasan segera hadir, sekarang lihat kode Python.
Coba di sini online .
Bekerja pada yang kecil, tidak membiarkannya selesai pada yang besar.
sumber
y5untuk menghemat ruang kosong?K=5C ++ - 863 bytes, tidak diserang
Ini berjalan cukup cepat, di stadion baseball yang sama dengan solusi yang ditulis dalam Rust (sekitar 6 kali lebih cepat ketika kompilasi dengan optimasi dihidupkan). Saya akan bermain golf nanti malam ini (malam di Swedia).
sumber