AOJ Volume11 1179: Millennium

/*******************************
* 2012/07/06                   *
* AOJ Volume11 1179            *
* Millennium                   *
* crane                        *
********************************/
#include <iostream>
using namespace std;


#define MAX_N 1001
int field[MAX_N][11];

int main() {


    for(int i=1; i<=999; i++){
        for(int j=1; j<=10; j++){
            field[i][j] = 0;
        }
    }
    int  frag = 0;
    for(int i=1; i<=999; i++){
        frag = 0;
        if(i % 3 == 0)
            frag = 1;
        for(int j=1; j<=10; j++){
            if(frag == 1)
                field[i][j] = 20;
            else{
                if(j%2 == 0){
                    field[i][j] = 19;
                }else{
                    field[i][j] = 20;
                }

            }
        }
    }


    /* input  */
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        int y=0, m=0, d=0;
        cin >> y >> m >> d;
        long long  sum=0;
        int frag2=0;
        int a = m;
        for(int j=y; j<1000; j++){
            if(frag2 == 1)  a=1;

            for(int k=a; k<=10; k++){
                if(frag2 == 0){
                    sum += field[j][k] - d;
                    frag2 = 1;
                }else{
                    sum += field[j][k];
                }
            }
        }
        cout << sum+1 << endl;
    }

    return 0;
}

AOJ Volume1 0158: Collatz's Problem

• n が偶数の時は 2 で割る。
• n が奇数の時は 3 倍し、1 を足す。
• 整数 n は1以上でかつ上記の計算を繰り返す途中の値が1000000以下となる程度の整数とあったのでint からlongに変更。

/******************************
* 2012/07/15                  *
* AOJ_Volume1_0158            *
* Collatz's Problem           *
* crane                       *
*******************************/
#include<iostream>
using namespace std;
int main(){
    long long int n;
    while(cin >> n, n){
        int count = 0;
        while(1){
            if(n == 1) break;
            if(n % 2 == 0) n /= 2;
            else          n = (n*3) + 1;
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

AOJ Volume5 0538: IOIOI

単純に回したのでは時間切れとなったので
考え方を変更した。

P1ならIOI　　P2ならIOIOI
となるはずなので、IOIの連続出現回数をカウントしていく。
P1なら1回、P2なら２回連続で出現したらresをインクリメント
/*****************************
* 2012/07/15                 *
* AOJ_Volume5_0538           *
* IOIOI                      *
* crane                      *
******************************/
#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    while(cin >> n, n){
        int m;
        cin >> m;
       
        string s;
        cin >> s;
        int count=0, res= 0;
            for(int i=0; i<m;){
                if(s.substr(i, 3) == "IOI"){
                    count++;
                    if(n <= count) res++;
                }else {
                    count = 0;
                }
               
                if(count == 0) i++;
                else              i+=2;   
            }
        cout << res << endl;
    }
    return 0;
}

AOJ Volume11 1129: Hanafuda Shuffle (POJ1978)

問題文通りにそのまま書いてみた。


/********************************
*    2012/0623                    *
*   AOJ VOlume11 1129           *
*    POJ1978                     *
*   花札シャッフル              *
*    crane                       *
********************************/

#include<iostream>

#define MAX_N 50
int card[MAX_N];    //カード内容
int t_card[MAX_N];    //シャッフル用カードtmp

int main(){

    int n = 0;    //札の枚数
    int r = 0;    //カット回数
    int p = 0;    //p枚目から
    int c = 0;    //c枚取り出す

    while(std::cin >> n >> r, n, r){
        //配列の初期化
        for(int i=0; i<n; i++)        card[i] = i + 1;
       
        //shuffle
        for(int i=0; i<r; i++){    //カット回数r分
            std::cin >> p >> c;

            for(int j=0; j<c; j++)
                t_card[c-1-j] = card[n-p-j];

            for(int j=n-p+1; j<n; j++)
                card[j-c] = card[j];

            for(int j=0; j<c; j++)
                card[n-c+j] = t_card[j];
        }

        std::cout << card[n-1] << std::endl;

    }
    return 0;
}

AOJ Volume20 2013: Osaki

hh:mm:ss で与えられるため秒に統一する。
hh  ->*60*60
mm->*60
ss  
その時間に出発した電車、到着した電車の数をカウントする。
その時間にどれだけの電車が走っているかをカウントし、その最大値が答えになる。



 /*********************************
* 2012/0714                      *
* AOJ_Volume20_2013              *
* Osaki                          *
* crane                          *
**********************************/
#include<iostream>
#include<cstdio>
using namespace std;

#define MAX_N 24*60*60
int field[MAX_N];


int main(){
    int n;
    while(cin >> n, n){
        for(int i=0; i<MAX_N; i++)
            field[i] = 0;

        int h1,m1,s1,h2,m2,s2;
        for(int i=0; i<n; i++){
            scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
            int t1 = (h1 * 3600) + (m1 * 60) + s1;//秒に統一
            int t2 = (h2 * 3600) + (m2 * 60) + s2;
            field[t1]++;    //その時間に出発した電車をカウント
            field[t2]--;    //その時間に到着した電車をカウント
        }
       
        int m_count=0, count=0;
        for(int i=0; i<MAX_N; i++){//その時間に走っている車両数の最大値が答えになる。
            count += field[i];
            m_count = max(m_count, count);
        }
        cout << m_count << endl;       
    }
    return 0;
}

AOJ Volume2 0206: Next Trip

/****************************
* 2012/07/14                *
* AOJ_Volume2_0206          *
* Next Trip                 *
* crane                     *
*****************************/

#include<iostream>
using namespace std;

int main(){

    int pri;
    while(cin >> pri, pri){
        int res;
        bool frag = false;
        for(int i=1; i<=12; i++){
            int m,n;
            cin >> m >> n;
            pri -= m-n;
            if(pri <= 0 && frag != true){
                frag = true;
                res = i;
            }
        }
        if(frag) cout << res << endl;
        else     cout << "NA" << endl;
    }
    return 0;
}

AOJ Volume1 0149: Eye Test

判定関数においてA~Dそれぞれの範囲をわかりやすくするため
すべての下限上限を書いた。
A~Dの配列０～４だけどmap<char, int>なんかで扱っても良かったかも。

/****************************
* 2012/07/14                *
* AOJ_Volume1_0149          *
* Eye Test                  *
* crane                     *
*****************************/
//--------------------------------------//
//        判定    視力                    //
//    A    1.1以上                            //
//    B    0.6以上1.1未満                    //
//    C    0.2以上0.6未満                    //
//    D    0.2未満                            //
//--------------------------------------//

#include<iostream>
#include<map>
using namespace std;

int solve(double x);

int main(){
    int ldata[4] = {0, 0, 0, 0};
    int rdata[4] = {0, 0, 0, 0};
   
    double left, right;
    while(cin >> left >> right){
        int le = solve(left);
        int ri = solve(right);

        ldata[le]++;
        rdata[ri]++;
    }

    for(int i=0; i<4; i++)
        cout << ldata[i] << " " << rdata[i] << endl;
   return 0;
}

int solve(double x){
    if(1.1 <= x)                       return 0;
    else if(0.6<=x && x<1.1)  return 1;
    else if(0.2<=x && x<0.6)  return 2;
    else if(x<0.2)                     return 3;
}

AOJ Volume1 0134: Exit Survey

int sumでは足りないのでlong longで対応
/*****************************
* 2012/07/13                 *
* AOJ_Volume1_0134           *
* Exit_Survey                *
* crane                      *
******************************/
#include<iostream>
using namespace std;

int main(){
    int n, input;
    cin >> n;
    long long int sum = 0;
    for(int i=0; i<n; i++){
        cin >> input;
        sum += input;
    }
    cout << sum/n << endl;
    return 0;
}

AOJ Volume1 0127: Pocket Pager Input

/*********************************
* 2012/07/13                     *
* AOJ_Volume1_0127               *
* Pocket_Pager_Input             *
* crane                          *
**********************************/

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

char data[7][6] ={
    {},
    {' ','a','b','c','d','e'},
    {' ','f','g','h','i','j'},
    {' ','k','l','m','n','o'},
    {' ','p','q','r','s','t'},
    {' ','u','v','w','x','y'},
    {' ','z','.','?','!',' '}
};

int main(){

    string input;
    while(1){
        getline(cin, input);
        if(input.empty())break;

        bool frag = true;
        string output = "";
   
        if(input.length() % 2 != 0)
            frag = false;

        for(int i=0; i<input.length() && frag==true; i+=2){
                int in1 = (int) input.at(i) - '0';
                int in2 = (int) input.at(i+1) - '0';
                if(0<in1 && in1 < 7 && 0 < in2 && in2 < 6)
                    output += data[in1][in2];
                else
                    frag = false;
        }
        if(frag) cout << output << endl;
        else     cout << "NA" << endl;
    }
    return 0;
}

AOJ Volume0 013: Switching Railroad Cars

stackを用いる。

/*****************************
* 2012/07/11                 *
* AOJ_Volume0_0013           *
* Switching_Railroad_Cars    *
* crane                      *
******************************/


#include<iostream>
#include<stack>
using namespace std;

int main(){
    stack<int> data;
    int n;
    while(cin >> n){
        if(n == 0){
            cout << data.top() << endl;
            data.pop();
        }else data.push(n);
    }
    return 0;
}

AOJ Volume1 0139: Snakes

A種は，">'"の後に"="が1個以上並んだ後、"#"が来て、さらに前と同じ個数の"="が来た後、"~"（半角チルダ）で終わる。
B種は，">^"の後に "Q="が1個以上並んだ後、"~~"で終わる。

A種の例： >'====#====~        >'==#==~

B種の例： >^Q=Q=Q=Q=~~        >^Q=Q=~~

 /************************
* 2012/07/10            *
* AOJ_Volume1_0139      *
* Snakes                *
* crane                 *
*************************/

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


int main(){

    int n;
    cin >> n;

    while(n--){
        string input;
        cin >> input;
        if(input.length() <5){
            cout << "NA" << endl;
        }else{
            string s = input.substr(0,2);        //どの蛇か
            char e = input.at(input.length()-1); //A B尾判定
            char e2 = input.at(input.length()-2);//B　尾判定

            if(input.length() % 2 != 0){//lengthが偶数出ないものはAでもBでもない
                cout << "NA" << endl;
            }else if(s == ">'" && e == '~'){            //SnakeA
                bool frag_A = true;
                for(int i=2; i<input.length()/2; i++){  
                    char c1 = input.at(i);               //前から
                    char c2 = input.at(input.length()-i);//後ろから
                    if(c1 != '=' || c2 != '='){
                        cout << "NA" << endl;
                        frag_A = false;
                        break;
                     }
                }
                char a = input.at(input.length()/2 );
                if(a == '#' && frag_A) cout << "A" << endl;

            }else if(s == ">^" && e == '~' && e2 == '~'){  //SnakeB
                bool frag_B = true;
                for(int i=2; i<input.length()-2; i+=2){
                    string s1 = input.substr(i, 2);

                    if(s1 != "Q="){
                        cout << "NA" << endl;
                        frag_B = false;
                        break;
                    }
            }
                if(frag_B)cout << "B" << endl;
            }else cout << "NA"<< endl;
        }
    }
    return 0;
}

APJ Volume0 0044: Prime Number Ⅱ

/******************************
*  2012/07/09                 *
*  AOJ_Volume0_0044           * 
*  Prime_NumberⅡ             *
*  crane                      *
*******************************/


#include<iostream>
#include<cmath>
using namespace std;

#define MAX_N 50023
bool field[MAX_N];
int prime[MAX_N];
int main(){
    for(int i=2; i<MAX_N; i++){
        field[i] = true;
        prime[i] = 0;
    }

    int count = 0;
    field[0] = false;
    field[1] = false;
    for(int i=2; i<MAX_N; i++){
        if(field[i]){
            prime[count] = i;
            count++;
            for(int j=i*2; j<MAX_N; j+=i){
                field[j] = false;
            }
        }
    }
   


    int n;
    while(cin >> n){
        int a=0;
        for(int i=0; i<MAX_N; i++){
            if(prime[i] < n) a=prime[i];
            if(n < prime[i]){
                cout << a << " " <<  prime[i] << endl;
                break;
            }
        }

    }

    return 0;
}

AOJ Volume0 0083: Era Name Transformation

年、月、日を一つの数値として管理した。

/***************************
* 2012/07/09               *
* AOJ_Volume0_0083         *
* Era Name Transformation  *
* crane                    *
****************************/


//-----------------------------------//
//    meiji    1868.09.08 ～ 1912.07.29 //
//  taisho    1912.07.30 ～ 1926.12.24 //
//  showa    1926.12.25 ～ 1989.01.07 //
//  heisei    1989.01.08 ～            //
//-----------------------------------//
   
#include<iostream>
using namespace std;

int main(){
    int y, m, d;
    while(cin >> y >> m >> d){
        int data = 0;
        data = (y * 10000) + (m * 100) + d;

        if(data <18680908)
            cout << "pre-meiji" << endl;
        else if(18680908 <= data && data <= 19120729)
            cout << "meiji " << (y - 1868 + 1) << " " << m << " " << d << endl;
        else if(19120730 <= data && data <= 19261224)
            cout << "taisho " << (y - 1912 + 1) << " " << m << " " << d << endl;
        else if(19261225 <= data && data <= 19890107)
            cout << "showa " << (y - 1926 + 1) << " " << m << " " << d << endl;
        else if(19890108 <= data)
            cout << "heisei " << (y - 1989 + 1) << " " << m << " " << d << endl;
    }

    return 0;
}

AOJ Volume10 1041: Kyudo:A Japanese Art of Archery

問題通りに実装すればOK
nの値も４の倍数と親切に決めてくれているので問題なし。

 /*********************************
* 2012/07/09                     *
* AOJ_Volume10_1041              *
* Kyudo:A Japanese Art of Archery*
* crane                          *
**********************************/
#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin >> n, n){
        int tmp, sum=0;
        for(int i=0; i<n/4; i++){
            cin >> tmp;
            sum += tmp;
        }
        cout << sum << endl;
    }
    return 0;
}

