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 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 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;
}

AOJ Volume11 1155: How can I satisfy thee? Let me count the ways...

問題文に
<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)
とあったので一文字目にP Q Rはないと考えてcase文で一文字ずつ処理。


/****************************************************
*   2012/06/30                                                              *
*    AOJ Volume11 1155                                                  *
*    How can I satisfy thee? Let me count the ways...            *
*    crane                                                                      *
*****************************************************/

/*------------------------------------------------------------------------*
    <formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)
    ->一文字目にP Q Rはなし
*--------------------------------------------------------------------------*/


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

#define MAX_L 80


string in;
int pos;
int Vp,Vq,Vr;

int formula();

int main(){
    while(cin >> in){
        if(in == ".") break;

        int result = 0;                        //結果の初期化
        for(int p=0; p<3; p++)
            for(int q=0; q<3; q++)
                for(int r=0; r<3; r++){
                    Vp=p; Vq=q; Vr=r;
                    pos = 0;
                    if(formula()==2) result++;
                }
       
        cout << result << endl;
    }
    return 0;
}



int formula(){
    char c = in.at(pos);　　　　//一文字読む
    pos++;

    if(isdigit(c))        　　　　　//数字なら数値を返す
        return c-'0';
   
    switch(c){
    case 'P':
        return Vp;
        break;
    case 'Q':
        return Vq;
        break;
    case 'R':
        return Vr;
        break;
    case '-':
        return 2-formula();
        break;
    case '(':
        int a = formula();        //（）中の演算子左側
        int tmp=0;                //演算子用フラグ
        if(in.at(pos) == '*')
            tmp = 1;
        pos++;
        int b = formula();        //() 中の演算子右側
        pos++;                    　//)を飛ばすためpos++

        /*　* だった場合*/
        if(tmp == 1){
            return min(a, b);
        }else{
        /*  + だった場合*/
            return max(a, b);
        }
        break;
    }
}

AOJ Volume11 1159: Next Mayor

/************************************
* 2012/06/18                        *
*    AOJ Volume11 1159               *
*    Next Mayor                        *
*    crane                            *
*************************************/

#include<iostream>
#define MAX_N 50

int n, p;
int candidate[MAX_N];    //それぞれの候補者の持つ石の数

int main(){

    while(std::cin >> n >> p, (n||p)){                //n->候補者の数  p->小石の総数
        int turn = 0;                                //候補者ターン
        for(int i=0; i<n; i++) candidate[i] = 0;    //候補者も持石個数初期化
        int w = p;                                   
       
        while(1){
            if(w==0){
                w += candidate[turn];
                candidate[turn] = 0;
            }else{
                w--;
                candidate[turn]++;
                if(candidate[turn] == p)
                    break;
            }
           
            turn = (turn+1) % n;//次の人へ
        }
        std::cout << turn << std::endl;
    }
    return 0;
}

AOJ Volume11 1160: How Many Islands

dfsを使用


/********************************************
*   2012/06/18                                *
*    AOJ Volume11 1160                        *
*    How Many Islands?                        *
*********************************************/

//--------------------------------------------------//
//        海->0        陸->1                            //
//--------------------------------------------------//
#include<iostream>

#define MAX_N 50
int field[MAX_N][MAX_N];

/*  w:横  h:縦*/
int w, h;       

void dfs(int x, int y);    //dfs処理用

int main(){
    while(std::cin >> w >> h, w, h){    //地図情報入力
        int result = 0;                 //結果個数初期化
       
        /*地図作成*/
        for(int i=0; i<h; i++)        //縦
            for(int j=0; j<w; j++)    //横
                std::cin >> field[i][j];

        /*島破壊*/
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(field[i][j] == 1){
                    /*島があったら*/
                    dfs(j,i);
                    result++;
                }
            }
        }
        std::cout << result << std::endl;//結果出力
    }
    return 0;
}



void dfs(int x, int y){
    int a[8] = {-1, -1, -1, 0, 1, 1, 1, 0};//横
    int b[8] = {-1,  0,  1, 1, 1, 0,-1,-1};//縦

    //今いるところを0にする
    field[y][x] = 0;

    /* 移動する８近傍をループ*/
    for(int i=0; i<8; i++){
        //移動先 (nx, ny)
        int nx = x + a[i], ny = y + b[i];
       
        //移動先が地図上か判定 & 移動先が島かどうか判定
        if( 0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx]==1)
            dfs(nx, ny);
    }
}

AOJ Volume11 1165: Pablo Squarson's Headache

/************************************
*    2012/06/26                        *
*    AOJ Volume11 1165                *
*    Pablo Squarson's Headache        *
*    wrote crane                        *
*************************************/

#include<iostream>
using namespace std;
#define MAX_N 200
int field[MAX_N][2]; //[][0]->x [][1]->y

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

int main(){
    int n;
     while(cin >> n,n){
         int x=0;int y=0;

         int ni, di;
         field[0][0] = 0;
         field[0][1] = 0;
         for(int i=1; i<n; i++){
             cin >> ni >> di;
             field[i][0] = field[ni][0] + dx[di];
             field[i][1] = field[ni][1] + dy[di];
         }

         int xmin=10000, xmax=-10000;
         int ymin=10000, ymax=-10000;
         for(int i=0; i<n; i++){
             if(field[i][0] < xmin) xmin =field[i][0];
             if(field[i][0] > xmax) xmax =field[i][0];
             if(field[i][1] < ymin) ymin =field[i][1];
             if(field[i][1] > ymax) ymax =field[i][1];
         }
         x = xmax - xmin + 1;
         y = ymax - ymin + 1;
         cout << x << " "<< y << endl;;
     }
    return 0;
}

AOJ Volume11 1172: Chebyshev's Theorem

エラトステネスの篩で素数テーブルを作成しておく。

 /************************
* 2012/06/30                     *
* AOJ Volume11 1172        *
* Chebyshev's Theorem    *
* crane                             *
*************************/


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

#define MAX_N 246913

bool field[MAX_N];

int main(){

    field[0] = false;
    field[1] = false;
    for(int i=2; i<MAX_N; i++)    field[i] = true;

    for(int i=2; i<sqrt((double)MAX_N)+1; i++)
        if(field[i])
            for(int j=i*2; j<MAX_N; j+=i)
                field[j] = false;

    int n = 0;
    while(cin >> n, n){
        int count = 0;
        for(int i=n+1; i<=2*n; i++)
            if(field[i])
                count++;
        cout << count << endl;
    }
    return 0;
}

AOJ Volume11 1173: The Balance of the World

指定された括弧以外は無視していく。

/************************************************
*    2012/06/30                                    *
*    AOJ_Volume11_1173_                            *
*    The_Balance_of_the_World                    *
*    crane                                        *
*************************************************/

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


string input;

int main(){

    while(getline(cin, input)){
        stack<char> str;
        if(input.at(0) == '.')    break;

        bool frag = true;
        int i=0;
        while(1){
            if(!frag)    break;

            char c = input.at(i);
            i++;
            if(c == '.')    break;

            switch(c){
            case '(':
            case '[':
                str.push(c);
                break;
            case ')':
            case ']':
                if(!str.empty()){
                    char c2 = str.top();
                    str.pop();
                    if(c2 == '(' && c == ']')
                        frag = false;
                    else if(c2 == '[' && c == ')')
                        frag = false;
                }else{
                    frag = false;
                }
                break;
            }
        }
        if(frag&& str.empty()) cout << "yes" << endl;
        else                   cout << "no" << endl;
    }
    return 0;
}