CSES - Datatähti 2017 alku - Kolikot
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Sinulla on nn kolikkoa, joilla on tietyt arvot. Tehtäväsi on selvittää, mikä on pienin rahamäärä, jota ei voi muodostaa kolikoista.

Esimerkiksi jos kolikot ovat {2,1,2,7}\{2,1,2,7\}, niistä voi muodostaa rahamäärät 151 \ldots 5 seuraavasti:

  • 1=11 = 1
  • 2=22 = 2
  • 3=2+13 = 2+1
  • 4=2+24 = 2+2
  • 5=2+2+15 = 2+2+1

Kuitenkaan kolikoista ei voi muodostaa rahamäärää 66.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: kolikoiden määrä.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: kolikoiden arvot. Usealla kolikolla voi olla sama arvo.

Tuloste

Tulosta pienin rahamäärä, jota ei voi muodostaa kolikoista.

Esimerkki 1

Syöte:

4
2 1 2 7

Tuloste:

6

Esimerkki 2

Syöte:

5
3 3 3 3 3

Tuloste:

1

Osatehtävä 1 (22 pistettä)

  • 1n101 \le n \le 10
  • 1xi101 \le x_i \le 10

Osatehtävä 2 (35 pistettä)

  • 1n1001 \le n \le 100
  • 1xi10001 \le x_i \le 1000

Osatehtävä 3 (43 pistettä)

  • 1n1051 \le n \le 10^5
  • 1xi1091 \le x_i \le 10^9