AOJ Volume20 2001: Amida the city of Miracle

/***************************
* 2012/07/07               *
* AOJ_Volume20_2001        *
* Amida_the_city_of_Miracle*
* crane                    *
****************************/


#include<iostream>
using namespace std;

#define MAX_H 1001
#define MAX_N 101

int field[MAX_H][MAX_N];

int main(){
    int n,m,a;
    while(cin >> n >> m >> a, (n||m||a)){//n:縦線、m:横線、a:調べる縦線
        for(int i=1; i<MAX_H; i++){
            for(int j=1; j<=n; j++){
                field[i][j] = j;
            }
        }

        int h, p, q;    //h:横線の高さ　p,q:つながっている横線
        for(int i=0; i<m; i++){
            cin >> h >> p >> q;
            field[h][p] = q;
            field[h][q] = p;
        }

        int res= a;
        for(int i=MAX_H-1; 0<i; i--){
            res = field[i][res];
        }

        cout << res << endl;
    }
    return 0;
}

AOJ Volume20 2000: Misterious Games

/*************************
*  2012/07/07            *
*  AOJ_Volume20_2000     *
*  Misterious_Gems       *
*  crane                 *
**************************/

#include<iostream>
using namespace std;

#define FIELD 21
bool field[FIELD][FIELD];

