AOJ Volume 0 (0040-0059)

はい。
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?volumeNo=0

0040: Affine Cipher

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

kz gcd(kz a,kz b) { if(b==0) return a; else gcd(b,a%b); }

int main(){
    int mod=1000000007;
    int n,len,x,y;
    char s[260];
    scanf("%d",&n);
    while (fgets(s,260,stdin)!=NULL) {
        len=strlen(s)-1;
        bool flg=0;
        for (int a=0;a<26;++a) {
            if (gcd(a,26)!=1) continue;
            for (int b=0;b<26;++b) {
                char chk[len];
                for (int c=0;c<len;++c) {
                    if (islower(s[c])) {
                        chk[c]=(((s[c]-'a')*a+b)%26)+'a';
                    }
                }
                for (int d=0;d<len;++d) {
                    if (!strncmp(&chk[d],"this",4) || !strncmp(&chk[d],"that",4)) {
                        x=a;
                        y=b;
                        flg=1;
                    }
                }
            }
        }
        char ans[len];
        if (flg && len>3) {
            for (int i=0;i<len;++i) {
                if (islower(s[i])) {
                    printf("%c",((s[i]-'a')*x+y)%26+'a');
                } else {
                    printf("%c",s[i]);
                }
            }
            printf("\n");
        }
        flg=0;
    }
    return 0;
}

暗号はよく分からず。。1行まとめて読み込みが fgets(s,260,stdin) したのと、charで受け取った文字列の比較を !strncmp(&chk[d],"this",4) などと書くのをいつでも出来るように。

0041: Expression

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
int d[4];
bool f=0;
const char *op="+-*";

int cal(int a,int o,int b){
    if(o==0) return a+b;
    if(o==1) return a-b;
    return a*b;
}

bool sol(int a,int b,int c) {
    f++;
    if (cal(cal(cal(d[0],a,d[1]),b,d[2]),c,d[3])==10) {
        printf("(((%d %c %d) %c %d) %c %d)\n",d[0],op[a],d[1],op[b],d[2],op[c],d[3]);
        return true;
    }
    if (cal(cal(d[0],a,d[1]),b, cal(d[2],c,d[3]))==10) {
        printf("((%d %c %d) %c (%d %c %d))\n",d[0],op[a],d[1],op[b],d[2],op[c],d[3]);
        return true;
    }
    if (cal(cal(d[0],a, cal(d[1],b,d[2])),c,d[3])==10) {
        printf("((%d %c (%d %c %d)) %c %d)\n",d[0],op[a],d[1],op[b],d[2],op[c],d[3]);
        return true;
    }
    return f=0;
}

bool jg() {
    for (int i=0;i<3;++i) {
        for (int j=0;j<3;++j) {
            for (int k=0;k<3;++k) {
                if (sol(i,j,k)) return true;
            }
        }
    }
}


int main(){
    int mod=1000000007;
    for (;;) {
        scanf("%d %d %d %d",&d[0],&d[1],&d[2],&d[3]);
        if (d[0]==d[1] && d[1]==d[2] && d[2]==d[3] && d[0]==0) break;
        sort(d,d+4);
        do {
            if (jg()) break;
        } while (next_permutation(d,d+4));
        if (f==0) printf("0\n");
    }
    return 0;
}

カッコの位置は実質上は3種類しか無いらしい？ ((a op b) op c ) op d と (a op b) op (c op d) と (a op (b op c)) op d これしかないという証明は知りません。 const char *op="+-*"; の記法やnext_permutationの使い方を出来るように。

0042: A Thief

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

kz gcd(kz a,kz b) { if(b==0) return a; else gcd(b,a%b); }

int main(){
    int mod=1000000007;
    int w,n,a[1000],b[1000],Case=1;
    char s[260];
    for (;;) {
        scanf("%d",&w);
        if (w==0) break;
        int dp[w+1]={0};
        int ans[2]={0,0};
        scanf("%d",&n);
        for (int i=0;i<n;++i) {
            scanf("%d,%d",&a[i],&b[i]);
        }
        for (int i=0;i<n;++i) {
            for (int j=w-b[i];j>0;--j) {
                if (dp[j]!=0) {
                    dp[j+b[i]]=max(dp[j+b[i]],dp[j]+a[i]);
                }
            }
            dp[b[i]]=max(dp[b[i]],a[i]);
        }
        for (int i=0;i<w+1;++i) {
            if (ans[0]<dp[i]) {
                ans[0]=dp[i];
                ans[1]=i;
            }
        }
        printf("Case %d:\n%d\n%d\n",Case,ans[0],ans[1]);
        Case++;
    }
    return 0;
}

dpは1元配列で対応できる。配列の長さを耐えられる重さW+1にしておけば、dp配列のi番目に重さiでの最大の価値をいれて管理する。

0043: Puzzle

麻雀の判定？？残件。

0044: Prime Number II

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

kz gcd(kz a,kz b) { if(b==0) return a; else gcd(b,a%b); }

bool pr(int n) {
    int i=2;
    while (i*i<=n) {
        if (n%i==0) return false;
            i++;
    }
    return true;
}


