問25 Hit and Blow
解法
同じ数字がないので4*4検証して同じ数ならHitかBlowしかありません。
同じ場所でないならBlowです、同じ場所ならHitです。
同じ数字が許容されるとこの問題判定が少し難しくなりますね。
#include<stdio.h>
int main(){
int as[4],bs[4];
while(scanf("%d %d %d %d",&as[0],&as[1],&as[2],&as[3])!=EOF){
scanf("%d %d %d %d",&bs[0],&bs[1],&bs[2],&bs[3]);
int hit=0;
int blow=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(i!=j){
blow+=(as[i]==bs[j]);
}else{
hit+=(as[i]==bs[j]);
}
}
}
printf("%d %d\n",hit,blow);
}
}
問26 Dropping Ink
解法
そのままシミュレートします。
ペーパー上下左右をそれぞれ２マスを大きくして実際に垂らしたポイントをx+2,y+2とし、２～11マス目までを集計する事で外側判定処理を省いています。
#include<stdio.h>
#include<string.h>
int paper[15][15];
const int slide=2;
void small(int x,int y){
paper[x+1][y]++;
paper[x][y+1]++;
paper[x-1][y]++;
paper[x][y-1]++;
paper[x][y]++;
}
void middle(int x,int y){
paper[x+1][y+1]++;
paper[x+1][y-1]++;
paper[x-1][y+1]++;
paper[x-1][y-1]++;
small(x,y);
}
void big(int x,int y){
paper[x+2][y]++;
paper[x][y+2]++;
paper[x-2][y]++;
paper[x][y-2]++;
middle(x,y);
}
int main(){
memset(paper,0,sizeof(paper));
int x,y,s;
while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
x+=slide;
y+=slide;
if(s==3)big(x,y);
if(s==2)middle(x,y);
if(s==1)small(x,y);
}
int ansA=0,ansB=0;
for(int x=0;x<10;x++){
int x1=x+slide;
for(int y=0;y<10;y++){
int y1=y+slide;
if(paper[x1][y1]>ansB)ansB=paper[x1][y1];
if(paper[x1][y1]==0)ansA++;
}
}
printf("%d\n%d\n",ansA,ansB);
}
問27 What day is today?
解法
ツェラーの公式で一発です。
#include<stdio.h>
char weeks[7][10]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
int getWeekday(int nYear, int nMonth, int nDay)
{
//ツェラーの公式という有名な曜日判定プログラム
int nWeekday, nTmp;
if (nMonth == 1 || nMonth == 2) {
nYear--;
nMonth += 12;
}
nTmp = nYear/100;
nWeekday = (nYear + (nYear >> 2) - nTmp + (nTmp >> 2) + (13*nMonth + 8)/5 + nDay) % 7;
return nWeekday;
}
int main(){
while(1){
int m,d;
scanf("%d %d",&m,&d);
if(m==0&&d==0)break;
printf("%s\n",weeks[getWeekday(2004,m,d)]);
}
}
問28 Mode Value
1～100までの数の書かれたデータをカウントして、最頻値を出力する問題。
解法
範囲が決まっているので配列でカウントして最頻値の出現回数を更新。
最頻値と同じ数だけ出た数を全て出力すれば答え。
#include<stdio.h>
int main(){
int memo[101]={0};
int n,max=0;
while(scanf("%d",&n)!=EOF){
memo[n]++;
if(max<memo[n])max=memo[n];
}
for(int i=1;i<=100;i++){
if(max==memo[i])printf("%d\n",i);
}
}
問29 English Sentence
解法
出現範囲があやふやなのでstd::mapで集計しますが原理は問28と同じです。
カウントしてカウントが今までの記録を更新したらその単語と回数で記録を更新。
一番長い単語が出たら更新。
それだけ。
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
int main(){
std::map<std::string,int> memo;
std::string word,ansLongStr,ansCountStr;
int maxCount=0,maxLen=0;
while(std::cin.eof()==false){
std::cin>>word;
if(memo.find(word)==memo.end())memo[word]=0;
memo[word]++;
if(word.size()>maxLen){
maxLen=word.size();
ansLongStr=word;
}
if(memo[word]>maxCount){
maxCount=memo[word];
ansCountStr=word;
}
}
std::cout<<ansCountStr<<" "<<ansLongStr<<"\n";
}
問30 Sum of Integers
解法
動的計画法で解けば計算量は大雑把にって10*(55*50+45*10)=30000回程度です。
n sの組のうちｓが100までという構成できない値を聞いてくるのがこの問題のひっかけなのでそこだけ注意。
あとは何も考えない動的計画法で解けます。
i個めまで数字を使ったとき、i+1個めはi個めまでに使った数より大きなものをとるという条件で計算するだけです。
#include<stdio.h>
#include<string.h>
int main(){
int memo[11][10][101];//memo[数字の個数][数字の最高値][数字の合計値]
int ans[11][101];
memset(memo,0,sizeof(memo));
memset(ans,0,sizeof(ans));
memo[0][0][0]=1;
for(int i=1;i<=10;i++){
for(int j=0;j<=9;j++){
int t=j;
if(i==1&&j==0)t=-1;
for(int k=t+1;k<=9;k++){
for(int sum=45-k;sum>=0;sum--){
memo[i][k][sum+k]+=memo[i-1][j][sum];
}
}
}
for(int sum=0;sum<=45;sum++){
for(int j=0;j<=9;j++){
ans[i][sum]+=memo[i][j][sum];
}
}
}
int n,s;
while(scanf("%d %d",&n,&s)!=EOF){
if(n==0&&s==0)break;
printf("%d\n",ans[n][s]);
}
}
最終更新：2014年01月11日 11:25
