20180516 CF试做2

本文主要是介绍20180516 CF试做2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天晚上比赛就做了一个题目，其他题目看了看都没有思路。先说一下做的这个题目，一开始读错题意，卡了好久，一直没搞懂是什么意思，后来才明白:

A - Robbery

传送门：

点击打开链接

It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has n cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comfortable to work with and mark the cells with positive numbers from 1 to n from the left to the right.

Unfortunately, Joe didn't switch the last security system off. On the plus side, he knows the way it works.

Every minute the security system calculates the total amount of diamonds for each two adjacent cells (for the cells between whose numbers difference equals 1). As a result of this check we get an n - 1 sums. If at least one of the sums differs from the corresponding sum received during the previous check, then the security system is triggered.

Joe can move the diamonds from one cell to another between the security system's checks. He manages to move them no more than m times between two checks. One of the three following operations is regarded as moving a diamond: moving a diamond from any cell to any other one, moving a diamond from any cell to Joe's pocket, moving a diamond from Joe's pocket to any cell. Initially Joe's pocket is empty, and it can carry an unlimited amount of diamonds. It is considered that before all Joe's actions the system performs at least one check.

In the morning the bank employees will come, which is why Joe has to leave the bank before that moment. Joe has only k minutes left before morning, and on each of these k minutes he can perform no more than m operations. All that remains in Joe's pocket, is considered his loot.

Calculate the largest amount of diamonds Joe can carry with him. Don't forget that the security system shouldn't be triggered (even after Joe leaves the bank) and Joe should leave before morning.

Input

The first line contains integers n, m and k (1 ≤ n ≤ 10⁴, 1 ≤ m, k ≤ 10⁹). The next line contains n numbers. The i-th number is equal to the amount of diamonds in the i-th cell — it is an integer from 0 to 10⁵.

Output

Print a single number — the maximum number of diamonds Joe can steal.

Examples

Input

2 3 1
2 3

Output

Input

3 2 2
4 1 3

Output

Note

In the second sample Joe can act like this:

The diamonds' initial positions are 4 1 3.

During the first period of time Joe moves a diamond from the 1-th cell to the 2-th one and a diamond from the 3-th cell to his pocket.

By the end of the first period the diamonds' positions are 3 2 2. The check finds no difference and the security system doesn't go off.

During the second period Joe moves a diamond from the 3-rd cell to the 2-nd one and puts a diamond from the 1-st cell to his pocket.

By the end of the second period the diamonds' positions are 2 3 1. The check finds no difference again and the security system doesn't go off.

Now Joe leaves with 2 diamonds in his pocket.

注意，题目中k的意思是总共操作k次，m是每一场操作m个

思路：

（1）当n为偶数时，没法取。

（2）当n为奇数时，每偷一颗钻石的移动次数应该是n/2+1（一开始想成了n-1），把第奇数堆的一颗钻石向后移动一位，再从最后一堆取走一个。所以，能最大的偷取数量还受到奇数堆钻石的最小数量制约。因此最小数量应该是min(a[i])(i为奇数)与m/(n/2+1)*k的最小值。（注意会爆int）

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x7f7f7f7f
const int M = 100005;
LL n,m,k;
LL a[M];
LL num[M];
int main()
{cin>>n>>m>>k;for(int i=1; i<=n; i++) cin>>a[i];if(n%2==0){cout<<"0"<<endl;return 0;}LL ans =0;LL movs = n/2+1;if(movs>m){ans=0;}else{LL minn=a[1];for(int i=2;i<=n;i++){if(i%2==1){minn=min(a[i],minn);}}ans = min(minn , (LL)m/movs *k);}cout<<ans<<endl;return 0;
}

这篇关于20180516 CF试做2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！