int main(){
    int mod=1000000007;
    int n;
    while (scanf("%d",&n)!=EOF) {
        int ans[2]={0,0};
        for (int i=n-1;n>0;--i) {
            if (pr(i)) {
                ans[0]=i;
                break;
            }
        }
        for (int i=n+1;i<100000;++i) {
            if (pr(i)) {
                ans[1]=i;
                break;
            }
        }
        printf("%d %d\n",ans[0],ans[1]);
    }
    return 0;
}

素数判定するものを書いておいてn-1から減算し続けて、n+1から加算し続けて素数を探せば大丈夫そう。

0045: Sum and Average

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

kz gcd(kz a,kz b) { if(b==0) return a; else gcd(b,a%b); }

int main(){
    int mod=1000000007;
    int x,y,tmp=0;
    int ans[2]={0,0};
    while (scanf("%d,%d",&x,&y)!=EOF) {
        tmp++;
        ans[0]+=x*y;
        ans[1]+=y;
    }
    ans[1]=ans[1]*10/tmp;
    if (ans[1]%10>4) {
        ans[1]=ans[1]/10+1;
    } else {
        ans[1]/=10;
    }

    printf("%d\n%d\n",ans[0],ans[1]);
    return 0;
}

合計金額は単価 * 数量を加算し続けて、数量の平均は数量の合計と行数で計算をすれば大丈夫そう。

0046: Differential

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

kz gcd(kz a,kz b) { if(b==0) return a; else gcd(b,a%b); }

int main(){
    vector<double> n(1);
    int tmp=0;
    double s;
    while (scanf("%lf",&s)!=EOF){
        n.push_back(s);
        tmp++;
    }
    sort(n.begin(),n.end());
    printf("%lf\n",n[tmp]-n[1]);
    return 0;
}

件数がわからなかったのをvectorにpush_back()で追加してsort()した。なぜか、0がvectorの中に入ってくるので末尾のtmp番目と0番目が使えず1番目との差を解にした。

0047: Cup Game

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;


int main(){
    int tmp[3]={1,0,0};
    char x,y;
    while (scanf("%c,%c",&x,&y)!=EOF){
        int a=-1,b=-1,c=-1;
        if (x=='A' || y=='A') a=0;
        if (x=='B' || y=='B') b=1;
        if (x=='C' || y=='C') c=2;
        if (a==0 && b==1) swap(tmp[0],tmp[1]);
        if (a==0 && c==2) swap(tmp[0],tmp[2]);
        if (b==1 && c==2) swap(tmp[1],tmp[2]);
    }
    if (tmp[0]==1) printf("A\n");
    if (tmp[1]==1) printf("B\n");
    if (tmp[2]==1) printf("C\n");
    return 0;
}

移動をシミュレートする。

0048: Class

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    double s;
    while (scanf("%lf",&s)!=EOF){
        if (s<=48.0) {
            printf("light fly\n");
        } else if (s<=51.0) {
            printf("fly\n");
        } else if (s<=54.0) {
            printf("bantam\n");
        } else if (s<=57.0) {
            printf("feather\n");
        } else if (s<=60.0) {
            printf("light\n");
        } else if (s<=64.0) {
            printf("light welter\n");
        } else if (s<=69.0) {
            printf("welter\n");
        } else if (s<=75.0) {
            printf("light middle\n");
        } else if (s<=81.0) {
            printf("middle\n");
        } else if (s<=91.0) {
            printf("light heavy\n");
        } else {
            printf("heavy\n");
        }
    }
    return 0;
}

分類する境界値に気をつける。

0049: Blood Groups

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    int n;
    char s[2];
    int ans[4]={0};
    while (scanf("%d,%s",&n,s)!=EOF){
        if(!strcmp(s,"A")) {
            ans[0]++;
        } else if(!strcmp(s,"B")) {
            ans[1]++;
        } else if(!strcmp(s,"AB")) {
            ans[2]++;
        } else {
            ans[3]++;
        }
    }
    for (int i=0;i<4;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

char文字列の比較にstrcmpを使った。

0050: Apple and Peach

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    string s;
    getline(cin, s);
    for (int i=0;i<s.size()-4;++i) {
        string t=s.substr(i,5);
        if(t=="apple") s.replace(s.begin()+i,s.begin()+i+5,"peach");
        if(t=="peach") s.replace(s.begin()+i,s.begin()+i+5,"apple");
    }
    cout<<s<<endl;
    return 0;
}

string文字列をgetlineで半角スペースも込みで一気に読み込めるらしい。apple, peachを探すのは先頭0文字目から末尾5文字目まで。そのとき見てる文字から5文字目までの範囲でapple, peachがあったらreplaceで置換する。

