けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1601 短句 (ICPC 国内予選 2015 B) (150 点)

なにこの 575 検出器!!!解法自体は Greedy にやるだけ

問題へのリンク

問題概要

57577 を検出せよ。 複数あるときは一番先頭を検出せよ。

do the best and enjoy today at acm icpc

の場合は先頭から dothe bestand enjoy todayat acmicpc で 57577 なので、先頭の index 1 を出力する。

解法

Greedy に check するだけ

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int len[5] = {5, 7, 5, 7, 7};

int main() {
  int N;
  while (cin >> N, N) {
    vector<string> a(N); for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) {
      bool ok = true;
      int j = i;
      for (int it = 0; it < 5; ++it) {
        string str = "";
        while (j < N && str.size() < len[it]) str += a[j++];
        if (str.size() != len[it]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        cout << i+1 << endl;
        break;
      }
    }
  }
}