UOJ Logo LFYZ Online Judge

LFYZOJ

#7. 颓我家财

统计

问题描述

11月,《東方天空璋 ~ Hidden Star in Four Seasons》在Steam上登录。

poorpool 也想买,但是他发现他的钱包里只有$ n $张面额互不相同的纸币,于是他就想知道,这些纸币不能凑成的最小正金额是多少。

输入格式

第一行一个整数$ n $。

第二行$ n $个整数,是poorpool钱包里每张纸币的面额。

输出格式

一个整数,是这些纸币不能凑成的最小正金额。

样例一

input

3
1 2 5

output

4

数据范围与约定

对于30%的数据,$ n \leq 15 $。

对于60%的数据,$ n \leq 1000 $。

对于100%的数据,$ n \leq 10^5 $,保证给出的面额是递增的且小于等于$ 10^9 $。

时间限制: $ 1\mathrm{s} $

空间限制: $ 256\mathrm {MB} $

下载

样例数据下载

题目来源

poorpool & Mr_Wolfram 2017年12月临汾一中第一届信息学算法设计竞赛

from 张若天,清华大学