牛客练习赛64 A 怪盗-1412 平分1的个数

链接：https://ac.nowcoder.com/acm/contest/5633/A
来源：牛客网

题目描述
一个长度为n+m+k{n+m+k}n+m+k包含n{n}n个数字1{1}1，m{m}m个数字2{2}2和k{k}k个数字4{4}4的数组，最多可能有多少个子序列1412{1412}1412？
如果一个序列是数组的子序列，当且仅当这个序列可以由数组删去任意个元素，再将数组中的剩余元素按顺序排列而成。
输入描述:

第一行一个整数t{t}t，表示测试用例的组数。
接下来t{t}t行每行三个整数n,m,k{n,m,k}n,m,k表示一组测试用例。

输出描述:

对于每组测试用例输出一行一个整数表示答案。

示例1
输入
复制

3
6 7 8
1 2 2
6 0 3

输出
复制

504
0
0

备注:

1<=t<=200000{1<=t<=200000}1<=t<=200000
0<=n,m,k<=10000{0<=n,m,k<=10000}0<=n,m,k<=10000

很(不)容易想到：

形如1111444411112222的一定是满足题意的最优方案
即把1平分放到4的左右两边
- n为奇数时左边放 $n / 2 + 1$ 个 $1$ ,右边放 $n / 2$ 个 $1$
- $n$ 为偶数时左边和右边都放 $n / 2$ 个 $1$

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e6+7)
#define ll long long int
#define int long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif


int n, m, Q, K;

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(Q);
	while(Q--) {
		scanf("%lld %lld %lld ", &n, &m, &K);
		int lef = n&1 ? n/2+1 : n/2;
		int rig = n/2;
		printf("%lld\n", lef*rig*m*K);
	}


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}