0061 Rank Checker
チームデータをベクターに確保し得点順にソートします。
これを上位から読み上位チームの番号と順位の組をMapに保存します。
も少し賢い方法があるような気もしますが標準的に実装してみました。
これくらいならEXCELで計算した方が早そうです。
#include<stdio.h>
#include<vector>
#include<map>
#include <algorithm>
struct team{
int no,p;
bool operator<(const team t)const {
return p>t.p;
}
};
int main(){
std::vector<team> teams;
team t;
do{
scanf("%d,%d",&t.no,&t.p);
teams.push_back(t);
}while(t.no!=0 && t.p!=0);
std::sort(teams.begin(),teams.end());
std::vector<team>::iterator it=teams.begin();
int rank=1,p=(*it).p;
std::map<int,int> memo;
while(it!=teams.end()){
if(p==(*it).p){
memo[(*it).no]=rank;
}else{
p=(*it).p;
rank++;
memo[(*it).no]=rank;
}
it++;
}
while(scanf("%d",&p)!=EOF){
printf("%d\n",memo[p]);
}
}
0062 What is the Bottommost?
#include<stdio.h>
int main(){
char t[11];
int sum,com[]={1,10,45,120,210};
while(scanf("%s",t)!=EOF){
sum=0;
for(int i=0;i<5;i++) sum+=com[i]*(t[i]+t[9-i]-96);
printf("%d\n",sum%10);
}
}
0063 Palindrome
#include<stdio.h>
#include<string.h>
int main(){
char text[101];
bool ok;
int len,ans=0;
while(scanf("%s",text)!=EOF){
ok=true;
len=strlen(text);
for(int i=0;i<len/2;i++){
if(text[i]!=text[len-i-1]){
ok=false;
break;
}
}
ans+=ok?1:0;
}
printf("%d\n",ans);
}
0064 Secret Number
#include<stdio.h>
#include<string.h>
int main(){
char t[81];
int len,mod,sum=0,ans=0;
while(scanf("%s",t)!=EOF){
len=strlen(t);
mod=0;
sum=0;
for(int i=0;i<len;i++){
if('0'<=t[i] && t[i]<='9'){
sum*=10;
sum+=t[i]-'0';
}else{
ans+=sum;
sum=0;
}
}
ans+=sum;
}
printf("%d\n",ans);
}
0065 Trading
解法
今月の取引を記録し、先月の取引と照合して共通集合をとりカウントするだけです。
簡単なのでコードを見た方が早いでしょう。
#include<stdio.h>
#include<map>
int main(){
int no,day;
char re[3];
std::map<int,int> now,old;
while(1){
scanf("%d,%d",&no,&day);
if(now.find(no)==now.end()){
now[no]=1;
}else{
now[no]++;
}
scanf("%[\n]",re);
if(re[1]!='\0') break;
}
while(scanf("%d,%d",&no,&day)!=EOF){
if(old.find(no)==old.end()){
old[no]=1;
}else{
old[no]++;
}
}
std::map<int,int>::iterator it=old.begin();
while(it!=old.end()){
if(now.find((*it).first)!=now.end()){
printf("%d %d\n",(*it).first,(*it).second+now[(*it).first]);
}
it++;
}
}
0066 Tic Tac Toe
解法
この問題はマトリックス*cを使って縦横斜めのチェックパターンを配置します。
チェックパターンを一つずつ読み込み、チェックする3マスの文字コードの|をとりuとします。
もし3マスともoかxならuは18でマスクをとった時2か16となります。
もし3マスがoxsが混在すれば18でマスクをとった時18となりこれによって勝敗のチェックができます。
#include<stdio.h>
int main(){
char i,d,s,u,m[10],*c="3331114201203602";
while(scanf("%s",m)>0){
d='d';
for(i=0;i<8;i++){
s=c[i+8]%8;
u=m[s]|m[s+c[i]%8]|m[s+2*c[i]%8];
d=(u&18)<17?u:d;
}
printf("%c\n",d);
}
}
0067 The Number of Island
昔のRPG風の升目に島を表す1と海を表す0が与えられています。
マップの中にある島の数を数えて出力せよという問題です。
解法
ただ単に深さ優先探索をします。
升目を上から調べて、島があればその島のなかでいけるところを全て調べ海に戻します。
これを続けて島の数を数えれば答えが出ます。
#include<stdio.h>
int dxs[]={1,0,-1,0},dys[]={0,1,0,-1};
char map[12][13];
void saiki(int x,int y){
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(nx<0 || 11<nx || ny<0 || 11<ny ||map[ny][nx]=='0') continue;
map[ny][nx]='0';
saiki(nx,ny);
}
}
bool setMap(){
for(int i=0;i<12;i++){
if(scanf(" %12s",map[i])==EOF) return false;
}
int x,y,i,count=0;
for(i=0;i<144;i++){
x=i%12;
y=i/12;
if(map[y][x]=='1'){
map[y][x]='0';
count++;
saiki(x,y);
}
}
printf("%d\n",count);
return true;
}
int main(){
char s1;
do{
if(setMap()==false) break;
if(scanf("%c",&s1)==EOF) break;
}while(scanf("%c",&s1)!=EOF);
}
0068 Enclose Pins with a Rubber Band
#include<stdio.h>
void setData(int n){
double xs[101],ys[101],vx1,vy1,vx2,vy2;
bool hits[101];
for(int i=0;i<n;i++){
scanf("%lf,%lf",&xs[i],&ys[i]);
hits[i]=false;
}
if(n<5){
printf("%d\n",n-3);
return ;
}
double d;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(j==i || (hits[i]&&hits[j])) continue;
vx1=xs[j]-xs[i];
vy1=ys[j]-ys[i];
bool first=true;
bool ok=true;
for(int k=0;k<n;k++){
if(i==k || j==k) continue;
vx2=xs[k]-xs[i];
vy2=ys[k]-ys[i];
if(first==true){
d=vx1*vy2-vx2*vy1;
first=false;
}else{
if(d*(vx1*vy2-vx2*vy1)<=0){
ok=false;
break;
}
}
}
if(ok==true){
hits[i]=hits[j]=true;
}
}
}
int ans=0;
for(int i=0;i<n;i++){
ans+=hits[i]?1:0;
}
printf("%d\n",n-ans);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setData(n);
scanf("%d",&n);
}
}
0069 Drawing Lots II
解法
書いてある通りに実装し、上から順に線を引いた場合を試していきます。
線を引いてはゴールにたどり着けるかsimulation関数で調べます、できないなら線を戻して次の線を引きます。
線を引けるかのチェックを忘れないでください。
#include<stdio.h>
char map[31][13];
bool simulation(int now,int goal,int d){
for(int i=0;i<d;i++){
now+=map[i][now-1]=='1'?-1:map[i][now]=='1'?1:0;
}
return goal==now;
}
void setData(int n){
int start,goal,d;
scanf("%d %d %d",&start,&goal,&d);
for(int i=0;i<d;i++){
scanf("%s",&map[i][1]);
map[i][0]=map[i][n]='0';
}
if(simulation(start,goal,d)==true){
printf("0\n");
return;
}
for(int i=0;i<d;i++){
for(int j=1;j<n;j++){
if(map[i][j-1]=='0' && map[i][j]=='0' && map[i][j+1]=='0'){
map[i][j]='1';
if(simulation(start,goal,d)==true){
printf("%d %d\n",i+1,j);
return;
}
map[i][j]='0';
}
}
}
printf("1\n");
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setData(n);
scanf("%d",&n);
}
}
0070 Combination of Number Sequences
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
ベクトルA(1,2,3,,,,n-1,n)
と0~9までの整数を使ったn個の整数の並びでできたベクトルK(k1,k2,,,kn)を考えます。
整数sが与えられるのでAとKの内積が整数sになるKの組み合わせが何個あるか答えよという問題。
解法
賢い方法を思いつかなかったので全探索で解きました。
#include <stdio.h>
void search(int deep ,int sum);
int sums[11][331]={0};
bool spentNos[11];
int main(){
for(int i=0;i<11;i++){
spentNos[i]=false;
}
search(0,0);
int n,s;
while(scanf("%d %d",&n,&s)!=EOF){
if(n>10 || s>330){
printf("0\n");
}else{
printf("%d\n",sums[n][s]);
}
}
}
void search(int deep ,int sum){
sums[deep][sum]++;
if(deep==10){
return ;
}
for(int i=0;i<10;i++){
if(spentNos[i]==false){
spentNos[i]=true;
search(deep+1,sum+(deep+1)*i);
spentNos[i]=false;
}
}
}
最終更新:2011年08月22日 11:39