【练习4-1】Cake Distribution（分配蛋糕）

A . Cake Distribution

Description

You are about to have a birthday and you would like to prepare a birthday cake that weighs anywhere between 1 and 1018 grams inclusive. You know that there will be A,B or C guests at the party. You would like to cut this cake into pieces such that:

The weight of each piece is a positive integer number of grams.
No matter how many guests arrive, the pieces can be distributed between the guests in such a way that each guest gets the same amount of cake. Note that some guests might get more than one piece.
You don’t want to spend too much time cutting the cake, so you would like to have at most 5,000 pieces. Let’s do it!

Input

The only line of input contains the 3 numbers A,B,C, all positive integers not more than 1000.

Output

On the first line, output one number K, the number of pieces. On each of the next K lines, output a description of each piece, consisting of 4 numbers, wi,ai,bi,ci, where wi is the weight of the piece in grams and ai,bi,ci are indices of the person who will get this piece if A,B, or C guests arrive, respectively. The indices should satisfy 1≤ai≤A, 1≤bi≤B, 1≤ci≤C. The sum of all wis must be less than or equal to 1018.

Samples

Input

1 2 3

Output

4
2 1 1 1
1 1 1 2
1 1 2 2
2 1 2 3

1.题目出处

这道题是Waterloo Local Contest 2019 Fall里面的A题。
官方题目链接：点击
官方题解及数据：点击

2.题目翻译

做的时候刚开始硬是没看明白讲了个什么意思，后来用了N多翻译了解到了是这样的情景：
你有一个最大1e18的蛋糕，可能有A个或B个或C个人（其中一种）来吃蛋糕，分配蛋糕时，必须每个人的分配到的蛋糕质量相同（数量可以不同，但质量必须相同），由于你很懒，最多分5000块（这就决定了你不可能用暴力来跑）。
那么解释一下样例：
先输出你分了多少块N(自己决定的，有特判,不能多于5000块）
然后下面N行，每行
第一个输出这一块蛋糕的质量。
第二个输出如果有A个人那么第几个人会得到这块蛋糕。
第三个输出如果有B个人那么第几个人会得到这块蛋糕。
第四个输出如果有C个人那么第几个人会得到这块蛋糕。

代码

错误示范（忽略最多5000块）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 1e6+5; 
int main()
{
    
	ll a,b,c;
	cin>>a>>b>>c;
	ll t = a*b*c;
	cout<<t<<endl;
	ll na=1,nb=1,nc=1;
	ll cnta=0,cntb=0,cntc=0;
	ll moda,modb,modc;
	moda = b*c;
	modb = a*c;
	modc = a*b;
	for(ll i=1;i<=t;i++) {
    
		printf("1 %lld %lld %lld\n",na,nb,nc);
		if(++cnta%moda==0)
			na++;
		if(++cntb%modb==0)
			nb++;
		if(++cntc%modc==0)
			nc++;
	} 
    return 0;
}

这就是假设每一块都是1g来计算的，也是看在时间限制是15s才敢这么写的。

正确示范

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 1e6+5; 
int cnt;
map<ll,int> mp;
ll num[N];
int main()
{
    
	ll a,b,c;
	cin>>a>>b>>c;
	for(int i = 1;i <= a; i++) 
		if(!mp[b*c*i])
			num[++cnt]=b*c*i,mp[b*c*i]=1;
	for(int i = 1;i <= b; i++) 
		if(!mp[a*c*i])
			num[++cnt]=a*c*i,mp[a*c*i]=1;
	for(int i = 1;i <= c; i++) 
		if(!mp[b*a*i])
			num[++cnt]=b*a*i,mp[b*a*i]=1;
	sort(num+1,num+1+cnt);
	ll last = 0;
	cout << cnt << endl;
	for (int i=1;i<=cnt;i++) {
    
	  	cout<<num[i]-last<<' '<<(last/(b*c) + 1)<<' '<<(last/(a*c)+1)<<' '<<(last/(b*a)+1)<<'\n';
	 	last = num[i];
	}
    return 0;
}

简洁版本

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 1e6+5; 
set<ll> st;
int main()
{
    
	ll a,b,c;
	cin>>a>>b>>c;
	for(int i = 1;i <= a; i++) 
		st.insert(b*c*i);
	for(int i = 1;i <= b; i++) 
		st.insert(a*c*i);
	for(int i = 1;i <= c; i++) 
		st.insert(b*a*i);
	ll last = 0;
	cout << st.size() << endl;
	for (auto x : st) {
    
	  	cout<<x-last<<' '<<(last/(b*c) + 1)<<' '<<(last/(a*c)+1)<<' '<<(last/(b*a)+1)<<'\n';
	 	last = x;
	}
    return 0;
}

简洁版本其实就是用set来代替了用map查重复，以及sort排序的步骤，因为set会自动查重并排序。

auto x : st
set<int>::iterator it = st.begin();it!=st.end();it++
这两种写法都是可以的，很明显前者更简单。auto就是自动获取类型。
前者用x代替数值，后者用*it。

解析

可能乍一看觉得什么乱七八糟，其实仔细看看就可以理解其中的道理了：
这其实就是暴力的一个超级优化，时间复杂度直接从O(1e9)降到O(1e3)。在思想方面完全是一模一样的。就是遍历只不过把一些可以合并的合并起来了，实际上总的质量M = a×b×c没有改变

①最一开始的三次for循环是什么意思？
拿一次来说(以A为例）,每b×c克就属于一个人(总质量a×b×c，共a份，每份b×c)
②为什么要用 这一次的x-上一次的x?
还是上面的原因，每个人的质量就是a(或b或c)，我们停顿一次（进行一次操作）就是有至少一组需要换人了。由于每次累计达到a(或b或c)克的蛋糕被分给一个人，就需要换下一个人，所以此操作是输出该小步有多少蛋糕被分出。（x是累计值）
③last/(b×c) + 1)是什么意思？
换人操作，当last是你insert时的i×b×c时，现在正在分蛋糕的就是last/(b×c) + 1号

演示一遍：
1 2 3
↓
1 --> 6
2 --> 3 6
3 --> 2 4 6
也就是累计到6g时A换人
累积到3g ，6g时B换人
累积到2g , 4g, 6g时C换人

查重并排序后 --> 2 3 4 6
也就是在累积到2,3,4,6g时需要换人。

第一块大小 2-0=2 ，1 1 1 , 此时C换人。
第二块大小 3-2=1 ，1 1 2 , 此时B换人。
第三块大小 4-3=1 ，1 2 2 , 此时C换人。
第四块大小 6-4=2， 1 2 3 , 此时A,B,C都换人。

所以其实这就是暴力的优化。
暴力是：
1 1 1 1
1 1 1 1
1 1 1 2
1 1 2 2
1 1 2 3
1 1 2 3
A每6次换一个，B每3次换一个，C每2次换一个。（关注点是某个组合的替换）
优化是：
2 1 1 1
1 1 1 2
1 1 2 2
2 1 2 3
优化版就是把重复的质量归在一起（关注点在每个组合的替换）