切蛋糕

在第一行输出一个不超过6000的正整数N，表示方案的操作次数。

接下来的N行描述该方案的N次操作。

对于第i次操作，若该操作要进行切分操作，则在该行行首输出1，之后输出要切分的蛋糕的大小。例如：若要将一块大小为 $1/{2^1}$ 的蛋糕分割成两块大小为 $1/{2^2}$ 的蛋糕，则在该行输出1 1;若要将一块大小为 $1/{2^2}$ 的蛋糕分割成两块大小为 $1/{2^3}$ 的蛋糕，则在该行输出1 2。初始时完整的蛋糕，大小视为 $1/{2^0}$ 。

若该操作要进行打包操作，则在该行行首输出2，之后输出一个正整数m，代表要打包的蛋糕块数。之后输出m个正整数，分别代表要打包的m快蛋糕的大小。例如：若要将一块大小为 $1/{2^1}$ 的蛋糕和一块大小为 $1/{2^2}$ 的蛋糕进行打包，则在该行输出2 2 1 2;若要将两块大小为 $1/{2^2}$ 的蛋糕进行打包，则在该行输出2 2 2 2。

需要注意，一块蛋糕只有在被打包后才可以被龙龙送给他的hxd。所以你至少应进行k次打包操作。每份被包装的蛋糕的大小与1/k的差距的绝对值不应大于 $1/{2^{10}}$ 。

C(clang11) 解法, 执行用时: 5ms, 内存消耗: 372K, 提交时间: 2021-02-01 23:59:56

#include<stdio.h>
#include<math.h>
int main()
{
	int a,i,k,j,two=1;
	scanf("%d",&k);
	for(i=1;;i++)
	{
		if(fabs((double)i/2048.0-1.0/k)<=1.0/1024.0)break;
	}
	printf("%d\n",2047+k);
	a=i;
	for(i=0;i<=10;i++)
	{
		for(j=1;j<=two;j++)
		{
			printf("1 %d\n",i);
		}
		two*=2;
	}
	for(i=0;i<k;i++)
	{
		printf("2 %d",a);
		for(j=1;j<=a;j++)printf(" 11");
		printf("\n");
	}
 }

C++(clang++11) 解法, 执行用时: 9ms, 内存消耗: 412K, 提交时间: 2021-03-05 14:07:35

#include<bits/stdc++.h>
using namespace std;
int main(){
	int k;
	cin>>k;
	int ans = 1023;
	cout<<ans+k<<endl;
	int cn  = 1;
	for(int i=0;i<=9;i++){
		for(int j=0;j<cn;j++){
			cout<<"1 "<<i<<endl;
		}
		cn *= 2;
	}
	int now = 1024/k;
	while(k--){
			cout<<"2 "<<now;
			for(int i=0;i<now;i++){
				cout<<" 10";
			}
			cout<<endl;
	}
}

Python3 解法, 执行用时: 52ms, 内存消耗: 4892K, 提交时间: 2022-01-05 14:06:32

k = int(input())
print(2047+k)
for i in range(11):
    for j in range(1, (1 << i)+1):
        print(1, i)
x = (1 << 11) // k
for i in range(k):
    print(2, x, end=' ')
    for j in range(x):
        print(11,end=' ')
    print()

详情