int main(){

    int n; //宝石の個数
    while(cin >> n, n){
        for(int i=0; i<FIELD; i++)
            for(int j=0; j<FIELD; j++)
                field[i][j] = false;

        /*--宝石の位置--*/
        int xi, yi;
        for(int i=0; i<n; i++){
            cin >> xi >> yi;
            field[yi][xi] = true;
        }   

        int m;    //命令の個数
        cin >> m;

        char dj;
        int lj;
        int x = 10, y = 10;            //ロボット降下位置
        for(int i=0; i<m; i++){
            cin >> dj >> lj;        //命令取得
            while(lj--){
                switch (dj){
                case 'N':
                    y++;
                    break;
                case 'E':
                    x++;
                    break;
                case 'S':
                    y--;
                    break;
                case 'W':
                    x--;
                    break;
                }

                if(field[y][x]){
                    n--;
                    field[y][x] = false;
                }
            }
        }   
        if(n == 0) cout << "Yes" << endl;
        else       cout << "No" << endl;
    }
}

POJ_No.2386: Lake Counting

dfs。

/********************************************************************************************
*    2012/04/24                                                                                *
*    プログラミングコンテストちゃれんじブック                                                *
*    p.35 第二章 2-1すべての基本"全探索"                                                        *
*    Lake Conting (POJ NO.2386)                                                                *
*    大きさがN×Mの庭がある。そこに雨が降り、水溜りができた。水溜りは８近傍で隣接している    *
*    場合につながっているとみなす。全部でいくつの水溜りがあるか                                *
*                                                                                            *
*            8近傍***                                                                        *
*                    *w*                                                                        *
*                    ***                                                                        *
*    適当なWからはじめ、そこからつながっている部分を[.]に置き換えるという操作を繰り返す。    *
*    1回のDFSで、はじめのWとつながっているWはすべて[.]に置き換わるため、Wがなくなるまで何回    *
*    DFSを行ったかが答えになる。状態の遷移は8方向の移動の8通りで、DFSは各マスに対してたかだ  *
*    1回しか呼び出されないため、計算量はO(8×N×M)=O(N×M)となる。                            *
*                                                                                            *
*    crane                                                                                *
********************************************************************************************/

/**************************************************
**************!制約!*******************************
***************・N,M≦100**************************
**************************************************/

#include<iostream>

void dfs(int x, int y);    //[w] -> [.]

int N,M;        //縦×横 サイズ
char **field;    //庭

int main(){
    int res=0; //結果

    //庭の大きさ(入力)
    std::cin >>    N >> M;
    /*多次元配列確保*/
    field = new char*[N];
    for(int i=0; i<M; i++){
        field[i] = new char[M];
    }
    //庭作成
    for(int i=0; i<N;i++){
        for(int j=0; j<M; j++){
            std::cin>> field[i][j];
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(field[i][j] == 'W'){
                //Wが残っているならそこからdfsをはじめる
                dfs(i, j);
                res++;
            }
        }
    }
    //結果出力
    std::cout << res << std::endl;
    int ff;
    std::cin >> ff;
    return 0;
}

void dfs(int x, int y){
    //今いるところを.に置き換える
    field[x][y] = '.';

    //移動する8方向をループ
    for(int dx=-1; dx<=1; dx++){
        for(int dy=-1; dy<=1; dy++){
            //x方向にdy y方向にdy移動した場所を(nx,ny)とする
            int nx = x + dx, ny = y + dy;

            //nxとnyが庭の範囲内かどうかとfield[nx][ny]が水溜りかどうかを判定
            if(0 <= nx && ny < N && 0 < ny && ny < M && field[nx][ny] == 'W')    dfs(nx, ny);
        }
    }
}

AOJ Volume5 0543:Receipt

/********************************
*    2012/07/03                    *
*    AOJ Volume5 0543            *
*    Receipt                        *
*    crane                        *
*********************************/

#include<iostream>
using namespace std;


int main(){

    int s = 0;
    while(cin >> s, s){    //総額=0で終了
        for(int i=0; i<9; i++){
            int pri=0;
            cin >> pri;
            s = s - pri;
        }
        cout << s << endl;
    }
    return 0;
}

AOJ Volume2 0217: Walking in the Hospital

/****************************************
*    2012/06/30                            *
*    AOJ Volume2 0217                    *
*        Walking in the Hospital            *
*   crane                                *
*****************************************/

#include<iostream>
using namespace std;

