Algoogle

Algorithm for Programming Contest

AOJ 2582 Step Aerobics

Category: AOJ Tag: implementation

Step Aerobics

問題概要


1段の段差の上での左右の足の上げ下げの列が与えられる. 不正な列はない.
両足とも下段についている状態から両足とも上段についている状態(またはその逆)になる回数を求めよ.

解法


やるだけだがコーディング時間を節約する簡単な実装を心がける.
上げ下げは交互に来ることが保証されているので各列の2文字目はいらない.
始め目的の状態を上げた状態に設定する.
各ステップで命令の足の状態を変更する.
両足の状態が目的の状態に達したら答えに1足して目的の状態を変更する.

入力のlrを処理するのが面倒だったので状態の配列を大きく取ってcharをそのままつっこんだ.

コード


(2582.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)

string op[128];
int st[256], n;

int solve(){
    memset(st,0,sizeof(st));
    int ans = 0, s = 1;
    rep(i,n) {
        st[op[i][0]] ^= 1;
        if(s == st['l'] and s == st['r']) ++ans, s ^= 1;
    }
    return ans;
}

bool input(){
    cin >> n;
    if(!n) return 0;
    rep(i,n) cin >> op[i];
    return 1;
}

int main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments