Why Did the Cow Cross the Road II
Time limit2sMemory limit512 MB
Given a 52-character string where each of the 26 letters appears twice, count pairs of letters whose chord crossings force their paths to intersect.
- Level
Medium4 of 10
- Topics
- Array, Implementation, Brute force, Intervals
- Solved
- No attempts yet
Problem
John's farm has a circular pasture with a road running around its boundary. Every morning John's cows cross the road to graze in the pasture, and every evening they cross it again to return to the barn.
The cows are creatures of habit and cross the road the same way every day. Each cow enters through one fixed point on the circular road and leaves through a different point. No two cows pass through the same point on the road. Having watched this, John decides to analyze these points. There are 26 cows in total, named A, B, ..., Z. John walks clockwise around the 52 points and records which cow passes through each one. The resulting 52-character string contains each letter exactly twice.
For some pairs of cows, their paths must meet somewhere no matter how the cows walk. Count how many such pairs there are.
Input
The first line contains a string of 52 characters. Each character is an uppercase letter, and each letter appears exactly twice.
Output
Print the number of pairs of cows whose paths must meet.
Hint
In the sample, the paths of A and B must meet.