int main(){
    int n;    //データ数
   
    while(cin >> n, n){
        int p, d1, d2;
        int m_p=0, md=0;
        for(int i=0; i<n; i++){
            cin >> p >> d1 >> d2;
            if(d1+d2 > md){
                m_p = p;
                md = d1 + d2;
            }
        }

        cout << m_p << " " << md << endl;
    }
    return 0;
}

AOJ Volume2 0238: Time To Study

/********************************************
*    2012/07/03                                *
*    AOJ Volume2 0238                        *
*    Time To Study                            *
*    crane                                              *
*********************************************/
#include<iostream>
using namespace std;

int main(){
    int t;
    while(cin >> t, t){//目標時間
        int n;
        cin >> n;        //勉強回数

        int sum = 0;
        int st, et;        //開始時間, 終了時間
        for(int i=0; i<n; i++){
            cin >> st >> et;
            sum += et - st;
        }
       
        if( t <= sum)    cout << "OK" << endl;
        else{
            cout << t - sum << endl;
        }
    }
    return 0;
}

AOJ Volume2 0239: Calorie Counting

/************************************
*    2012/07/03                        *
*    AOJ Volume2 0239                *
*    Calorie Counting                *
*    crane                            *
*************************************/


#include<iostream>
#define MAX_N 1000
using namespace std;

//[p:タンパク質, q:脂質, r:炭水化物]
/*-------------------------------------------------*/
//        1gあたり                                    //
//        タンパク質,炭水化物->4kcal                    //
//        脂質               ->9kcal   
/*-------------------------------------------------*/
struct {
    int num;
    int p;
    int q;
    int r;
} num[MAX_N];


int main(){
    int n;//お菓子の数
    while(cin >> n, n){
       
        for(int i=1; i<=n; i++)
            cin >> num[i].num >> num[i].p >> num[i].q >> num[i].r;

        int P, Q, R, C;    //P:タンパク質, Q:脂質, R:炭水化物, C:制限摂取カロリー
        cin >> P >> Q >> R >> C;
        bool frag = true;
        for(int i=1; i<=n; i++){
            int sum = (4 * num[i].p) + (9 * num[i].q) + (4 * num[i].r);   
           
            if(num[i].p <= P && num[i].q <= Q && num[i].r<=R && sum <= C){
                cout << num[i].num << endl;
                frag = false;
            }
        }
        if(frag)    cout << "NA" << endl;
    }
    return 0;
}

AOJ Volume0 0031: Weight

/***********************
*  2012/07/04          *
*  AOJ Volume0 0031    *
*  Weight              *
*  crane               *
************************/

//---------------------------//
//       2 )  6   ---0       //
//         ------            //
//       2 )  3   ---1       //
//         ------            //
//            1              //
//---------------------------//
#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        bool f = false;
        while(n != 1){
            if(n%2 == 1){
                if(f) cout << " " << pow(2.0, count);
                else{
                    f = true;
                    cout << pow(2.0,count);
                }
            }
            n/=2;
            count++;
        }
        if(f) cout << " ";
        cout << pow(2.0, count) << endl;
    }
    return 0;
}

AOJ Volume0 0053: Sum of Prime Numbers

エラトステネスの篩で素数テーブルを作成する際、
確定した素数をvectorに貯めておく。

 /****************************
*  2012/07/04               *
*  AOJ Volume0 0053         *
*  Sum_of_Prime_Numbers     *
*  crane                    *
*****************************/

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

#define MAX_N 1000000

bool field[MAX_N];
int prime[MAX_N];
int main(){
  
    vector<int> prime;
    /* 素数テーブル作成 */
    field[0] = false; field[1] = false;
    for(int i=0; i<MAX_N; i++){
        field[i] = true;
    }

    int count = 0;
    prime.push_back(0);
    for(int i=2; i<MAX_N; i++){
        if(field[i]){
            prime.push_back(i + prime[count]);
            count++;
            for(int j=i*2; j<MAX_N; j+=i)
                field[j] = false;
        }
    }

    int n;
    while(cin >> n, n){
        cout << prime[n] << endl;
    }

}

AOJ Volume0 0054: Sum of Nth decimal places

紙にひっ算を試しに書いてそれを参考にするとやりやすい。

/****************************************
*    2012/06/29                            *
*    AOJ Volume0 0054                    *
*    Sum of Nth decimal places            *
*     crane                                        *
*****************************************/
#include<iostream>
using namespace std;

int main(){
    int a, b, i;

    while(cin >>  a >> b >> i){
        int sum = 0;
        bool frag = false;
        while(i--){
            a = (a % b) * 10;
            if(frag = true)
                sum += a/b;
            frag = true;
        }
        cout << sum << endl;
    }
}

AOJ Volume0 0059: Intersection of Rectangles

/*************************
* 2012/07/04                           *
* AOJ Volume0 0059                 *
* Intersection of Rectangles      *
* crane                                      *
**************************/

//---------------------------------------------//
//   xa1 <= xb2    ya1 <= yb2                  //
//   xb1 <= xa2    yb1 <= ya2                  //
//   であれば、長方形は重なっている部分が  //
//   ある。とかんがえられる。                     //
//--------------------------------------------//

#include<iostream>
using namespace std;

