2847 – List: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == 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 po...
 
No edit summary
Line 18: Line 18:
* '''1 ⩽ a ⩽ b ⩽ 100'''
* '''1 ⩽ a ⩽ b ⩽ 100'''
* se recomandă utilizarea unei liste alocate dinamic
* se recomandă utilizarea unei liste alocate dinamic
== Exemplul ==
== Exemplul ==
; listin.txt
; listin.txt
Line 38: Line 37:
  15 22
  15 22
  7 4
  7 4
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>

Revision as of 21:27, 2 January 2024

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

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

Rezolvare

<syntaxhighlight lang="python" line> 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()

</syntaxhighlight>