問題一覧 > 通常問題

No.2691 Longest Infection Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 188
作問者 : hibit_athibit_at / テスター : MMMM 👑 seekworserseekworser ypwwypww kikueplkikuepl
1 ProblemId : 9897 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-21 14:29:44

問題文

悪の医者である hibit 君は以下のような内訳で患者を受け持っています。

  • 血液型が A型 である人が $A$ 人
  • 血液型が B型 である人が $B$ 人
  • 血液型が O型 である人が $O$ 人
  • 血液型が AB型 である人が $W$ 人

血液型は以下のような性質を持ちます。

  • A型の人からは、A型またはAB型の人にのみ輸血できる
  • B型の人からは、B型またはAB型の人にのみ輸血できる
  • O型の人からは、すべての人に輸血できる
  • AB型の人からは、AB型の人にのみ輸血できる

hibit 君は悪の医者なので「HBウイルス」を患者達の中でたくさん感染させたいです。

まず、以下の手順を $1$ 回だけ行います。

  • ある人にウイルスを注入する。その人は感染する

その後、以下の手順を任意の回数（ $0$ 回でもよい）行います。

  • ある人から別の人に（血液型の相性が問題ない場合にのみ）輸血をする
  • 輸血元の人が感染していた場合、輸血先の人も感染する
  • ある人が輸血を行える（輸血元になれる）のは、$1$ 回だけである

感染する患者数の最大値を出力してください。

入力

$A\ B\ O\ W$

  • 入力はすべて整数
  • $0 \leq A,B,O,W \leq 10^3$
  • 患者が少なくとも $1$ 人存在する。つまり $(A,B,O,W) \neq (0,0,0,0)$

出力

整数 $1$ 行で出力してください。

サンプル

サンプル1
入力
1 1 1 1
出力
3

この入力では、A型、B型、O型、AB型の人がそれぞれ $1$ 名ずついます。

  • まず、O型の人にウイルスを注入をします。その人は感染します。
  • O型の人はB型の人に輸血します。B型の人は感染します。
  • B型の人はAB型の人に輸血します。AB型の人は感染します。

結果、感染する患者数は $3$ 人となります。他にも色々な経路が考えられますが、これが最大値です。

サンプル2
入力
3 4 5 6
出力
15

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。