Fişierul intrare/ieşire:camelot.in, camelot.outSursăConcurs Clasa a 7-a
AutorTeodor PlopAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.3 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Camelot

Cu ocazia venirii primăverii, măreţul regat Camelot va fi gazda luptelor de echipă în The Grand Arena. În curtea regatului sunt N soldaţi, fiecare având o anumită putere p[i]. Astfel se vor forma două echipe din aceşti soldaţi, puterea fiecărei echipei fiind suma puterilor membrilor acesteia. Într-o astfel de luptă, echipa pierzătoare este cea cu puterea mai mică.

Regele Uther Pendragon, curios din fire, doreşte să ştie câte posibilităţi de a împărţi echipele există, posibilităţi în care prima echipă este cea pierzătoare.

Rezultatul va fi afişat modulo 900001.

Date de intrare

În fişierul de intrare camelot.in se găseşte pe prima linie numărul de soldaţi N aflaţi în curtea regatului, iar pe cea de-a doua linie N numere naturale, reprezentând puterile soldaţilor.

Date de ieşire

În fişierul de ieşire camelot.out se va găsi un singur număr natural P, reprezentând numărul de posibilităţi de a alege echipele astfel încât prima echipă să fie cea pierzătoare.

Restricţii

  • 2 ≤ N ≤ 400
  • 1 ≤ p[i] ≤ 600
  • Orice soldat trebuie să aparţină unei singure echipe.

Exemplu

camelot.incamelot.out
3
1 3 5
3

Explicaţie

Cele trei posibilităţi sunt:
{1} şi {2, 3}: Prima echipă are puterea 1, cea de-a doua echipă are puterea 8.
{1, 2} şi {3}: Prima echipă are puterea 4, cea de-a doua echipă are puterea 5.
{2} şi {1, 3}: Prima echipă are puterea 3, cea de-a doua echipă are puterea 6.

Trebuie sa te autentifici pentru a trimite solutii. Click aici