(Part 1: Problem D) (Part 2: Problem A)

After the disaster solving A-large, it became clear that I needed to do more than 2 problems to get an advancing score. But also both B and C seemed likely to be impossible in the languages I wanted. But I still didn't want to use my normal languages. I mean at least B-small seemed quite obvious. A typical problem we can solve with memoization. If we set the state to be equal to an array of 9 elements containing the number of eaters that have 1, 2, ... 9 pancakes. We need to notice that it never makes sense to create a plate that has more pancakes than the original plate from which we took the pancakes. Otherwise each minute just shifts the array...

Anyway, I decided to look for a new language to learn. But something a bit more usable than the other two. I tried Julia. It actually felt like cheating, because it turns out this is a pretty good language. There's a couple of things I don't like, like the 1-indexing. But it was overall a nice experience. Similar to python but with some differences. And apparently benchmarks say it is a bit faster. You can also make it less dynamically typed if needed. Anyway:

function solve(P) mem = Dict() function f(seq) if haskey(mem, seq) return mem[seq] end #println(seq) res = 1000000000 if count(x -> (x != 0), seq) == 0 # all zeros, base case res = 0 else # let one minute go: a = [ seq[i] for i = [2:9] ] push!(a, 0) res = 1 + f(a) # move something: for i = [2:9] if seq[i] > 0 for j = [1:i-1] #if j != div(i , 2) # continue #end for k = [1 : i - j - 1] if seq[k] > 0 b = [x for x = seq] b[k] -= 1 b[k + j] += 1 b[i] -= 1 b[i - j] += 1 res = min(res, 1 + f(b) ) end end # move to empty plate if i - j < i b = [x for x = seq] b[j] += 1 b[i - j] += 1 b[i] -= 1 res = min(res, 1 + f(b) ) end end end end end mem[seq] = res #print (seq) #print (" = ") #println(res) return res end seq = [ count(x -> x==i, P) for i = [1:9] ] return f(seq) end s = int(readline(STDIN)) for i = [1: s] n = int(readline(STDIN)) q = split(readline(STDIN), " " ) P = map( x -> int(x) , q) @printf "Case #%d: %d\n" i solve(P) end

Coding this was easy except for googling how to do things. The logic I learned when learning python really helped.

## No comments :

Post a Comment