0
I would like to understand an algorithm about OBI 2017 - Cutting Paper link: https://olimpiada.ic.unicamp.br/pratique/pu/2017/f2/papel/ cannot understand why at the time of making the paper cuts he used an h[1] - start % 2 module:
start = 0 if heights[0] > heights[1] else 1
max_count = 2
count = 1
for h in reversed(sorted_heights):
if (h[1] - start) % 2 == 0:
count += 1
elif h != heights[0][1] and h != heights[-1]:
count -= 1
if count > max_count:
max_count = count
Complete code:
def simplify(heights):
new_heights = []
new_heights.append([heights[0], 0])
ascending = True if heights[0] < heights[1] else False
for i in range(1, len(heights)):
actual_ascending = True if heights[i - 1] < heights[i] else False
if actual_ascending != ascending:
new_heights.append([heights[i - 1], new_heights[-1][1] + 1])
ascending = actual_ascending
if heights[-2] != heights[-1]:
print(heights[-2])
print(heights[-1])
new_heights.append([heights[-1], new_heights[-1][1] + 1])
return new_heights
if __name__ == "__main__":
# Número de retângulos
input()
# Alturas
heights = simplify([int(x) for x in input().split()])
sorted_heights = heights[:]
sorted_heights.sort()
start = 0 if heights[0] > heights[1] else 1
max_count = 2
count = 1
for h in reversed(sorted_heights):
if (h[1] - start) % 2 == 0:
count += 1
elif h != heights[0][1] and h != heights[-1]:
count -= 1
if count > max_count:
max_count = count
print(max_count)
I really appreciate anyone who can help me.
x % 2 == 0will only be true ifxfor par. That’s what you didn’t understand?– bfavaretto
This I understood, what I did not understand is why it has to be even, because it pulls the position and not the height of the rectangle, then in what is par it adds up as if it had made a cut, that which I did not understand, because it has to be par to be true and it effect a cut? For the account you have there is the cut being counted to represent the maximum number of cuts.
– Dark
Why did you remove it? That’s a good question. I intended to study the algorithm to try to answer you :)
– bfavaretto
I restored, I ended up making an amendment for not having understood this part, but I would like very much because on some occasion I could use this reasoning, I believe that it may be "incorrect" and that it worked by mere coincidence.
– Dark