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
Datele de intrare corespund restrictiilor impuse 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, next_node=None):
self.a = a
self.b = b
self.next_node = next_node
def insert_after(node, a, b):
new_node = Node(a, b, node.next_node)
node.next_node = new_node
def insert_before(head, prev_node, node, a, b):
new_node = Node(a, b, node)
if prev_node is None:
return new_node
else:
prev_node.next_node = new_node
return head
def main():
with open('listin.txt', 'r') as fin, open('listout.txt', 'w') as fout:
n = int(fin.readline().strip())
if n < 1 or n > 100000:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
a, b = map(int, fin.readline().strip().split())
if a < 1 or a > 100 or b < 1 or b > 100:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
head = Node(a, b)
node = head
for _ in range(n-1):
a, b = map(int, fin.readline().strip().split())
if a < 1 or a > 100 or b < 1 or b > 100:
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
node.next_node = Node(a, b)
node = node.next_node
fout.write("Datele de intrare corespund restrictiilor impuse\n")
prev = None
node = head
while node is not None:
if node.a % 2 == 0 and node.b % 2 == 1:
insert_after(node, 2*(node.a+node.b), 2*(node.a+node.b)-node.b)
elif node.a % 2 == 1 and node.b % 2 == 0:
head = insert_before(head, prev, node, 2*(node.a+node.b)-node.a, 2*(node.a+node.b))
elif node.a % 2 == 0 and node.b % 2 == 0:
insert_after(node, (node.a+node.b)//2, (node.a+node.b)//2+node.b)
elif node.a % 2 == 1 and node.b % 2 == 1:
head = insert_before(head, prev, node, (node.a+node.b)//2+node.a, (node.a+node.b)//2)
prev = node
node = node.next_node
node = head
while node is not None:
fout.write(str(node.a) + ' ' + str(node.b) + '\n')
node = node.next_node
if __name__ == "__main__":
main()