Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Atom Bombs!? God!
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 435Accepted: 66Special Judge

Description

Base on a real story, with real atom bombs!

The little cat has been invited to visit the Chinese nuclear physics research institute, Mianyang, Sichuan Prov. N (1 <= N <= 500) atomic warheads have been displayed in a large room, and each one has been assigned to an uppercase letter. Look at the following graph:

Three atomic warheads are displayed there, where two of them are assigned to letter ‘L’ and one of them to ‘O’. Visitors are only allowed to move back and forth on the guard line. At some point of the guard line, visitors may see some strange words formed by all the N letters. For instance, at the leftmost and rightmost part of the guard line, people may see a word “LOL” (words are obtained by letters from left to right). The positions that make some warheads blocked by others in line of sight should not be valid.

You are given an expected word to be seen, along with the coordinates of atomic booms (x, y) where y > 0. The guard line is just the x-axis. You are to output the whole intervals of places on x-axis, where the expected word can be seen. The intervals (A1, B1), (A2, B2), ... (AM, BM) should be expressed as a sequence of 2 * M values, A1, B1, A2, B2, … AM, BM. A1 should be replaced by * if it is –infinity, similarly BM should be replaced by * if it is infinity. What is more, we have restrictions that A1 < B1 <= A2 < B2 <=… <= AM < BM. (since we are always using open intervals, Bi may be equal with Ai+1)

Input

First line – an integer N.
Second line – a sequence of N uppercase letters, denoting the expected word to be seen.
3rd – (2 + N)-th lines – each contains the information of a single atomic warhead: an uppercase letter (assigned to that warhead), and two integers Xi, Yi denoting the coordinate of this warhead. (-2000 <= Xi <= 2000, 0 < Yi <= 2000).

Output

First line – an integer M.
Second line – 2 * M values. Values may be a single character *, or a real number. You should round the result to seven digits after the decimal point. We ensure double is OK for this problem.

Sample Input

3
LOL
L 0 3
O -1 2
L 1 1

Sample Output

2
* -3.0000000 3.0000000 *

Source

POJ Monthly--2006.03.26,Zeyuan Zhu,Modified from NEERC2005 Area

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator