AOJ Volume0 0033: Ball

Bの筒に入れて問題無いか確認→問題なければBを更新
Bの筒に入れられない場合はCの筒で同様に
どちらにも入れられない→Noを出力
すべて入れられたら→Yes


/****************************************
* 2012/10/04　　　　　　　　　　　　　　　　　　　　　*
* AOJ Volume0 0033 Ball　　　　　　　　　　　　　　*
* crane　　　　　　　　　　　　　　　　　　　　　　　　　*
*****************************************/


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

int main(){
　　int n = 0;
    cin >> n;

    queue<int> data;
    while(n--){
        data.empty();
        int num = 10, input = 0;
        while(num--){
            cin >> input;
            data.push(input);
        }

        int b = 0, c = 0, count = 10;
        bool frag = true;
        while(count--){
            int f = data.front();
            if(f > b)      b = f;
            else if(f > c) c = f;
            else frag = false;
                   
            data.pop();
        }

        if(frag) cout << "YES" << endl;
        else     cout << "NO"  << 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;
}

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 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 Volume0 0047 Cup Game

/******************************
*   2012/0516                 *
*   AOJ Volume0 0047 CupGame  *
*   crane                     *
*******************************/

#include<iostream>
#include<string>

int main(){
    int va[]={1, 0, 0};

    std::string input;
    while(getline(std::cin,input) && input.length() != 0){      
        int in1 = input.at(0) - 'A';
        int in2 = input.at(2) - 'A';
        int tmp = va[in1];
        va[in1] = va[in2];
        va[in2] = tmp;
    }

    for(int i=0; i<3; i++)
        if(va[i]==1){
            char res = i + 'A';
            std::cout << res << std::endl;
    }
    return 0;
}

AOJ Volume0 0031: Weight

10進数から2進数変換の考え方で解いていく。
/***********************
*  2012/07/04             *
*  AOJ Volume0 0031 *
*  Weight                     *
*  crane                       *
************************/
#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 Volume 0030:Sum of Integers

無駄が多いのでそのうち修正

/******************************************
* 2012/06/29                              *
* AOJ Volume0 0030 Sum of Integers        *
* wrote crane                             *
*******************************************/
#include<iostream>
using namespace std;

int num[] ={ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=0; //ｎ個の数字
int s=0; //ｎ個の数字の和がsとなる

int count;
void solve(int x, int sum, int c);

int main(){
 while(cin >> n >> s, (n||s)){
  count = 0;
  solve(n, s, 0);
  cout << count << endl;
 }
 return 0;
}

void solve(int x, int sum, int c){//x->ｎ個の数字 ,  sum->和  c->numカウント用
 if(x == 0 && y==0 && c==10){ 
  count++;
  return;
 }else if(9<c || x<0 || y<0){
  return;
 }else{
  int a=y-num[c];
  c++;
  solve(x, y, c); //足さない
  solve(x-1, a,c);//足す
 }
 return;
}

AOJ Volume0 0025: Hit and Blow

/***********************
*   2012/06/29         *
*   AOJ Volume0 0025   *
*   Hit and Blow       *
*   crane              *
************************/

#include<iostream>
using namespace std;

int main(){

    int a[4]; //Aさんの思い浮かべた４つの数字
    int b[4]; //Bさんの思い浮かべた４つの数字

    while(cin >> a[0] >> a[1] >> a[2] >> a[3]){
        int hit=0;
        int blow=0;

        for(int i=0; i<4; i++)
            cin >> b[i];

        for(int i=0; i<4; i++)
            for(int j=0; j<4; j++)
                if(a[i] == b[j])
                    if(i==j)
                        hit++;
                     else
                        blow++;
         cout << hit << " " << blow << endl;
    }
    return 0;
}

AOJ Volume0 0019: Factorial

20!までを考えるとint ではオーバーフローしてしまう。

long long intで対応

/********************

* 2012/03/22        *

* AOJ Volume0 0019  *

* Factorial         *

* crane             *

*********************/

#include<iostream>

using namespace std;

int main(){

    int n = 0;

    long long int result = 1;

    while(cin >> n){

        for(int i=1; i<=n; i++)

            result *= i;

        cout << result << endl;

    }

    return 0;

}
}

AOJ Volume0 0018: Sorting Five Number

何ヶ月か前にコーディングしたsort()を使わないものと今回コーディングしたsort()

を２つ

※降順注意

・昔の

/********************
*  2012/03/22       *
*  crane            *
*********************/
//降順に並び替え
#include<iostream>
using namespace std;

int Sorts_desc_order(int input[]);

int main(){
    int input[5]; //5つの入力数値
    for(int i=0; i<5; i++){
        cin >> input[i];
    }

    Sorts_desc_order(input);
    cout << input[0] << " "<<
    input[1] << " "<< input[2] << " "<< input[3] << " "<< input[4]<< "\n";
    return 0;
}

int Sorts_desc_order(int input[]){
    int tmp; //入れ替え退避用
    for(int i=4; i>=0; i--){
       for(int j=0; j<i; j++){
           if(input[j] < input[j+1]){
                tmp = input[j+1];
                input[j+1] = input[j];
                input[j] = tmp;
            }
        }
    }
    return 0;
}

・今回の

/***********************
*  2012/07/04          *
*  AOJ Volume0 0018    *
*  Sorting Five Numbers*
*  crane               *
************************/

#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;

int main(){
    int in[5];
    for(int i=0; i<5; i++)
        cin >> in[i];

    sort(in, in+5, greater<int>());

    cout << in[0];
    for(int i=1; i<5; i++)
        cout << " " << in[i];
    cout << endl;
}

AOJ Volume0 0017: Caesar Cipher

"the " , "this", "that"のいずれかが見つかるまでシフトする。

キーは3つだったため、配列で回さずそのままifで通した。

/*************************
*  2012/07/03            *
*  AOJ Volume0 0017      *
*  Caesar Cipher         *
*  crane                 *
**************************/

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

int main(){
    string input;
    while(getline(cin, input)){
 
        for(int i=0; i<26; i++){
            for(int j=0; j<input.length(); j++){
                if('a'<=input.at(j) &&  input.at(j) <='z')
                    input.at(j) = ((input.at(j) - 'a' + 1) % 26) + 'a';
            }
            if(input.find("the")!=-1 || input.find("this")!=-1 || input.find("that")!=-1){
                break;
            }
        }
        cout << input << endl;
    }
    return 0;
}