「AOJ再挑戦106～110」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦106～110」(2014/02/07 (金) 16:57:00) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問106 Discounts of Buckwheat
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106
そばを安く買う問題。
解法
200グラム ３８０円
１０００グラム１５２０円
３００グラム ５５０円
１２００グラム １８７０円
５００グラム ８５０円
１５００グラム ２２４４円
の商品があるのだと考えて動的計画法を適用すればきれいに解けます。
#include<stdio.h>
int main(){
int gs[6]={2,10,3,12,5,15};
int vs[6]={380,1520,550,1870,850,2244};
int dp[51]={0};
for(int i=0;i<6;i++){
int g=gs[i];
int v=vs[i];
for(int j=0;j+g<=50;j++){
if(j>0&&dp[j]==0)continue;
if(dp[j+g]==0||dp[j+g]>=dp[j]+v){
dp[j+g]=dp[j]+v;
}
}
}
int g;
while(scanf("%d",&g)!=EOF){
if(g==0)break;
printf("%d\n",dp[g/100]);
}
}
*問107 Carry a Cheese
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0107
直方体のチーズが円形の穴を通るか判定する問題
解法
直方体の四角形の一番短い対角線が円の直径よりも小さいならチーズは穴を通ります。
これをきちんと証明するのは少し難しいですが直感的には明らかだと思います。
#include<stdio.h>
#include<algorithm>
int main(){
int a,b,c,n,t,r;
while(1){
scanf("%d %d %d",&a,&b,&c);
if((a|b|c)==0)break;
t=std::max(a,std::max(b,c));
t=a*a+b*b+c*c-t*t;
scanf("%d",&n);
while(n--){
scanf("%d",&r);
printf("%s\n",t<4*r*r?"OK":"NA");
}
}
}
*問108 Operation of Frequency of Appearance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0108
出現頻度操作の問題。
解法
そのまま実装。
再帰万歳（太陽万歳）。
最初の数字を除けば１２以下の数しかならばいないんだからこのへんｓｔｄ：：mapを使わない理由はあるのだけれど。
それに対応するとコードが膨らむので対処はしない。
#include<stdio.h>
#include<map>
#include<string.h>
int calcNext(int nums[12],int n,int deep,int reNums[12]){
std::map<int,int> memo;
for(int i=0;i<n;i++){
int num=nums[i];
if(memo.find(num)==memo.end())memo[num]=0;
memo[num]++;
}
int next[12];
for(int i=0;i<n;i++)next[i]=memo[nums[i]];
bool isLast=true;
for(int i=0;i<n;i++){
if(next[i]!=nums[i])isLast=false;
}
if(isLast==true){
memcpy(reNums,next,sizeof(next));
return deep;
}else{
return calcNext(next,n,deep+1,reNums);
}
}
int main(){
int n,nums[12],ans[12];
while(1){
scanf("%d",&n);
if(n==0)break;
for(int i=0;i<n;i++)scanf("%d",&nums[i]);
printf("%d\n",calcNext(nums,n,0,ans));
for(int i=0;i<n;i++){
if(i>0)printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
}
*問109 Smart Calculator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109
与えられた四則演算の式を計算する問題。
解法
再帰下降構文解析、私にとって書きやすい方法で書いてみたので参考にしてはいけない。
http://d.hatena.ne.jp/nanikaka/20110829/1314603165
この人みたいに関数の粒度を細かくするのが正しいらしい。
#include<stdio.h>
#include<ctype.h>
int ope(int& p,char *siki,int pri,int deep){
bool first=true;
int num=0;
char c=siki[p];
while(c!='='&&c!='\0'){
c=siki[p];
if(c=='('){
p++;
num=ope(p,siki,0,deep+1);
p++;
}
if(c==')'){
return num;
}
if(c=='-'&&first==true){
num=0;
while(isdigit(siki[p+1])){
num=num*10+siki[p+1]-'0';
p++;
}
num=-num;
p++;
}
if(c=='+'){
if(1<=pri){
return num;
}else{
p++;
num+=ope(p,siki,1,deep+1);
}
}
if(c=='-'&&first==false){
if(1<=pri){
return num;
}else{
p++;
num-=ope(p,siki,1,deep+1);
}
}
if(c=='*'){
if(2<=pri){
return num;
}else{
p++;
num*=ope(p,siki,2,deep+1);
}
}
if(c=='/'){
if(2<=pri){
return num;
}else{
p++;
num/=ope(p,siki,2,deep+1);
}
}
if(isdigit(c)){
num=c-'0';
while(isdigit(siki[p+1])){
num=num*10+siki[p+1]-'0';
p++;
}
p++;
}
first=false;
}
return num;
}
int main(){
int n;
char siki[101];
scanf("%d",&n);
while(n--){
scanf("%s",siki);
int p=0;
printf("%d\n",ope(p,siki,0,0));
}
}
*問106 Discounts of Buckwheat
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106
そばを安く買う問題。
解法
200グラム ３８０円
１０００グラム１５２０円
３００グラム ５５０円
１２００グラム １８７０円
５００グラム ８５０円
１５００グラム ２２４４円
の商品があるのだと考えて動的計画法を適用すればきれいに解けます。
#include<stdio.h>
int main(){
int gs[6]={2,10,3,12,5,15};
int vs[6]={380,1520,550,1870,850,2244};
int dp[51]={0};
for(int i=0;i<6;i++){
int g=gs[i];
int v=vs[i];
for(int j=0;j+g<=50;j++){
if(j>0&&dp[j]==0)continue;
if(dp[j+g]==0||dp[j+g]>=dp[j]+v){
dp[j+g]=dp[j]+v;
}
}
}
int g;
while(scanf("%d",&g)!=EOF){
if(g==0)break;
printf("%d\n",dp[g/100]);
}
}
*問107 Carry a Cheese
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0107
直方体のチーズが円形の穴を通るか判定する問題
解法
直方体の四角形の一番短い対角線が円の直径よりも小さいならチーズは穴を通ります。
これをきちんと証明するのは少し難しいですが直感的には明らかだと思います。
#include<stdio.h>
#include<algorithm>
int main(){
int a,b,c,n,t,r;
while(1){
scanf("%d %d %d",&a,&b,&c);
if((a|b|c)==0)break;
t=std::max(a,std::max(b,c));
t=a*a+b*b+c*c-t*t;
scanf("%d",&n);
while(n--){
scanf("%d",&r);
printf("%s\n",t<4*r*r?"OK":"NA");
}
}
}
*問108 Operation of Frequency of Appearance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0108
出現頻度操作の問題。
解法
そのまま実装。
再帰万歳（太陽万歳）。
最初の数字を除けば１２以下の数しかならばいないんだからこのへんｓｔｄ：：mapを使わない理由はあるのだけれど。
それに対応するとコードが膨らむので対処はしない。
#include<stdio.h>
#include<map>
#include<string.h>
int calcNext(int nums[12],int n,int deep,int reNums[12]){
std::map<int,int> memo;
for(int i=0;i<n;i++){
int num=nums[i];
if(memo.find(num)==memo.end())memo[num]=0;
memo[num]++;
}
int next[12];
for(int i=0;i<n;i++)next[i]=memo[nums[i]];
bool isLast=true;
for(int i=0;i<n;i++){
if(next[i]!=nums[i])isLast=false;
}
if(isLast==true){
memcpy(reNums,next,sizeof(next));
return deep;
}else{
return calcNext(next,n,deep+1,reNums);
}
}
int main(){
int n,nums[12],ans[12];
while(1){
scanf("%d",&n);
if(n==0)break;
for(int i=0;i<n;i++)scanf("%d",&nums[i]);
printf("%d\n",calcNext(nums,n,0,ans));
for(int i=0;i<n;i++){
if(i>0)printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
}
*問109 Smart Calculator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109
与えられた四則演算の式を計算する問題。
解法
再帰下降構文解析、私にとって書きやすい方法で書いてみたので参考にしてはいけない。
http://d.hatena.ne.jp/nanikaka/20110829/1314603165
この人みたいに関数の粒度を細かくするのが正しいらしい。
#include<stdio.h>
#include<ctype.h>
int ope(int& p,char *siki,int pri,int deep){
bool first=true;
int num=0;
char c=siki[p];
while(c!='='&&c!='\0'){
c=siki[p];
if(c=='('){
p++;
num=ope(p,siki,0,deep+1);
p++;
}
if(c==')'){
return num;
}
if(c=='-'&&first==true){
num=0;
while(isdigit(siki[p+1])){
num=num*10+siki[p+1]-'0';
p++;
}
num=-num;
p++;
}
if(c=='+'){
if(1<=pri){
return num;
}else{
p++;
num+=ope(p,siki,1,deep+1);
}
}
if(c=='-'&&first==false){
if(1<=pri){
return num;
}else{
p++;
num-=ope(p,siki,1,deep+1);
}
}
if(c=='*'){
if(2<=pri){
return num;
}else{
p++;
num*=ope(p,siki,2,deep+1);
}
}
if(c=='/'){
if(2<=pri){
return num;
}else{
p++;
num/=ope(p,siki,2,deep+1);
}
}
if(isdigit(c)){
num=c-'0';
while(isdigit(siki[p+1])){
num=num*10+siki[p+1]-'0';
p++;
}
p++;
}
first=false;
}
return num;
}
int main(){
int n;
char siki[101];
scanf("%d",&n);
while(n--){
scanf("%s",siki);
int p=0;
printf("%d\n",ope(p,siki,0,0));
}
}
*問110 Alphametic
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0110
簡単な覆面残を試す問題
解法
数字を文字列としてみてXを一つずつ数字を代入して
小学生の足し算の要領で足していって試すだけです。
#include<stdio.h>
#include<string.h>
#include<algorithm>
bool isAddOK(char* L1,char* M1,char* R1){
int pL=strlen(L1)-1;
int pM=strlen(M1)-1;
int pR=0;
char add=0,numL,numM,T;
char tempR[255];
while(add!=0||0<=pL||0<=pM){
numL=pL<0?0:L1[pL]-'0';
numM=pM<0?0:M1[pM]-'0';
T=numL+numM+add;
tempR[pR]=T%10+'0';
add=T/10;
pR++;
pL--;
pM--;
}
tempR[pR]='\0';
std::reverse(tempR,tempR+pR);
return strcmp(R1,tempR)==0;
}
void changeX(char* nums,char* reNums,char c){
for(int i=0;i<=strlen(nums);i++){
if(nums[i]=='X')reNums[i]=c;
else reNums[i]=nums[i];
}
}
int main(){
char L[255],M[255],R[255],L1[255],M1[255],R1[255];
while(scanf("%[^+]%*c%[^=]%*c%[^\n]%*c",L,M,R)!=EOF){
bool hit=false;
for(char i='0';i<='9';i++){
if(i=='0' && L[0]=='0' && strlen(L)>1)continue;
if(i=='0' && M[0]=='0' && strlen(M)>1)continue;
if(i=='0' && R[0]=='0' && strlen(R)>1)continue;
changeX(L,L1,i);
changeX(M,M1,i);
changeX(R,R1,i);
if(isAddOK(L1,M1,R1)){
printf("%c\n",i);
hit=true;
}
}
if(hit==false)printf("NA\n");
}
}
