「AOJ再挑戦41～45」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦41～45」(2014/01/30 (木) 03:13:52) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問41 Expression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
4つの1～9までの数字を読み込んで、それに+ - *（）を使って10を作れという問題。
解法
Prolog言語で考えてそれを無理やりC++に翻訳して解いてみた。
要は全組み合わせを検証している。
- +と*は交換法則で少し計算量を低減。
- 大学行ったことないのでこの我流の方法がよいのかはよくわからないまあ合格できてるからいいかな
#include<stdio.h>
#include<string>
#include<algorithm>
#include<set>
struct S{
int num;
std::string siki;
bool spents[4];
bool calcOK(const S& s){
for(int i=0;i<4;i++){
if((s.spents[i]==true)&&(spents[i]==true))return false;
}
return true;
}
bool operator<(const S& s1)const{
for(int i=0;i<4;i++){
if(spents[i]!=s1.spents[i])return spents[i]<s1.spents[i];
}
return num<s1.num;
}
};
std::set<S> sets[5];
S unionSpents(S& s1,S& s2){
S s3;
for(int i=0;i<4;i++){
s3.spents[i]=(s1.spents[i] || s2.spents[i]);
}
return s3;
}
S add(S& s1,S& s2){
S s3=unionSpents(s1,s2);
s3.siki="(" + s1.siki + " + " + s2.siki + ")";
s3.num=s1.num+s2.num;
return s3;
}
S dell(S& s1,S& s2){
S s3=unionSpents(s1,s2);
s3.siki="(" + s1.siki + " - " + s2.siki +")";
s3.num=s1.num-s2.num;
return s3;
}
S mult(S& s1,S& s2){
S s3=unionSpents(s1,s2);
s3.siki="(" + s1.siki + " * " + s2.siki +")";
s3.num=s1.num*s2.num;
return s3;
}
void search(int nums[4],int size){
if(size==1){
for(int i=0;i<4;i++){
S s1;
s1.num=nums[i];
s1.siki=(char)(nums[i]+'0');
for(int j=0;j<4;j++){
s1.spents[j]=(i==j)?true:false;
}
sets[1].insert(s1);
}
}else if(size>1){
search(nums,size-1);
for(int i=1;i<=size;i++){
S s1,s2;
int j=size-i;
if(j<1)continue;
std::set<S>::iterator it1,it2;
for(it1=sets[i].begin();it1!=sets[i].end();it1++){
s1=(*it1);
for(it2=sets[j].begin();it2!=sets[j].end();it2++){
s2=(*it2);
if(s1.calcOK(s2)){
if(i<=j)sets[size].insert(add(s1,s2));
sets[size].insert(dell(s1,s2));
if(i<=j)sets[size].insert(mult(s1,s2));
}
}
}
}
}
}
bool isOK10(S& s1){
return (s1.num==10)&&s1.spents[0]&&s1.spents[1]&&s1.spents[2]&&s1.spents[3];
}
void calc(int ns[4]){
sets[1].clear();
sets[2].clear();
sets[3].clear();
sets[4].clear();
search(ns,4);
S s1;
for(std::set<S>::iterator it=sets[4].begin();it!=sets[4].end();it++){
s1=(*it);
if(isOK10(s1)){
printf("%s\n",s1.siki.c_str());
return ;
}
}
printf("0\n");
}
int main(){
int ns[4];
while(1){
scanf("%d %d %d %d",&ns[0],&ns[1],&ns[2],&ns[3]);
if((ns[0]|ns[1]|ns[2]|ns[3])==0)break;
calc(ns);
}
}
*問42 A Thief
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
泥棒が風呂敷にお宝を包む問題。
解法
ナップザック問題そのままです。
#include<stdio.h>
int main(){
int W,caseNo=1;
while(scanf("%d",&W)!=EOF){
if(W==0)break;
int memo[1001]={0},sum=0,n,wi,vi;
scanf("%d",&n);
while(n--){
scanf("%d,%d",&vi,&wi);
sum+=wi;
if(sum>W)sum=W;
for(int i=sum;i>=wi;i--){
if(i-wi>0&&memo[i-wi]==0)continue;
if(memo[i]<memo[i-wi]+vi)memo[i]=memo[i-wi]+vi;
}
}
int ansV=0,ansW=0;
for(int i=0;i<=W;i++){
if(ansV<memo[i]){
ansV=memo[i];
ansW=i;
}
}
printf("Case %d:\n%d\n%d\n",caseNo,ansV,ansW);
caseNo++;
}
}
*43 Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
与えられ13個の数字に一つ足して役を作れるか判定する問題。
全部の数を使い切るのですから、小さい数からためし、その数を使い切るまで２，３、３連続組を作りあとは全探索するだけです。
手前からデータを食べていくリストプロセッサー的な発想です。
データ数が多い場合上がれる役のすべてをstd::setに入れてそれと照合するという発想もありかもしれません。
#include<stdio.h>
#include<string.h>
bool search(int count[10],int p,bool isTwoCreate){
bool result=false;
if(p==10&&isTwoCreate){
return true;
}else{
if(isTwoCreate==false){
count[p]-=2;
result=result || search(count,p,true);
count[p]+=2;
}
if(count[p]>2){
count[p]-=3;
result = result || search(count,p,isTwoCreate);
count[p]+=3;
}
if(p<=7&&count[p]>0&&count[p+1]>0&&count[p+2]>0){
count[p]--;
count[p+1]--;
count[p+2]--;
result=result || search(count,p,isTwoCreate);
count[p]++;
count[p+1]++;
count[p+2]++;
}
if(count[p]==0){
result=result || search(count,p+1,isTwoCreate);
}
}
return result;
}
int main(){
char text[15];
while(scanf("%s",text)!=EOF){
int count[10]={0};
for(int i=0;text[i]!='\0';i++)count[text[i]-'0']++;
bool isFirst=true;
bool isOK=true;
for(int i=1;i<=9;i++)if(count[i]>=5)isOK=false;
for(int i=1;isOK && i<=9;i++){
if(count[i]<4){
count[i]++;
if(search(count,0,false)){
isFirst?isFirst=false:printf(" ");
printf("%d",i);
}
count[i]--;
}
}
printf("%s",isFirst?"0\n":"\n");
}
}
*問44 Prime Number II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
与えられた数の上下直近にある素数二つをこたえる問題。
篩を使ってあとは上下を探すだけです。
#include<stdio.h>
#include<string.h>
const int MAX=60000;
bool isPrime[MAX];
void calc(){
memset(isPrime,true,sizeof(isPrime));
isPrime[0]=isPrime[1]=false;
for(int i=2;i*i<=MAX;i+=(1+(i&1))){
if(isPrime[i]==false)continue;
int add=i%2==0?i:i*2;
for(int j=(i%2==0?i*2:i*3);j<=MAX;j+=add){
isPrime[j]=false;
}
}
}
int main(){
calc();
int n;
while(scanf("%d",&n)!=EOF){
int p1,p2;
for(p1=n-1;isPrime[p1]==false;p1--);
for(p2=n+1;isPrime[p2]==false;p2++);
printf("%d %d\n",p1,p2);
}
}
*問45 Sum and Average
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
販売金額と販売数量の平均を出す問題
簡単なので特に工夫するところないです。
0.5足してintをとるくらいですね。
#include<stdio.h>
int main(){
double v,n,sum=0,count=0,type=0;
while(scanf("%lf,%lf",&v,&n)!=EOF){
sum+=v*n;
count+=n;
type+=1;
}
printf("%.0lf\n%d\n",sum,(int)(count/type+0.5));
}
*問41 Expression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
4つの1～9までの数字を読み込んで、それに+ - *（）を使って10を作れという問題。
解法
Prolog言語で考えてそれを無理やりC++に翻訳して解いてみた。
要は全組み合わせを検証している。
- +と*は交換法則で少し計算量を低減。
- 大学行ったことないのでこの我流の方法がよいのかはよくわからないまあ合格できてるからいいかな
#include<stdio.h>
#include<string>
#include<algorithm>
#include<set>
struct S{
int num;
std::string siki;
bool spents[4];
bool calcOK(const S& s){
for(int i=0;i<4;i++){
if((s.spents[i]==true)&&(spents[i]==true))return false;
}
return true;
}
bool operator<(const S& s1)const{
for(int i=0;i<4;i++){
if(spents[i]!=s1.spents[i])return spents[i]<s1.spents[i];
}
return num<s1.num;
}
};
std::set<S> sets[5];
S unionSpents(S& s1,S& s2){
S s3;
for(int i=0;i<4;i++){
s3.spents[i]=(s1.spents[i] || s2.spents[i]);
}
return s3;
}
S add(S& s1,S& s2){
S s3=unionSpents(s1,s2);
s3.siki="(" + s1.siki + " + " + s2.siki + ")";
s3.num=s1.num+s2.num;
return s3;
}
S dell(S& s1,S& s2){
S s3=unionSpents(s1,s2);
s3.siki="(" + s1.siki + " - " + s2.siki +")";
s3.num=s1.num-s2.num;
return s3;
}
S mult(S& s1,S& s2){
S s3=unionSpents(s1,s2);
s3.siki="(" + s1.siki + " * " + s2.siki +")";
s3.num=s1.num*s2.num;
return s3;
}
void search(int nums[4],int size){
if(size==1){
for(int i=0;i<4;i++){
S s1;
s1.num=nums[i];
s1.siki=(char)(nums[i]+'0');
for(int j=0;j<4;j++){
s1.spents[j]=(i==j)?true:false;
}
sets[1].insert(s1);
}
}else if(size>1){
search(nums,size-1);
for(int i=1;i<=size;i++){
S s1,s2;
int j=size-i;
if(j<1)continue;
std::set<S>::iterator it1,it2;
for(it1=sets[i].begin();it1!=sets[i].end();it1++){
s1=(*it1);
for(it2=sets[j].begin();it2!=sets[j].end();it2++){
s2=(*it2);
if(s1.calcOK(s2)){
if(i<=j)sets[size].insert(add(s1,s2));
sets[size].insert(dell(s1,s2));
if(i<=j)sets[size].insert(mult(s1,s2));
}
}
}
}
}
}
bool isOK10(S& s1){
return (s1.num==10)&&s1.spents[0]&&s1.spents[1]&&s1.spents[2]&&s1.spents[3];
}
void calc(int ns[4]){
sets[1].clear();
sets[2].clear();
sets[3].clear();
sets[4].clear();
search(ns,4);
S s1;
for(std::set<S>::iterator it=sets[4].begin();it!=sets[4].end();it++){
s1=(*it);
if(isOK10(s1)){
printf("%s\n",s1.siki.c_str());
return ;
}
}
printf("0\n");
}
int main(){
int ns[4];
while(1){
scanf("%d %d %d %d",&ns[0],&ns[1],&ns[2],&ns[3]);
if((ns[0]|ns[1]|ns[2]|ns[3])==0)break;
calc(ns);
}
}
*問42 A Thief
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042
泥棒が風呂敷にお宝を包む問題。
解法
ナップザック問題そのままです。
#include<stdio.h>
int main(){
int W,caseNo=1;
while(scanf("%d",&W)!=EOF){
if(W==0)break;
int memo[1001]={0},sum=0,n,wi,vi;
scanf("%d",&n);
while(n--){
scanf("%d,%d",&vi,&wi);
sum+=wi;
if(sum>W)sum=W;
for(int i=sum;i>=wi;i--){
if(i-wi>0&&memo[i-wi]==0)continue;
if(memo[i]<memo[i-wi]+vi)memo[i]=memo[i-wi]+vi;
}
}
int ansV=0,ansW=0;
for(int i=0;i<=W;i++){
if(ansV<memo[i]){
ansV=memo[i];
ansW=i;
}
}
printf("Case %d:\n%d\n%d\n",caseNo,ansV,ansW);
caseNo++;
}
}
*43 Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043
与えられ13個の数字に一つ足して役を作れるか判定する問題。
全部の数を使い切るのですから、小さい数からためし、その数を使い切るまで２，３、３連続組を作りあとは全探索するだけです。
手前からデータを食べていくリストプロセッサー的な発想です。
データ数が多い場合上がれる役のすべてをstd::setに入れてそれと照合するという発想もありかもしれません。
#include<stdio.h>
#include<string.h>
bool search(int count[10],int p,bool isTwoCreate){
bool result=false;
if(p==10&&isTwoCreate){
return true;
}else{
if(isTwoCreate==false){
count[p]-=2;
result=result || search(count,p,true);
count[p]+=2;
}
if(count[p]>2){
count[p]-=3;
result = result || search(count,p,isTwoCreate);
count[p]+=3;
}
if(p<=7&&count[p]>0&&count[p+1]>0&&count[p+2]>0){
count[p]--;
count[p+1]--;
count[p+2]--;
result=result || search(count,p,isTwoCreate);
count[p]++;
count[p+1]++;
count[p+2]++;
}
if(count[p]==0){
result=result || search(count,p+1,isTwoCreate);
}
}
return result;
}
int main(){
char text[15];
while(scanf("%s",text)!=EOF){
int count[10]={0};
for(int i=0;text[i]!='\0';i++)count[text[i]-'0']++;
bool isFirst=true;
bool isOK=true;
for(int i=1;i<=9;i++)if(count[i]>=5)isOK=false;
for(int i=1;isOK && i<=9;i++){
if(count[i]<4){
count[i]++;
if(search(count,0,false)){
isFirst?isFirst=false:printf(" ");
printf("%d",i);
}
count[i]--;
}
}
printf("%s",isFirst?"0\n":"\n");
}
}
*問44 Prime Number II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0044
与えられた数の上下直近にある素数二つをこたえる問題。
篩を使ってあとは上下を探すだけです。
#include<stdio.h>
#include<string.h>
const int MAX=60000;
bool isPrime[MAX+1];
void calc(){
memset(isPrime,true,sizeof(isPrime));
isPrime[0]=isPrime[1]=false;
for(int i=2;i*i<=MAX;i+=(1+(i&1))){
if(isPrime[i]==false)continue;
int add=i%2==0?i:i*2;
for(int j=(i%2==0?i*2:i*3);j<=MAX;j+=add){
isPrime[j]=false;
}
}
}
int main(){
calc();
int n;
while(scanf("%d",&n)!=EOF){
int p1,p2;
for(p1=n-1;isPrime[p1]==false;p1--);
for(p2=n+1;isPrime[p2]==false;p2++);
printf("%d %d\n",p1,p2);
}
}
*問45 Sum and Average
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0045
販売金額と販売数量の平均を出す問題
簡単なので特に工夫するところないです。
0.5足してintをとるくらいですね。
#include<stdio.h>
int main(){
double v,n,sum=0,count=0,type=0;
while(scanf("%lf,%lf",&v,&n)!=EOF){
sum+=v*n;
count+=n;
type+=1;
}
printf("%.0lf\n%d\n",sum,(int)(count/type+0.5));
}
