Slots of Fun
Time limit1sMemory limit128 MB
Given letters on a triangular lattice, find every letter whose three positions form an equilateral triangle.
- Level
Medium6 of 10
- Topics
- Geometry, Brute force, Implementation, Math
- Solved
- No attempts yet
Problem
A slot machine has a display built from identical circles packed into a triangle. The top row holds one circle, and every row below it holds one more circle than the row above, so a display with rows has circles. The circles are packed tightly, so the centers of neighbouring circles are all the same distance apart and their centers form a triangular lattice.
Each time the player pulls the lever, the machine writes a random lowercase letter into every circle. The machine pays off whenever three circles that hold the same letter sit at the vertices of an equilateral triangle (distances are measured between circle centers). To keep payoffs rare, the machine never prints more than three copies of any single letter in one display.
The manufacturer builds these machines with different numbers of rows and needs a program that finds the winning letters. Given a filled-in display, report every letter whose circles form an equilateral triangle.
Input
The input contains several displays. Each display starts with a line containing a single integer (), the number of rows. The next line contains exactly lowercase letters with no spaces: the contents of the circles listed row by row from the top row down, and left to right within each row. The input ends with a line containing a single , which is not a display and must not be processed.
Output
For each display, print one line listing every letter that forms an equilateral triangle, in alphabetical order and with no spaces between them. If no letter forms an equilateral triangle, print LOOOOOOOOSER! on that line instead.