「AOJ41~50」の編集履歴(バックアップ)一覧はこちら
「AOJ41~50」(2011/08/21 (日) 18:47:03) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*41 Expression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
難しそうなのでパス。
丁寧に場合分けしたらいいのだろうか?
----
*0042 A Thief
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
典型的なナップザック問題、メモ化探索で計算。
計算量が小さいのでメモ化も適当。
メモは大きい方から足しこむことで、同じ荷物を何度も入れることを防いでいる。
もう少し賢いコードがありそうだけど?
#include<stdio.h>
void calc(int max,int i){
int memo[1001]={0},n,v,w,tMax,ansV=0,ansW=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d,%d",&v,&w);
for(int j=max;j>=w;j--){
if((j==w || memo[j-w]>0) && memo[j]<memo[j-w]+v){
memo[j]=memo[j-w]+v;
}
}
}
for(int i=0;i<=max;i++){
if(memo[i]>ansV){
ansV=memo[i];
ansW=i;
}
}
printf("Case %d:\n",i);
printf("%d\n%d\n",ansV,ansW);
}
int main(){
int w,i=1;
scanf("%d",&w);
while(w!=0){
calc(w,i);
i++;
scanf("%d",&w);
}
}
----
*0043 Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
計算量が小さいので力づくで全探索。
行列演算で解けそうだけど、どう行列に落とし込めばいいかわからなかったので探索で解いた。
もう少し賢いコードがありそう。
#include<stdio.h>
bool ans,first;
int m[10];
void saiki(int deep){
if(deep==4){
for(int i=1;i<10;i++){
if(m[i]==2){
ans=true;
break;
}
}
return ;
}
for(int i=1;i<10;i++){
if(m[i]>2){
m[i]-=3;
saiki(deep+1);
m[i]+=3;
if(ans==true) return;
}
}
for(int i=1;i<8;i++){
if(m[i]>0 && m[i+1]>0 && m[i+2]>0){
m[i]--;
m[i+1]--;
m[i+2]--;
saiki(deep+1);
m[i]++;
m[i+1]++;
m[i+2]++;
if(ans==true) return;
}
}
}
int main(){
char t[14];
while(scanf("%s",t)>0){
for(int i=1;i<10;i++)m[i]=0;
for(int i=0;i<13;i++)m[t[i]-'0']++;
first=true;
for(int i=1;i<10;i++){
ans=false;
if(m[i]<4){
m[i]++;
saiki(0);
m[i]--;
if(ans==true){
if(first==true){
printf("%d",i);
first=false;
}else{
printf(" %d",i);
}
}
}
}
if(first==true){
printf("0");
}
printf("\n");
}
}
----
*0044 Prime Number II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
素数を求めて、setに入れてupper_boundとlower_boundで求めるだけ。
もしnが50000よりずっと大きな数になったらどうするか考えものの問題。
#include<stdio.h>
#include<set>
std::set<int> s;
void setSo(){
int so[50023]={0};
s.insert(2);
for(int i=3;i<50023;i+=2){
if(so[i]!=0) continue;
s.insert(i);
for(int j=i*3;j<50023;j+=i*2){
so[j]=1;
}
}
}
int main(){
setSo();
int n;
while(scanf("%d",&n)>0){
printf("%d %d\n",*(--s.lower_bound(n)),*(s.upper_bound(n)));
}
}
----
*0045 Sum and Average
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
何も考えずに足しこむだけ。
#include<stdio.h>
int main(){
int m,t,s=0,i=0;
double c=0;
while(scanf("%d,%d",&m,&t)>0){
s+=m*t;
c+=t;
i++;
}
printf("%d\n%d\n",s,(int)(c/i+0.5));
}
----
*0046 Differential
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0046
一番大きいのと小さいのをメモして差分をとるだけ。
#include<stdio.h>
int main(){
double max,min,t;
scanf("%lf",&max);
min=max;
while(scanf("%lf",&t)!=EOF){
min=min>t?t:min;
max=max<t?t:max;
}
printf("%lf\n",max-min);
}
----
*0047 Cup Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0047
今ボールのはいってるカップが交換されたらボールの位置を交換するだけ。
3項演算子?がコード短縮のポイント。
コードの短さでは結構自信があったのだが、この問題ここに掲載のコードの半分の短さのコードで書けるらしい、、、ちょっと想像がつかない。
70byteとか意味不明すぎる。
#include <stdio.h>
int main(void)
{
char n='A',a,b;
while(scanf("%c,%c",&a,&b)!=EOF){
n=n==a?b:n==b?a:n;
}
printf("%c\n",n);
}
----
*0048 Class
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0048
簡単な問題なので愚直に実装。
if文で分岐してもよかったかも。
体重分岐の部分を?演算子を何個も連ねる解法もあり少し面白い。
#include<stdio.h>
#include<map>
#include<string>
int main(){
std::map<double,std::string> c;
std::map<double,std::string>::iterator it;
c[48.0]="fly";
c[51.0]="bantam";
c[54.0]="feather";
c[57.0]="light";
c[60.0]="light welter";
c[64.0]="welter";
c[69.0]="light middle";
c[75.0]="middle";
c[81.0]="light heavy";
double w;
while(scanf("%lf",&w)!=EOF){
if(w<=48.0){
printf("light fly\n");
}else if(w>91.0){
printf("heavy\n");
}else{
it=c.lower_bound(w);
if(c.begin()!=it) it--;
printf("%s\n",(*it).second.c_str());
}
}
}
----
*0049 Blood Groups
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0049
簡単な問題なので一番楽な方法で実装。
もう少しコード削れたかな?
#include<stdio.h>
#include<map>
#include<string>
int main(){
std::map<std::string,int> memo;
int s;
char d[3];
memo["A"]=memo["B"]=memo["AB"]=memo["O"]=0;
while(scanf("%d,%s",&s,d)!=EOF){
memo[d]++;
}
printf("%d\n%d\n%d\n%d\n",memo["A"],memo["B"],memo["AB"],memo["O"]);
}
----
*0050 Apple and Peach
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0050
文字数が同じことを利用して手抜き実装、適当です。
#include <iostream>
#include<string>
int main(){
std::string s;
std::string t;
getline(std::cin,s);
int len=s.size();
for(int i=0;i<len-4;i++){
if(s[i]=='a' || s[i]=='p'){
t=s.substr(i,5);
if(t=="apple"){
s.replace(i,5,"peach");
}else if(t=="peach"){
s.replace(i,5,"apple");
}
}
}
std::cout<<s;
}
*41 Expression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
難しそうなのでパスしました。
どう解いたらいいのかちょっと思いつきません。
----
*0042 A Thief
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
典型的なナップザック問題です。
重量制限付きナップザックに荷物を詰め込んで価値を最大化するという問題です。
解法
動的計画法で解きます。
この時大きい方から足しこむことで、同じ荷物を何度も入れることを防ぎます。
#include<stdio.h>
void calc(int max,int i){
int memo[1001]={0},n,v,w,tMax,ansV=0,ansW=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d,%d",&v,&w);
for(int j=max;j>=w;j--){
if((j==w || memo[j-w]>0) && memo[j]<memo[j-w]+v){
memo[j]=memo[j-w]+v;
}
}
}
for(int i=0;i<=max;i++){
if(memo[i]>ansV){
ansV=memo[i];
ansW=i;
}
}
printf("Case %d:\n",i);
printf("%d\n%d\n",ansV,ansW);
}
int main(){
int w,i=1;
scanf("%d",&w);
while(w!=0){
calc(w,i);
i++;
scanf("%d",&w);
}
}
----
*0043 Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
数字を組み合わせて指定された役を5つ作るという問題です。
数字の書かれた13枚のカードに一枚カードを加えて、数字の連番3つか同じ数3つの役を4つ、同じ数2つの役を一つ作ります。
解法
計算量も組み合わせ数も小さいので力づくの探索で求めます。
#include<stdio.h>
bool ans,first;
int m[10];
void saiki(int deep){
if(deep==4){
for(int i=1;i<10;i++){
if(m[i]==2){
ans=true;
break;
}
}
return ;
}
for(int i=1;i<10;i++){
if(m[i]>2){
m[i]-=3;
saiki(deep+1);
m[i]+=3;
if(ans==true) return;
}
}
for(int i=1;i<8;i++){
if(m[i]>0 && m[i+1]>0 && m[i+2]>0){
m[i]--;
m[i+1]--;
m[i+2]--;
saiki(deep+1);
m[i]++;
m[i+1]++;
m[i+2]++;
if(ans==true) return;
}
}
}
int main(){
char t[14];
while(scanf("%s",t)>0){
for(int i=1;i<10;i++)m[i]=0;
for(int i=0;i<13;i++)m[t[i]-'0']++;
first=true;
for(int i=1;i<10;i++){
ans=false;
if(m[i]<4){
m[i]++;
saiki(0);
m[i]--;
if(ans==true){
if(first==true){
printf("%d",i);
first=false;
}else{
printf(" %d",i);
}
}
}
}
if(first==true){
printf("0");
}
printf("\n");
}
}
----
*0044 Prime Number II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
ある数nに一番近い二つの素数を求めよという問題。
解法
素数の表を求め表をsetに入れて、setからupper_boundとlower_boundするだけで答えがもとまります。
#include<stdio.h>
#include<set>
std::set<int> s;
void setSo(){
int so[50023]={0};
s.insert(2);
for(int i=3;i<50023;i+=2){
if(so[i]!=0) continue;
s.insert(i);
for(int j=i*3;j<50023;j+=i*2){
so[j]=1;
}
}
}
int main(){
setSo();
int n;
while(scanf("%d",&n)>0){
printf("%d %d\n",*(--s.lower_bound(n)),*(s.upper_bound(n)));
}
}
----
*0045 Sum and Average
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
販売単価と販売数量の合計を求めるだけの問題です。
簡単なので肩慣らしにどうぞ。
#include<stdio.h>
int main(){
int m,t,s=0,i=0;
double c=0;
while(scanf("%d,%d",&m,&t)>0){
s+=m*t;
c+=t;
i++;
}
printf("%d\n%d\n",s,(int)(c/i+0.5));
}
----
*0046 Differential
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0046
数字列が与えられるので列の中で一番大きな数字と小さな数字の差を出力してください。
解法
一つずつ読みながら一番大きいのと小さいのをメモして差分をとるだけです。
#include<stdio.h>
int main(){
double max,min,t;
scanf("%lf",&max);
min=max;
while(scanf("%lf",&t)!=EOF){
min=min>t?t:min;
max=max<t?t:max;
}
printf("%lf\n",max-min);
}
----
*0047 Cup Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0047
カップゲームの入れ替えをシミュレートして最後にボールのはいってるカップの位置を出力する問題。
解法
今ボールのはいってるカップが交換されたらボールの位置nを交換するだけです。
3項演算子?がコード短縮のポイントです。
#include <stdio.h>
int main(void)
{
char n='A',a,b;
while(scanf("%c,%c",&a,&b)!=EOF){
n=n==a?b:n==b?a:n;
}
printf("%c\n",n);
}
----
*0048 Class
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0048
体重データからボクサーの階級を出力する問題です。
解法
簡単な問題なので愚直に実装します。
#include<stdio.h>
#include<map>
#include<string>
int main(){
std::map<double,std::string> c;
std::map<double,std::string>::iterator it;
c[48.0]="fly";
c[51.0]="bantam";
c[54.0]="feather";
c[57.0]="light";
c[60.0]="light welter";
c[64.0]="welter";
c[69.0]="light middle";
c[75.0]="middle";
c[81.0]="light heavy";
double w;
while(scanf("%lf",&w)!=EOF){
if(w<=48.0){
printf("light fly\n");
}else if(w>91.0){
printf("heavy\n");
}else{
it=c.lower_bound(w);
if(c.begin()!=it) it--;
printf("%s\n",(*it).second.c_str());
}
}
}
----
*0049 Blood Groups
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0049
生徒の血液型のデータが与えられる。
どの血液型が何人いるか出力せよという問題。
解法
簡単なのでそのまま実装。
#include<stdio.h>
#include<map>
#include<string>
int main(){
std::map<std::string,int> memo;
int s;
char d[3];
memo["A"]=memo["B"]=memo["AB"]=memo["O"]=0;
while(scanf("%d,%s",&s,d)!=EOF){
memo[d]++;
}
printf("%d\n%d\n%d\n%d\n",memo["A"],memo["B"],memo["AB"],memo["O"]);
}
----
*0050 Apple and Peach
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0050
文字列の中のAppleをPeachにPeachをAppleに置き換える問題。
解法
文字列型の基本機能を使いこなすだけです。
#include <iostream>
#include<string>
int main(){
std::string s;
std::string t;
getline(std::cin,s);
int len=s.size();
for(int i=0;i<len-4;i++){
if(s[i]=='a' || s[i]=='p'){
t=s.substr(i,5);
if(t=="apple"){
s.replace(i,5,"peach");
}else if(t=="peach"){
s.replace(i,5,"apple");
}
}
}
std::cout<<s;
}