2847 – List

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

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

</syntaxhighlight>