16 martie 2016

Code jam, for women (solutiile mele, #1)

Problema 1) link

Enunt
Cody are mai multe produse in magazin si vrea sa faca o reducere de 75%. Ea tipareste niste etichete atat pt preturile vechi cat si pt cele noi, dar comanda ii vine cu preturile amestecate, de la cel mai mic la cel mai mare, iar ea trebuie sa gaseasca perechile (pret nou, pret vechi).

Idee
2 pointeri p1 si p2, unul aflat la inceput (pe pretul minim, care mereu va fi cel la reducere), iar altul flotant, in cautarea originalului de la pretul redus. Pointerii se misca pana cand ajung la celalalt capat.

Rezolvare (Python)

f = open("A-large-practice.in", 'r')
T = eval(f.readline())

for i in range (T):
N = eval(f.readline())
v = f.readline().split(' ')
p1 = 0
p2 = 1
print("Case #", i+1, ": ", sep="", end="")
while (p1 < 2*N):
nr = 4/3 * eval(v[p1]) # the previous price value
while (eval(v[p2]) < nr):
p2 += 1 # put p2 there
print(v[p1], " ", sep="", end="")
v[p2] = "-1" # mark as visited by p2
# reposition p1
p1 += 1
while (p1 < 2*N and eval(v[p1]) == -1):
p1 += 1 # skip where p2 already was positioned
print()