struct{
    double x;
    double y;
} data[4];

int main(){
    while(    cin >> data[0].x >> data[0].y >> data[1].x >> data[1].y >> data[2].x >> data[2].y >> data[3].x >> data[3].y){
        bool frag = false;
        if(data[0].x <= data[3].x && data[2].x <= data[1].x)
            if(data[0].y <= data[3].y && data[2].y <= data[1].y)
                frag = true;

        if(frag) cout << "YES" << endl;
        else     cout << "NO"  << endl;
    }
}

AOJ Volume0 0067: The Number of Island

dfs.

/****************************************
*    2012/07/03                            *
*    AOJ Volume0 0067                    *
*    The Number of Island                *
*    crane                                *
*****************************************/
#include<iostream>
#include<string>
using namespace std;


int field[12][12];

void dfs(int x, int y);

int main(){
    string input;
    while(getline(cin,input)){
        if(input.empty())
            return 0;
        for(int i=0; i<12; i++){
            for(int j=0; j<12; j++){
                field[i][j] = input[j]-'0';
            }
            getline(cin, input);
        }

        int count = 0;
        for(int i=0; i<12; i++){
            for(int j=0; j<12; j++){
                if(field[i][j] == 1){
                    dfs(j, i);
                    count++;
                }
            }
        }
        cout << count << endl;   
    }
    return 0;
}


void dfs(int x, int y){

    int dx[] = {-1, 0, 1, 0};
    int dy[] = { 0, 1, 0, -1};

    field[y][x] = 0;

    for(int i=0; i<4; i++){
        int nx = x + dx[i];    int ny = y + dy[i];
        if(0<=nx && 0<=ny && nx<12 && ny<12 && field[ny][nx]==1)
            dfs(nx, ny);
    }
   
}

AOJ Volume0 0077: Run Length

/********************************
*    2012/05/16                    *
* AOJ Volume0 0077 Run Length    *
* wrote crane                    *
*********************************/

#include<string>
#include<sstream>
#include<iostream>


std::string input;
std::string output;
int main(){

    //while(getline(std::cin, input) && input.length() != 0){
    while(std::cin >> input){
        output="";        //出力用文字列初期化
        int i=0;
        while(i < input.length()){
            if(input.at(i) == '@'){
                int tmp;
                std::stringstream ss;
                ss << input.at(i+1);
                ss >> tmp;       
                for(int j=1; j<tmp; j++){
                    output += input.at(i+2);
                }
            i++;
            }else{
                output += input.at(i);
            }   
        i++;
        }
        std::cout << output << std::endl;
    }
    return 0;
}

AOJ Volume0 0078: Magic Square

1. 中央のマス目のちょうど一つ下のマス目に１をいれる。
2. 次の数字を右斜め下のマス目にいれる。
   ただし、数字をいれようとしたマス目が正方形からはみ出している場合、すでに数字が埋まっている場合は以下の方法に従って数字を入れるマス目を探す。
• 右にはみ出した場合には、同じ行の左はしに、左にはみ出した場合には、同じ行の右はしに、下にはみ出した場合には、同じ列の一番上に数字をいれる。
• 数字をいれようとしたマス目が埋まっているときには、その埋まっているマス目の左斜め下のマス目にいれる。
3. 全てのマス目が埋まるまで２を繰り返す。 

/*********************************
*   2012/07/04                   *
*   AOJ Volume0 0078             *
*   Magic Square                 *
*   crane                        *
**********************************/
//左上を(1,1) 右下を(n,n)と考える。


#include<iostream>
#include<cstdio>
using namespace std;

#define MAX_N 15+1
#define INF 500

int field[MAX_N][MAX_N];

int main(){
    int n;
    while(cin >> n, n){
       
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                field[i][j] = INF;

        //centerの下
        int x = (n/2) + 1;
        int y = x+1;

        for(int i=1; i<=n*n; i++){//すべて埋まるまで
            bool frag = true;
            while(frag){
                if( n < y)    y = 1;//下にはみ出し
                if( n < x)  x = 1;//右にはみ出し
                if( x < 1)  x = n;//左にはみ出し

                if(field[y][x] == INF){
                    field[y][x] = i;
                    x++; y++;
                    frag = false;
                }else if(field[y][x] != INF){//もう値が入っていたら
                    x--;
                    y++;                   
                }
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                printf("%4d", field[i][j]);   
            }
            cout << endl;
        }
    }
}

AOJ Volume0 0084: Search Engine

/********************************
*    2012/07/03                    *
*    AOJ Volume0 0084            *
*    Search Engine                *
*    crane                        *
*********************************/

#include<iostream>
#include<string>
#include<queue>
using namespace std;
string str;
int main(){
    getline(cin,str);
    queue<char> tmp;
    queue<char> que;
    int count_t = 0;
    int count_q = 0;
    bool frag = false;
    for(int i=0; i<str.length(); i++){
        char c = str.at(i);
        if(c == ' ' || c=='.' || c==','){
            if( 2<count_t && count_t < 7){
                if(frag == true){
                    que.push(' ');
                    count_q++;
                }
                frag = true;
                for(int i=0; i<count_t; i++){
                    que.push(tmp.front());
                    tmp.pop();
                    count_q++;
                }
            }else{
                for(int i=0; i<count_t; i++){
                    tmp.pop();
                }
            }
            count_t=0;
        }else{
            tmp.push(c);
            count_t++;
        }
    }

    for(int i=0; i<count_q; i++){
        cout << que.front();
        que.pop();
    }
    cout << "\n";
    return 0;
}

