以下是来自日本的原始新闻PDF,已完整保存和染色。


可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 1 – Fish
魚(Fish)
JOI 君はふと, 魚を飼おうと思い立った.
JOI 君の家の近所のペットショップに行ったところ,そこではN 匹の魚が売られていた.i 番目の魚の体
長はLi cm で,色は赤,緑,青のいずれかである.JOI 君はこれらのN 匹の魚のうちから1 匹以上を家で
飼うことに決めた.
魚を飼うときに注意しなければならないことがある.大きい魚と小さい魚を同時に飼うと,大きい魚が
小さい魚を食べてしまう.具体的には,魚X の体長が魚Y の体長の2 倍以上であるとき,X とY を同時に
飼うとX がY を食べてしまう.そのため,このような2 匹の魚を同時に飼うことはできない.
JOI 君は,飼う魚の色の組合せが何通りありうるのかが気になった.2 つの色の組合せが異なるとは,赤,
緑,青の少なくとも1 色の魚の数が異なることである.ペットショップで売られている魚の体長と色が与
えられるので,JOI 君が飼う魚の色の組合せとして考えられるものの個数を求めたい.
課題
ペットショップで売られている魚の体長と色が与えられたとき,JOI 君が飼う魚の色の組合せとして考え
られるものの個数を出力するプログラムを作成せよ.
制限
1 ≦N ≦500 000 魚の数
1 ≦Li ≦1 000 000 000 i 番目の魚の体長
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれている.N はペットショップで売られている魚の数を表す.
• 1 + i 行目(1 ≦i ≦N) には,整数Li と文字Ci が空白を区切りとして書かれている.文字Ci はR,G,B
のいずれかである.これは,i 番目の魚の体長がLi cm であり,Ci がR ならi 番目の魚の色が赤,Ci
がG ならi 番目の魚の色が緑,Ci がB ならi 番目の魚の色が青であることを表す.
出力
標準出力に,JOI 君が飼う魚の色の組合せとして考えられるものの個数を1 行で出力せよ.
魚– 1 / 2
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 1 – Fish
採点基準
採点用データのうち,配点の10%分は,N ≦100 を満たす.
採点用データのうち,配点の30%分は,N ≦2000 を満たす.
入出力の例
入力例1 出力例1
4 6
10 R
4 G
8 B
5 B
1 番目の魚は2 番目の魚を食べてしまうので,これらを同時に飼うことはできない.1 番目と4 番目,2
番目と3 番目についても同様である.よって,可能な色の組合せは,「赤1 匹」「緑1 匹」「青1 匹」「赤と青
1 匹ずつ」「緑と青1 匹ずつ」「青2 匹」の6 通りである.
入力例2 出力例2
10 13
26 B
10 B
16 G
20 R
6 R
5 G
13 G
40 R
8 R
33 R
魚– 2 / 2