当前位置:网站首页>[exercise 4-1] cake distribution
[exercise 4-1] cake distribution
2022-07-06 15:57:00 【Flame car】
List of articles
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. Source of topic
The question is Waterloo Local Contest 2019 Fall Inside A topic .
Official title link : Click on
Official solutions and data : Click on
2. Topic translation
At first, I didn't understand what I said , Later on N Many translators have learned such a situation :
You have a biggest 1e18 The cake , There may be A Or B Or C personal ( One of them ) Come and eat cake , When distributing cakes , Everyone must be assigned to the cake Same quality ( The number can vary , But the quality must be the same ), Because you are lazy , At most 5000 block ( This determines that you cannot run with violence ).
Then explain the example :
First output how many pieces you divided N( It's up to you , There is a special judgment , No more than 5000 block )
And then down N That's ok , Each row
The first one is to output the quality of this cake .
The second output, if any A How many people will get this cake .
Third output, if any B How many people will get this cake .
The fourth output, if any C How many people will get this cake .
Code
Error model ( Ignore most 5000 block )
#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;
}
This is the assumption that every piece is 1g Calculated , It also depends on the time limit 15s Dare to write like this .
Correct demonstration
#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;
}
Simple version
#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;
}
The concise version actually uses set Instead of using map Duplicate check , as well as sort Sorting steps , because set It will automatically check the duplicate and sort .
auto x : st
set<int>::iterator it = st.begin();it!=st.end();it++
Both are acceptable , Obviously, the former is simpler .auto Is to get the type automatically .
The former uses x Substitute value , The latter uses *it.
analysis
At first glance, it may feel messy , In fact, if you look carefully, you can understand the truth :
This is actually a super optimization of violence , The time complexity is directly from O(1e9) drop to O(1e3). In terms of ideology, it is exactly the same . Traversal just merges some that can be merged , In fact, the total quality M = a×b×c There is no change
① The first three times for What does cycle mean ?
Take one for example ( With A For example ), Every time b×c Gram belongs to one person ( The total quality a×b×c, common a Share , each b×c)
② Why use This time x- Last time x?
Or the reason above , The quality of everyone is a( or b or c), We pause once ( Do one operation ) There is At least one group needs to be replaced . Due to the accumulation of a( or b or c) Gram's cake was given to one person , You need to change someone , So this operation is to output how many cakes are separated in this small step .(x Is the cumulative value )
③last/(b×c) + 1) What does that mean? ?
Replacement operation , When last It's you insert At the time of the i×b×c when , Now the one who is sharing the cake is last/(b×c) + 1 Number
Give me a demonstration :
1 2 3
↓
1 --> 6
2 --> 3 6
3 --> 2 4 6
That is, accumulated to 6g when A substitutions
Accumulate to 3g ,6g when B substitutions
Accumulate to 2g , 4g, 6g when C substitutions
After checking and sorting --> 2 3 4 6
That is, it is accumulating to 2,3,4,6g When you need to change people .
The first size 2-0=2 ,1 1 1 , here C substitutions .
The second size 3-2=1 ,1 1 2 , here B substitutions .
The third size 4-3=1 ,1 2 2 , here C substitutions .
The fourth size 6-4=2, 1 2 3 , here A,B,C Change people .
So in fact, this is the optimization of violence .
Violence is :
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 Every time 6 Change one at a time ,B Every time 3 Change one at a time ,C Every time 2 Change one at a time .( The focus is the replacement of a combination )
Optimization is :
2 1 1 1
1 1 1 2
1 1 2 2
2 1 2 3
The optimized version is to put the repeated quality together ( The focus is on the replacement of each combination )
边栏推荐
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
- Opencv learning log 19 skin grinding
- Matlab example: two expressions of step function
- Research Report on market supply and demand and strategy of geosynthetics industry in China
- Research Report on market supply and demand and strategy of Chinese graphic screen printing equipment industry
- Borg Maze (BFS+最小生成树)(解题报告)
- China's salt water membrane market trend report, technological innovation and market forecast
- China chart recorder market trend report, technology dynamic innovation and market forecast
- Penetration test (8) -- official document of burp Suite Pro
- Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
猜你喜欢
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
【高老师UML软件建模基础】20级云班课习题答案合集
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
Ball Dropping
Matlab example: two expressions of step function
C语言必背代码大全
信息安全-安全编排自动化与响应 (SOAR) 技术解析
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
Penetration test (1) -- necessary tools, navigation
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
随机推荐
Cost accounting [13]
编程到底难在哪里?
[exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
JS调用摄像头
Record of brushing questions with force deduction -- complete knapsack problem (I)
Information security - threat detection - detailed design of NAT log access threat detection platform
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
对iptables进行常规操作
Matlab comprehensive exercise: application in signal and system
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Market trend report, technical innovation and market forecast of lip care products in China and Indonesia
力扣刷题记录--完全背包问题(一)
Information security - threat detection engine - common rule engine base performance comparison
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
动态规划前路径问题优化方式
信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
China's PCB connector market trend report, technological innovation and market forecast
7-1 懂的都懂 (20 分)
入门C语言基础问答