← 返回题目列表

AtCoder · joisc2012_fish

fish. 鱼

中文机器翻译题面 查看原题

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

魚 - 原题 PDF 第 1 页
原题PDF第3页
魚 - 原题 PDF 第 2 页
原题PDF第4页
可复制的 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