Farmer John has devised an automatic system to predict whether a cow has spots, based only on its weight. To classify a new cow C, FJ finds the cow C' in his herd with weight closest to that of C. If C' has spots, then FJ guesses that C will also have spots; if C' has no spots, FJ guesses the same for C. If there is not one unique nearest neighbor C' but rather a tie between two of FJ's cows, then FJ guesses that C will have spots if one or both of these nearest neighbors has spots.

FJ wants to test his new spot predictor on a group of new cows. After weighing these cows, he sees that the new shipment contains a cow of every integer weight between A and B (inclusive). Please determine how many of these cows will be classified as having spots, using FJ's classifier. Note that the classifier only uses data from FJ's N existing cows. Since A and B can both be quite large, your program will not likely run fast enough if it loops from A to B by ones.

(Note: this problem's statement was partially recovered during import.)

Line 1: Three integers N, A, and B (1 <= A <= B <= 1,000,000,000).

Lines 2..1+N: Each line describes a single cow, either "S W" (a spotted cow of weight W) or "NS W" (a non-spotted cow of weight W). Weights are integers in the range 1 ... 1,000,000,000.

A single integer giving the number of incoming cows that FJ's algorithm will classify as having spots.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Bronze