Preparing NOJ

被遗忘的计划

1000ms 524288K

Description:

在比特超市有 $$$n$$$ 种商品,依次编号为 $$$1$$$ 到 $$$n$$$,购买一件第 $$$i$$$ 种商品的价格为 $$$i$$$ 元,其价值为 $$$v_i$$$。由于备货充足,每种商品都可以购买任意非负整数件。

小Q计划购买恰好 $$$k$$$ ($$$1\leq k\leq 10^9$$$) 件商品,并计算出了 $$$f_0,f_1,f_2,\dots,f_{n-1}$$$,其中 $$$f_i$$$ 表示购买 $$$k$$$ 件商品且商品价格之和对 $$$n$$$ 取模的余数恰好为 $$$i$$$ 的所有方案中商品价值之和的最大可能值。

一天过去之后,健忘的小Q忘记了昨天做的购物计划中到底要买多少件物品,请写一个程序根据小Q的回忆找到 $$$k$$$ 的值。

Input:

第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 1\,000$$$),表示商品的种类数。

第二行包含 $$$n$$$ 个整数 $$$v_1,v_2,\dots,v_n$$$ ($$$1\leq |v_i|\leq 10^9$$$),依次表示每种商品的价值。

第三行包含 $$$n$$$ 个整数 $$$f_0,f_1,\dots,f_{n-1}$$$ ($$$-10^{18}\leq f_i\leq 10^{18}$$$),表示小Q回忆出来的 $$$f$$$ 的每一项的值。

Output:

输出一行一个整数 $$$k$$$ ($$$1\leq k\leq 10^9$$$),即 $$$k$$$ 的取值,若有多个合法的 $$$k$$$,输出任意一个。如果小Q回忆有误,即在 $$$[1,10^9]$$$ 内找不到对应的 $$$k$$$,请输出"-1"。

Sample Input:

3
1 2 3
6 4 5

Sample Output:

2

Sample Input:

3
1 2 3
-1 -2 -3

Sample Output:

-1

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389E

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:25

Related

Nothing Yet