Magic Weapon
InterviewTime limit2sMemory limit512 MB
Count triples of details, one per color, where the red number's first and last digits match the green's last digit and the blue's first digit, and all three model numbers differ.
- Level
Medium5 of 10
- Topics
- Combinatorics, Math, Hash map, Implementation
- Solved
- No attempts yet
Problem
To create the magic weapon, the Space Rangers need three details: green, red, and blue.
Green, Red, and Blue Rangers want to know how many different ways they have to create the weapon. Each ranger has several details: Green Ranger has green details, Red Ranger has red details, Blue Ranger has blue details.
Each detail has a model number. To create the weapon, the rangers must follow three rules:
- The first digit of the model number of the red detail must equal the last digit of the model number of the green detail.
- The last digit of the model number of the red detail must equal the first digit of the model number of the blue detail.
- The model numbers of all three details must be different.
Two ways to create the weapon are considered different if at least one ranger uses another detail, even if its model number is the same.
For each ranger you are given the model numbers of their details. One ranger can have several details with the same model number.
Help the rangers find out how many different ways to create the magic weapon they have.
Input
The first line of input contains three integers g, r, b, the number of details that Green Ranger, Red Ranger, and Blue Ranger have, respectively (1 ≤ g, r, b ≤ 105).
The next line contains g integers xi, the model numbers of the green details (0 ≤ xi ≤ 109).
The next line contains r integers yi, the model numbers of the red details (0 ≤ yi ≤ 109).
The next line contains b integers zi, the model numbers of the blue details (0 ≤ zi ≤ 109).
Output
Print one integer: the number of ways to create the magic weapon.