Computer Science Canada :: View topic

var stream : int
var str : string

open : stream, "s5.in", get
get : stream, str
var t : int := strint (str)

var scorearray : flexible array 1 .. 0 of int
proc calc (w : int, balls : int, pin : array 1 .. * of int, score : int, mem : int)
var switch : boolean := false
var totalscore : int := score
var ballsLeft := balls - 1
var pinsLeft : array 1 .. upper (pin) of int

if mem + 1 <= upper (pin) then
for i : mem + 1 .. upper (pin)
for z : 1 .. upper (pin)
pinsLeft (z) := pin (z)
end for
for h : 0 .. w - 1
if (i + h) >= 1 and (i + h) <= upper (pinsLeft) then
totalscore += pinsLeft (i + h)
%put totalscore

pinsLeft (i + h) := 0

end if
end for
% if ballsLeft = 0 then
% for h : 1 .. upper (pin)
% put pinsLeft (h), " " ..
% end for
% put ""
% put ""
% end if
%put ballsLeft
if ballsLeft > 0 then
calc (w, ballsLeft, pinsLeft, totalscore, mem + 1)
else
new scorearray, upper (scorearray) + 1
scorearray (upper (scorearray)) := totalscore
end if
totalscore := score
end for
else
new scorearray, upper (scorearray) + 1
scorearray (upper (scorearray)) := totalscore
end if
end calc

for i : 1 .. t
get : stream, str
var n : int := strint (str)
get : stream, str
var k : int := strint (str)
get : stream, str
var w : int := strint (str)
%put n, " ", k, " ", w, " "
var data : array 1 .. n of int
for h : 1 .. n
get : stream, str
data (h) := strint (str)
end for
calc (w, k, data, 0, 1 - (w - 1) - 1)
var maxscore : int := 0

for h : 1 .. upper (scorearray)
maxscore := max (scorearray (h), maxscore)
end for
put maxscore
end for

Author:	Tony [ Thu Nov 01, 2007 8:12 pm ]
Post subject:	RE:s5 2007
umm.. Quote: for h : 1 .. upper (scorearray) maxscore := max (scorearray (h), maxscore) end for You're calculating every possible score in there? It's Pins nCr Balls combinations. Assuming Pins >>> Balls: (Pins - Balls)^Balls will give you a conservative estimate of the value. So it could be over 29500^500. That's a lot. So it should be clear that you're not supposed to try everything. -------- A hint comes in a form of Bob's strategy for going after the highest scoring shot, one at a time. That's very easy to do, even in O(N^2) sort, 30,000^2 is <<< 29500^500. Supposedly this will give you the correct answer 20% of the time, and be fairly close the rest of the time. This should be your starting case, not 0. I think that checking if any particular shot will improve/worsen Bob's strategy on the remainder, should give you the answer in O(N^3) time.