Winner Ave (More tricks)

2003-04-08 00:00:00 UTC

Complex tweek 10

Status: Passed
Results: 2532.430K raw score
CPU Time: 83.41
Score: 2541.68
Submitted at: 2003-04-02 16:25:59 UTC
Scored at: 2003-04-02 16:57:19 UTC

Current Rank: 1221st
Basis for: Complex tweek 11 (diff)

Code
function c = solver(a)

n=size(a,1);

v=a(:,1)+i*a(:,2);
if n<10
c=findenum(a,a(1,4),v);
return
end
freightv=a(:,3);
petrolv=a(:,4);

petrol=0;
freight=0;

pos=1;
jdest=1;

freightn=freightv/sum(freightv);
petroln=petrolv/sum(petrolv);

petrol  = petrol +  petrolv(1);
freight = freight + freightv(1);
petrolv(1)=0; freightv(1)=-1;

beenthere=logical(zeros(n,1));
beenthere(1)=true;
c=zeros(1,n);
c(1)=1;
next=1;

while(next)
jdest=jdest+1;
dpos=abs(v-v(pos));
possible = find(  ...
(petrol + petrolv  >=  dpos + abs(v-v(1)))  & ...
(petrol >= dpos )  & ~beenthere);
if (isempty(possible))
break
end

metric = (2*petroln(possible) + freightn(possible)) ./ abs(v(pos)-v(possible));
[maxm,imax]=max(metric);

next=possible(imax(1));
c(jdest)=next;
petrol=petrol + petrolv(next) - abs(v(pos)-v(next));
freight=freight+freightv(next);
pos=next;
beenthere(pos)=true;
%fprintf(1,'\njdest=%d, next=%d, petrol=%f, freight=%f',jdest,next,petrol,freight);
end

c(jdest)=1;
c=c(1:jdest);

function [c,x]=findenum1(a,gas,coord,current,g,f,c)

coord0=coord(current);
gas=gas+a(current,4);	% free gas
g=g+a(current,4);	% total gas
coord(current)=inf;
dist=abs(coord-coord0);
reachable=find(dist<=gas);
if isempty(reachable)
c=[];
x=[];
return
end

f=f+a(current,3);

if reachable(1)==1
i1=2;
x=f-g;
cm=[c 1];
else
i1=1;
x=inf;
end

for i=i1:length(reachable)
nw=reachable(i);
[c1,x1]=findenum1(a,gas-dist(nw),coord,nw,g,f,[c nw]);
if ~isempty(c1)
if x1>x
cm=c1;
x=x1;
end
end
end
if isinf(x)
c=[];
else
c=cm;
end

function c=findenum(a,gas,coord)

current=1;

dist=abs(coord-coord(current));
reachable=find(dist<=gas);
c=[1 1];
if isempty(reachable)
return
end
x=0;
for i=2:length(reachable)
nw=reachable(i);
[c1 x1]=findenum1(a,gas-dist(nw),coord,nw,0,0,[1 nw]);
if ~isempty(c1)
if x1>x
c=c1;
x=x1;
end
end
end
if c(end)~=1
c(end+1)=1;
end