AOJ Volume0 0092: Square Searching

 動的計画法で解く。
[i][j] = [i-1][j-1]と[i][j-1]と[i-1][j]の最小値
0行目と０列目では[i-1]や[j-1]ができない。
->fieldの左上部分を(1,1)にして0行目と0列目を0で初期化しておく。
 ※[i][j]='*'なら[i][j]=0とする。
/*****************************
* 2012/07/06                 *
* AOJ Volume0 0092           *
* Square Searching           *
* crane                      *
******************************/

#include<iostream>
using namespace std;

#define MAX_N 1000
char field[MAX_N][MAX_N];
int data[MAX_N][MAX_N];
int main(){
   
    int n;
    while(cin >> n, n){
        for(int i=0; i<n; i++){
            data[0][i] = 0;
            data[i][0] = 0;
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                cin >> field[i][j];
                data[i][j] = 0;
            }
        }

        int max = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(field[i][j] ==  '*'){
                    data[i][j] = 0;
                }else{
                    data[i][j]=min(data[i-1][j-1],min(data[i][j-1],data[i-1][j]))+1;
                    if(max < data[i][j])
                        max = data[i][j];
                }
            }
        }
           
        cout << max << endl;

    }
    return 0;
}

AOJ Volume10 1019: Vampairish Night

/********************************
*  2012/07/05                   *
*  AOJ Volume10 1019            *
*  Vampairish Night             *
*  crane                        *
*********************************/
#include<iostream>
using namespace std;

#define MAX_N 100

int main(){
   
    int n,k;
   
        while(cin >> n >> k, (n||k)){
            int blood[MAX_N];
            for(int i=0; i<k; i++)
                cin >>  blood[i];   
           
            bool frag = true;
            int data =0;
            for(int i=0; i<n; i++){
                for(int j=0; j<k; j++){
                    cin >> data;
                    blood[j] -= data;
                    if(blood[j] <0){
                        frag = false;
                    }
                }
            }
            if(frag)    cout << "Yes" << endl;
            else        cout << "No" << endl;
        }
    return 0;
}

AOJ Volume11 1137:Numeral System

/****************************
*    2012/06/23                                *
*    AOJ1137    Numeral System       *
*    crane                                          *
*****************************/
#include<iostream>
#include<string>
using namespace std;

char c[4] = {'m', 'c', 'x', 'i'};
int v[4] = {1000, 100, 10, 1};

int toint(string str);

int main(){

    int N=0;
    cin >> N;
    string in1,in2;

    while(N--){
        cin >> in1 >> in2;
        int sum = toint(in1) + toint(in2);    //合計計算
       
       
        for(int i=0; i<4; i++){
            int d = 0;
            while(sum >= v[i]){
                sum-= v[i];
                d++;
            }
            if(d > 1) cout << d;
            if(d > 0) cout << c[i];
        }
        cout << endl;
    }
    return 0;
}


int toint(string str){
    int result = 0;

    int d=1;
    for(int i=0; i<str.size(); i++){
        if('0' <= str[i] && str[i] <= '9')
            d = str[i] - '0';
        else{
            for(int j=0; j<4; j++){
                if(str[i] != c[j]){ continue;}
                result += v[j] * d;
                d = 1;
                break;
            }
        }
    }
    return result;
}

AOJ Volume11 1141: Dirichlet's Theorem on Arithmetic Progressions

エラトステネスの篩で素数を求めておく。

/****************************************************
*    2012/06/23                                        *
*    AOJ Volume11 1141                                *
*    Dirichlet's Theorem on Arithmetic Progressions    *
*    ディリクレの算術級数定理                        *
*    crane
*****************************************************/
#include<iostream>
#include<cmath>
using namespace std;

#define MAX_N 1000000

int field[MAX_N];

int main(){
    /*素数テーブル作成*/
    field[0] = 0; field[1] = 0;
    for(int i=2; i<MAX_N; i++)    field[i] = 1;//初期化
    for(int i=2; i<sqrt((double)MAX_N)+1; i++){
        if(field[i] == 1)
            for(int j=i*2; j<MAX_N; j+=i)
                field[j] = 0;
    }

    int a,d,n;    //a->aからはじめる,  dずる増える,　n番目目の素数
    while(cin >> a >> d >> n, (a||d||n)){
        int cnt = 0;
        while(1){
            if(field[a]==1) cnt++;
            if(cnt==n) break;
            a += d;
        }
        cout << a << endl;
    }
    return 0;
}

AOJ Volume11 1147: ICPC Score Totalizer Software

入力をソートし、最大値、最小値を除外する。

