Classroom Greetings
National Olympiad — Municipal round
Submission name: klas.cpp
Problem summary
Students enter in the supplied order. An arriving boy shakes hands with every boy already inside and exchanges one greeting in each direction with every girl. An arriving girl says one greeting to the whole room if it is nonempty; each student already inside replies once. Count handshakes and individual spoken greetings.
Input
A nonempty string: + denotes a girl and − (ASCII minus) a boy.
Output
Handshakes and spoken greetings, separated by a space.
Constraints
1 ≤ string length ≤ 20000.
Worked example
An independently prepared example for this explanation.
Input
--+
Output
1 3
Solution analysis
- Track the number of boys, girls and students already present.
- A boy adds boys handshakes and twice girls greetings.
- A girl entering a nonempty room adds one plus the previous number of students greetings.
Why it works
Each greeting and handshake is assigned uniquely to the arriving student who triggers it.
Watch out. A girl’s initial greeting is a single utterance, not one per classmate.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each greeting and handshake is assigned uniquely to the arriving student who triggers it.
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
long long b=0,g=0,h=0,w=0;
for(char c:s){
if(c=='-'){
h+=b;
w+=2*g;
b++;
}
else{
if(b+g){
w+=1+b+g;
}
g++;
}
}
cout<<h<<' '<<w<<'\n';
}