0051: Differential II

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    int mod=1000000007;
    int n,s;
    scanf("%d",&n);
    for (int i=0;i<n;++i) {
        scanf("%d",&s);
        int w1[10]={0};
        int w2[10]={0};
        for (int j=0;j<8;++j) {
            w1[s%10]+=1;
            w2[s%10]+=1;
            s/=10;
        }
        int x=0,y=0;
        int tmp1=10000000;
        for (int a=0;a<8;++a) {
            for (int b=9;b>=0;--b) {
                if (w1[b]>0) {
                    x+=(b*tmp1);
                    tmp1/=10;
                    w1[b]-=1;
                    break;
                }
            }
        }
        int tmp2=10000000;
        for (int a=0;a<8;++a) {
            for (int b=0;b<10;++b) {
                if (w2[b]>0) {
                    y+=(b*tmp2);
                    tmp2/=10;
                    w2[b]-=1;
                    break;
                }
            }
        }
        printf("%d\n",x-y);
    }
    return 0;
}

大きい数を作るなら桁の大きい方に9,8,7...から優先して使う。小さい数を作るなら桁の大きい方に0,1,2...から優先して使う。作った数の差が解になる。

0052: Factorial II

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    //int mod=1000000007;
    int mod=1003199;
    int n;
    for (;;) {
        scanf("%d",&n);
        if (n==0) break;
        int ans=0;
        while (n) {
            n/=5;
            ans+=n;
        }
        printf("%d\n",ans);
    }
    return 0;
}

色々計算してうまくいかなかったので他の人の解を覗いたらn/=5して、ans+=nしてる人が殆どだった。なぜこれで解になるのかは不明。

0053: Sum of Prime Numbers

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

bool pr(int n) {
    int i=2;
    while (i*i<=n) {
        if (n%i==0) return false;
        i++;
    }
    return true;
}

int main(){
    int mod=1000000007;
    bool b[111111]={0};
    for (int i=2;i<111111;++i) {
        b[i]=pr(i);
    }
    int n;
    for (;;) {
        scanf("%d",&n);
        if (n==0) break;
        int ans=0,cnt=0;
        for (int i=2;cnt<n;++i) {
            if (b[i]) {
                ans+=i;
                cnt++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

先に素数の配列を用意しておけばそれらを加算すれば解になる。

0054: Sum of Nth decimal places

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    int mod=1000000007;
    int m=70099;
    int a,b,n;
    while (scanf("%d %d %d",&a,&b,&n)!=EOF) {
        int ans=0;
        while (n>0) {
            a=a%b*10;
            ans+=a/b;
            n-=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

doubleは信用できないし、小数と整数を混ぜては計算しにくいので * 10して整数で見られるようにする。

0055: Sequence

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    int mod=1000000007;
    double tmp=7.814814814814;
    double n;
    while (scanf("%lf",&n)!=EOF) {
        printf("%.10lf\n",n*tmp);
    }
    return 0;
}

サンプルを見るとこれしか解がない気がするのだが。。きちんと計算するのは持ち越しで。

0056: Goldbach's Conjecture

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

bool pr(int n) {
    int i=2;
    while (i*i<=n) {
        if (n%i==0) return false;
        i++;
    }
    return true;
}


int main(){
    int mod=1000000007;
    bool b[50010]={0};
    int n,ans;
    for (int i=2;i<50010;++i) {
        b[i]=pr(i);
    }
    for (;;) {
        scanf("%d",&n);
        if (n==0) break;
        ans=0;
        for (int i=2;i<(n+1)/2+1;++i) {
            if ((n-i)<i) break;
            if (b[i] && b[n-i]) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

素数を求めておけばペアで和がnになる素数があるか調べられる。

0057: The Number of Area

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

int main(){
    int mod=1000000007;
    int n;
    while (scanf("%d",&n)!=EOF) {
        printf("%d\n",n*(n+1)/2+1);
    }
    return 0;
}

nまでの総和+1が解になるらしい。証明は不明。

0058: Orthogonal

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

bool sol(double xa,double ya,double xb,double yb,double xc,double yc,double xd,double yd) {
    if (abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1e-10) return true;
    return false;
}

int main(){
    int mod=1000000007;
    int n;
    double a,b,c,d,e,f,g,h;
    while (scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h)!=EOF) {
        if (sol(a,b,c,d,e,f,g,h)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

直交を判定する。

0059: Intersection of Rectangles

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

kz gcd(kz a,kz b) { if(b==0) return a; else gcd(b,a%b); }

int main(){
    int mod=1000000007;
    int n;
    double a,b,c,d,e,f,g,h;
    while (scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h)!=EOF) {
        if (g<a || c<e || h<b || d<f) {
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }
    return 0;
}

xb2がxa1より小さければその差分だけ左右に離れるので重なることはない。yb2がya1より小さければその差分だけ上下に離れるので重なることはない。

♥ﾟ:;恋の因数分解;:ﾟ♥

fuse of love

0040: Affine Cipher

0041: Expression

0042: A Thief

0043: Puzzle

0044: Prime Number II

0045: Sum and Average

0046: Differential

0047: Cup Game

0048: Class

0049: Blood Groups

0050: Apple and Peach

0051: Differential II

0052: Factorial II

0053: Sum of Prime Numbers

0054: Sum of Nth decimal places

0055: Sequence

0056: Goldbach's Conjecture

0057: The Number of Area

0058: Orthogonal

0059: Intersection of Rectangles