/****************************************
*    2012/07/02                            *
*    AOJ Volume11 1147                    *
*    ICPC Score Totalizer Software        *
*    crane                                *
*****************************************/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define MAX_N 100

int main(){
    int n;   
    while(cin >> n, n){
        vector<int> data;
       
        int input;
        for(int i=0; i<n; i++){
            cin >>input;
            data.push_back(input);
        }

        sort(data.begin(), data.end());

        data[0]   =  0;
        data[n-1] =  0;
        int sum = 0;
        for(int i=0; i<n; i++)
            sum += data[i];
        cout << sum/(n-2) << endl;
    }
    return 0;
}

AOJ Volume11 1148: Analyzing Login/Logout Records

どのPCにログインし、どのPCからログアウトしたかは考えず、
ログイン数、ログアウト数を利用する。

/********************************************
*   2012/07/02                              *
*   AOJ  Volume11 1148                      *
*   Analyzing Login/Logout Records          *
*   crane                                   *
*********************************************/
#include<iostream>
#define MAX_R 1000
using namespace std;

int main(){
    int n,m;                                            //n->PC数    m->学生数
    while(cin >> n >> m, (n||m)){
       
        int r;                                            //r->利用記録数   
        cin >> r;
        int it[MAX_R], in[MAX_R], im[MAX_R], is[MAX_R];
        for(int i=0; i<r; i++)
            cin >> it[i] >> in[i] >> im[i] >> is[i];

        int q;
        cin >> q;                                        //q->質問数
        for(int i=0; i<q; i++){
            int ts, te, tm;                               
            cin >> ts >> te >> tm;

            int sum = 0, cnt=0, s = 0, e = 0;
            for(int j=0; j<r; j++){
                if(im[j] == tm){
                    if(is[j] == 1){                        //ログイン
                        if(cnt==0){
                            if(it[j] < te){
                                if(ts < it[j])    s = it[j];   
                                else            s = ts;
                            }else                s = te;
                        }
                        cnt++;
                    }else if(is[j] == 0){                //ログアウト
                        cnt--;
                        if(cnt==0){
                            if(it[j] < te)    e = it[j];
                            else            e = te;
                            if(s <= e && ts<e)    sum += e - s;
                        }else                e = te;
                    }
                }
            }
        if(cnt > 0)    sum += te - s;
        cout << sum << endl;
        }
    }
    return 0;
}

AOJ Volume11 1153: Equal Totaol Score

/****************************************
*    2012/06/25                            *
*    AOJ Volume11 1153    Equal Totaol Score          *
*   crane                                                                   *
*****************************************/
#include<iostream>
using namespace std;

#define MAX_N 100
#define MAX_M 100

int n_field[MAX_N];
int m_field[MAX_M];
int n_c[MAX_N];    //コピー
int m_c[MAX_M];    //コピー

int n;    //太郎のカード
int m;    //花子のカード

int main(){

    while(cin >> n >> m, (n||m)){
        int sn=0, sm=0;       
       
        for(int i=0; i<n; i++){
            cin >> n_field[i];
            sn += n_field[i];    //合計n側
        }
        for(int i=0; i<m; i++){
            cin >> m_field[i];
            sm += m_field[i];    //合計m側
        }
       
        int li=0, lj=0, l_sum=1000;
        int c_sn, c_sm;        //合計のコピー

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                c_sn = sn;
                c_sm = sm;
               
                c_sn = c_sn - n_field[i] + m_field[j];
                c_sm = c_sm - m_field[j] + n_field[i];
               
                if(c_sn == c_sm)
                    if(n_field[i] + m_field[j]  <= l_sum){
                        l_sum = n_field[i] + m_field[j];
                        li = n_field[i];
                        lj = m_field[j];
                    }
            }
        }
        if(l_sum == 1000)
            cout << -1 << endl;
        else
            cout << li << " " << lj << endl;
    }
    return 0;
}

AOJ Volume11 1154:Monday-Suturday Prime Factors

/****************************************************
*    2012/06/25                                        *
*    AOJ Volume11 1154 Monday-Saturday Prime Factors *
*    wrote crane                                        *
*****************************************************/
#include<iostream>
#include<cmath>
using namespace std;

#define MAX_N 300000

int field[MAX_N];
bool res[MAX_N];

int main(){
    int input;
    while(cin >> input, input != 1){
        cout << input << ":";

        int a=0;
        for(int i=6; i<MAX_N; i++)    res[i] = 0;
       
        field[a++] = 6;        res[6] = 1;
        for(int i=7; i<MAX_N; i+=7){
            if(i+1<MAX_N){
                field[a++] = i+1;
                res[i+1] = 1;
            }
            if(i+6<MAX_N){
                field[a++] = i+6;
                res[i+6] = 1;
            }               
        }
       
        for(int i=0; i<a; i++)
                for(int j=field[i]*2; j<MAX_N; j=j+field[i])
                    res[j] = 0;
   
        for(int i=1; i<=input; i++)
            if(res[i] == 1)
                if(input % i == 0)
                    cout << " " <<i;
        cout << "\n";
   
    }
    return 0;
}