問41 Expression
解法
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
#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
全部の数を使い切るのですから、小さい数からためし、その数を使い切るまで2,3、3連続組を作りあとは全探索するだけです。
手前からデータを食べていくリストプロセッサー的な発想です。
データ数が多い場合上がれる役のすべてを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
篩を使ってあとは上下を探すだけです。
#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
簡単なので特に工夫するところないです。
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));
}
最終更新:2014年01月30日 03:13