2847 – List
De la Universitas MediaWiki
Cerinţa
Se dă o listă simplu înlănțuită care conține n perechi de numere naturale (a,b). Fiecare pereche este stocată în câte un nod al listei; notăm cu a primul număr stocat într-un nod și cu b al doilea număr stocat în acel nod.
Se cere să se insereze în listă astfel:
Dacă pentru nodul curent:
- a este par și b este impar se inserează după nodul curent un nou nod, care conține dublul sumei lor pe prima poziție a nodului inserat iar pe a doua poziție diferența dintre dublul sumei numerelor din nodul curent și al doilea număr din nodul curent;
- a este impar, b este par se inserează înaintea nodului curent un nou nod, care conține dublul sumei lor pe a doua poziție a nodului inserat și pe prima poziție diferența dintre dublul sumei numerelor din nodul curent și a primului număr din nodul curent;
- a este par, b este par se inserează după nodul curent un nou nod, care conține jumătatea sumei lor pe prima poziție a nodului inserat iar pe a doua poziție suma dintre jumătatea sumei numerelor din nodul curent și al doilea număr din nodul curent;
- a este impar, b este impar se inserează înaintea nodului curent un nou nod, care conține jumătatea sumei lor pe a doua poziție a nodului inserat și pe prima poziție suma dintre jumătatea sumei numerelor din nodul curent și a primului număr din nodul curent.
Date de intrare
Fișierul de intrare listin.txt conține pe prima linie numărul n, iar pe următoarele n linii n perechi de numere naturale separate prin spații.
Date de ieșire
Fișierul de ieșire listout.txt va conține pe câte o linie numerele fiecărui nod al listei separate prin spații, după realizarea inserărilor.
Restricţii şi precizări
- 1 ⩽ n ⩽ 100.000
- 1 ⩽ a ⩽ b ⩽ 100
- se recomandă utilizarea unei liste alocate dinamic
Exemplul 1
- listin.txt
5 1 2 2 4 1 1 2 6 7 4
- listout.txt
5 6 1 2 2 4 3 7 2 1 1 1 2 6 4 10 15 22 7 4
Exemplul 2
- listin.txt
100001 1 2 2 3 3 4 ... 100000 100001
- listout.txt
Datele de intrare nu corespund restrictiilor impuse
Rezolvare
class Node:
def __init__(self, a, b):
self.a = a
self.b = b
self.next = None
def insert_after(node, a, b):
new_node = Node(a, b)
new_node.next = node.next
node.next = new_node
def insert_before(head, node, a, b):
new_node = Node(a, b)
if head == node:
new_node.next = head
return new_node
else:
prev = head
while prev.next != node:
prev = prev.next
prev.next = new_node
new_node.next = node
return head
def main():
n = int(input())
sir = [list(map(int, input().split())) for _ in range(n)]
if len(sir) > 100000:
print("Datele de intrare nu corespund restrictiilor impuse")
return
head = Node(sir[0][0], sir[0][1])
node = head
for i in range(1, n):
node.next = Node(sir[i][0], sir[i][1])
node = node.next
node = head
while node:
a, b = node.a, node.b
if a % 2 == 0 and b % 2 == 1:
insert_after(node, 2*(a+b), 2*(a+b)-b)
node = node.next
elif a % 2 == 1 and b % 2 == 0:
head = insert_before(head, node, 2*(a+b)-a, 2*(a+b))
elif a % 2 == 0 and b % 2 == 0:
insert_after(node, (a+b)//2, (a+b)//2+b)
node = node.next
elif a % 2 == 1 and b % 2 == 1:
head = insert_before(head, node, (a+b)//2+a, (a+b)//2)
node = node.next
print("Datele de intrare corespund restrictiilor impuse")
node = head
while node:
print(node.a, node.b)
node = node.next
if __name__ == "__main__":
main()