Page 21 - MATINF Nr. 11-12

a
Concursul de Informatic˘ Programming Day 21

Date de ies , ire
Dac˘ C este 1, fis , ierul de ies , ire partitii.out va cont , ine pe cˆate o linie submult , imile partit , iei
a
de la cerint , a 1, elementele de pe o linie sunt separate printr-un spat , iu s , i sunt scrise ˆın ordine
cresc˘atoare. Submult , imile partit , iei se vor scrie ˆın ordinea cresc˘atoare a primului element.
a
Dac˘ C este 2, fis , ierul de ies , ire partitii.out va cont , ine num˘arul de la cerint , a 2.
Restrict , ii s , i preciz˘ari
• 2 ≤ k ≤ n ≤ 14, n num˘ar par;

• a 1 , a 2 , . . . , a n sunt numere naturale cu maxim 5 cifre.

• Pentru toate testele se garanteaz˘a existent , a solut , iei la cerint , a 1.

a
• Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 40 de puncte.
• Pentru rezolvarea corect˘ a cerint , ei 2 se vor acorda 60 de puncte.
a
Exemplu

partitii.in partitii.out
1 1 9
4 2 2 8
9 2 1 8
2 6
4 2
9 2 1 8

Explicat , ii
Pentru cerint , a 1 o partit , ie cu mult , imi de dou˘ elemente este
a
{2, 8} {1, 9}, fiecare submult , ime are 2 elemente s , i suma elementelor egal˘ cu 10.
a
Pentru cerint , a 2 sunt 6 partit , ii 2-speciale:
{9} {2, 1, 8}, cu sumele 9 s , i 11

{2} {9, 1, 8}, cu sumele 2 s , i 18
{1} {9, 2, 8}, cu sumele 1 s , i 19

{8} {9, 2, 1}, cu sumele 8 s , i 12

{9, 2} {1, 8}, cu sumele 11 s , i 9
{9, 8} {1, 2}, cu sumele 17 s , i 3.

Timp maxim de execut , ie: 6 secunde/test.
a
Memorie total˘ disponibil˘a: 2 MB.
Solut , ie
Cerint , a 1 ( 40 puncte)

a
Se ordoneaz˘a elementele mult , imii A s , i se afis , eaz˘ partit , ia:
{a[1], a[n]}, {a[2], a[n − 1]}, . . . , {a[n/2], a[1 + n/2]}

Cerint , a 2 ( 60 puncte)
Se genereaz˘a cu backtracking partit , iile cu restrict , iile din enunt , s , i se num˘ar˘a.