読者です 読者をやめる 読者になる 読者になる

SRM 587 Div2 Medium JumpFurther

問題

SRM 587 - TopCoder Wiki

階段の0フロアにいて,ステップxの時に,x段階段を登るか,その場にとどまるかの2通りのアクションを取ることが出来る. ただし,badStepのフロアに足を踏み入れる事はできない. この時,登れる階段の最大の数を答える問題.

解答

  • 単純に登ってbadStepに踏み入れないならそのまま全て登る.
  • そうでない場合.badStepが一つしか無いのでどこかのステップで1回留まればいい.
  • 沢山登りたいので,最初のステップ留まるのが最良の選択.
using namespace std;

class JumpFurther
{
public:
  int furthest(int N, int badStep)
    {
      int i;
      int not_wait = 1;
      int wait = 0;
      bool not_wait_is_bad = false;
      if (badStep == 1) not_wait_is_bad = true;
      for (i = 2; i <= N; i++) {
        not_wait += i;
        wait += i;
        if (not_wait == badStep) not_wait_is_bad = true;
      }
      if (not_wait_is_bad) return wait;
      return not_wait;
    }
};