Classroom Handshakes and Spoken Greetings
National Olympiad — Municipal round (2017 season)
Submission name: klas.cpp
Problem summary
Boys shake hands with earlier boys. Every pair involving a girl exchanges two spoken greetings. Count handshakes and occurrences of the greeting word after everyone arrives.
Input
N boys and M girls.
Output
Handshake count, then spoken-greeting count.
Constraints
0 ≤ N,M ≤ 100000000.
Worked example
Input and output for the worked example discussed below.
Input
1 2
Output
0 6
Solution analysis
- Every unordered boy-boy pair shakes hands exactly once, when its later member arrives. This gives N(N−1)/2 handshakes, independent of arrival order.
- There are NM mixed pairs and M(M−1)/2 girl-girl pairs. Every such pair speaks two greetings, so the spoken count is2NM+M(M−1).
- With one boy and two girls there are no boy-boy pairs. Two mixed pairs and one girl-girl pair each contribute two words, giving0 handshakes and6 greetings. All counts need64-bit arithmetic.
Why it works
The pair types partition all pairs of students. Each pair interacts once at the later arrival, and the stated rules determine its contribution uniquely. Summing these independent contributions gives both totals.
Watch out. Each verbal exchange contains two words, not one. Promote before multiplication; int overflows at the allowed class sizes.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long boys;
long long girls;
cin>>boys>>girls;
// Each pair interacts exactly once, when the later student arrives.
long long handshakes=boys*(boys-1)/2;
long long greetings=2*boys*girls+girls*(girls-1);
cout<<handshakes<<' '<<greetings<<'\n';
}