[Atelier Blue アトリエブルー]Homeコンテストパソコン甲子園2004年予選>8問目

8問目(再帰・スタック)

問題

2本のパイプがあります。そこに10個の一列に並んだ玉を順番に入れていきます。ただし、条件があります。玉には1から10までの番号が振ってあり、番号の小さい玉の後に大きい玉を入れることは可能ですが、その反対は不可能です。このとき、並んだ10個の玉をすべてパイプに入れきることが出来ればYES、そうでなければNOを出力してください。

詳しくは原文参照。

入力


1番目の玉の番号(整数)
2番目の玉の番号(整数)
...
...
10番目の玉の番号(整数)

出力

YES または NO

入力例


3
1
4
2
5
6
7
10
8
9

出力例

YRS

解き方例

スタック又は、再帰で組めばいいでしょう。サンプルは再帰で組みます。

ソースコード

お持ち帰り

C/C++

#include <stdio.h>

int sta[10];

//再帰(n:staの位置 r:右パイプの一番上の数 l:左パイプの一番上の数)
int func(int n,int r,int l){
    if(n == 10)return 1;
    if(sta[n]>r){
        if(func(n+1,sta[n],l))return 1;
    }

    if(sta[n]>l){
        if(func(n+1,l,sta[n]))return 1;
    }
    return 0;
}

int main(){
    int i;

    for(i=0;i<10;i++){
        int in;
        scanf("%d",&in);
        sta[i]=in;
    }

    if(func(0,0,0)){
        printf("YES\n");
    }else{
        printf("NO\n");
    }

    return 0;
}


その他

スタックを自分で作るのが嫌な時は再帰に限ります。関数呼び出しはスタック構造ですからね。


ページの一番上へ
前のページへ 一覧に戻る 次のページへ
初版2006-8-23
[Atelier Blue アトリエブルー]Homeコンテストパソコン甲子園2004年予選>8問目