「AOJ131～140」の編集履歴（バックアップ）一覧に戻る
AOJ131～140 - (2011/08/24 (水) 18:44:55) のソース
----
*0131 Doctor's Strange Particles
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0131
ライツアウトと同じルールで盤面が与えられるので、全ての光を消す手順を表示せよという問題。
解法
ライツアウトは最上段の組み合わせを試したら後の段は自動的に決まるので最上段だけ全パタンを試します。
最下段に到達した時光ってるマスが残ってなければそれが正解です。
#include<stdio.h>
int map[10][10];
int ans[10][10];
int dxs[]={0,1,0,-1,0};
int dys[]={0,0,1,0,-1};
bool goal;
void push(int x,int y){
int nx,ny;
for(int i=0;i<5;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(nx<0 || 9<nx || ny<0 || 9<ny)continue;
map[ny][nx]=map[ny][nx]==1?0:1;
}
ans[y][x]=ans[y][x]==1?0:1;
}
void saiki(int deep){
if(deep==100){
for(int i=0;i<10;i++){
if(map[9][i]==1){
return;
}
}
goal=true;
return ;
}
int x=deep%10;
int y=deep/10;
if(y==0){
saiki(deep+1);
if(goal) return;
push(x,y);
saiki(deep+1);
if(goal) return;
push(x,y);
}else{
if(map[y-1][x]==1){
push(x,y);
}
saiki(deep+1);
if(goal)return;
}
}
void setMap(){
for(int i=0;i<100;i++){
scanf("%d",&map[i/10][i%10]);
ans[i/10][i%10]=0;
}
goal=false;
saiki(0);
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
printf("%s%d",j==0?"":" ",ans[i][j]);
}
printf("\n");
}
}
int main(){
int n;
scanf("%d",&n);
while(n--){
setMap();
}
}
----
*0132 Jigsaw Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0132
20*20マスの枡目でできたジグソーパズルを選んだピースから完成できるかどうかを問う問題。
解法
組み合わせ数が多く良い解法を思いつかない状態です。
とりあえず全探索するコードを記述中です。
#include <algorithm>
#include<stdio.h>
#include<string.h>
struct Peace{
int hs[4],ws[4],size;
char map[4][21][21];
int no;
void set(char onePeace[21][21],int h,int w){
size=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
map[0][i][j]=onePeace[i][j];
if(onePeace[i][j]=='#'){
size++;
}
}
}
ws[0]=w;
hs[0]=h;
round(1);
round(2);
round(3);
}
void round(int r){
hs[r]=ws[r-1];
ws[r]=hs[r-1];
for(int i=0;i<hs[r-1];i++){
for(int j=0;j<ws[r-1];j++){
map[r][j][ws[r]-i-1]=map[r-1][i][j];
}
}
}
bool operator<(const Peace p)const{
return size>p.size;
}
void print(int r){
printf("\n");
for(int i=0;i<hs[r];i++){
for(int j=0;j<ws[r];j++)printf("%c",map[r][i][j]);
printf("\n");
}
}
};
char board[21][21];
int allSize;
int h,w;
Peace Peaces[10];
int PeaceSheet[10];
int peaceOKs[10];
int n;
bool allOK;
void saiki(char nowMap[21][21],int deep,int peaceCount,int nowNo){
if(deep==peaceCount){
allOK=true;
return ;
}
char nextMap[21][21];
char t1,t2,nx,ny;
for(int i=nowNo;i<n;i++){
if(peaceOKs[i]==true)
{
peaceOKs[i]=false;
for(int y=0;y<h;y++)
{
for(int x=0;x<w;x++)
{
for(int r=0;r<4;r++)
{
bool inOK=true;
ny=y+Peaces[i].hs[r];
nx=x+Peaces[i].ws[r];
if(ny>h || nx>w) continue;
memcpy(nextMap,nowMap,21*21);
for(int dy=0;dy<Peaces[i].hs[r];dy++){
for(int dx=0;dx<Peaces[i].ws[r];dx++){
nx=x+dx;
ny=y+dy;
t1=board[ny][nx];
t2=Peaces[i].map[r][dy][dx];
if(t1=='#' && t2=='#'){
inOK=false;
break;
}
if(t1=='.' && t2=='#'){
nextMap[ny][nx]='#';
}
}
if(inOK==false) break;
}
if(inOK==true){
saiki(nextMap,deep+1,peaceCount,i+1);
if(allOK==true) return;
}
}
}
}
return ;
}
}
}
void check(){
for(int i=0;i<n;i++){
peaceOKs[i]=false;
}
allOK=false;
int peaceNo;
int sum=0;
int count=0;
scanf("%d",&count);
for(int i=0;i<count;i++){
scanf("%d",&peaceNo);
peaceOKs[PeaceSheet[peaceNo-1]]=true;
sum+=Peaces[PeaceSheet[peaceNo-1]].size;
}
if(allSize!=sum){
printf("NO\n");
return ;
}else{
saiki(board,0,count,0);
printf("%s\n",allOK==true?"YES":"NO");
}
}
void setData(){
allSize=0;
for(int i=0;i<h;i++){
scanf("%s",&board[i]);
for(int j=0;j<w;j++){
if(board[i][j]=='.'){
allSize++;
}
}
}
scanf("%d",&n);
int peaceH,peaceW;
char peaceData[21][21];
for(int i=0;i<n;i++){
scanf("%d %d",&peaceH,&peaceW);
for(int j=0;j<peaceH;j++){
scanf("%s",&peaceData[j]);
}
Peaces[i].set(peaceData,peaceH,peaceW);
Peaces[i].no=i;
}
std::sort(Peaces,Peaces+n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==Peaces[j].no){
PeaceSheet[i]=j;
break;
}
}
}
/*for(int i=0;i<n;i++){
Peaces[i].print(0);
Peaces[i].print(1);
Peaces[i].print(2);
Peaces[i].print(3);
}
*/
int p;
scanf("%d",&p);
for(int i=0;i<p;i++){
check();
}
}
int main(){
while(1){
scanf("%d %d",&h,&w);
if(h==0 && w==0) break;
setData();
}
}
----
*0133 Rotation of a Pattern
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0133
8*8マスの盤面を90度ずつ回した結果を表示せよという問題。
解法
回転行列の概念を使って盤面を90度ずつ回して表示するだけです。
#include<stdio.h>
#include<string.h>
void round(char a[8][9],int r){
char b[8][9];
for(int i=0;i<64;i++){
b[i%8][7-i/8]=a[i/8][i%8];
b[i/8][8]='\0';
}
memcpy(a,b,72);
printf("%d\n",r);
for(int i=0;i<8;i++){
printf("%s\n",a[i]);
}
}
int main(){
char a[8][9];
for(int i=0;i<8;i++)scanf("%s",a[i]);
round(a,90);
round(a,180);
round(a,270);
}
----
*0134 Exit Survey
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0134
ｎ人の購入金額が与えられるので平均購入金額を表示せよという問題。
解法
簡単なので特に解法もありません。
桁あふれを警戒してlong long intを使うくらいです。
#include <iostream>
int main(){
long long int sum=0,m,n;
std::cin>>n;
for(int i=0;i<n;i++){
std::cin>>m;
sum+=m;
}
std::cout<<sum/n<<"\n";
}
----
*0135 Clock Short Hand and Long Hand
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0135
時計の短軸と長軸のなす角を判断して、角度にあった判断結果を表示せよという問題。
解法
時計の短軸が長軸の位置に影響を受けるということに注意すれば簡単な問題。
0.5度を1単位とすると簡単に解けます。
#include<stdio.h>
#include<stdlib.h>
int main(){
int n,r1,r2,r;
scanf("%d",&n);
while(n--){
scanf("%d:%d",&r1,&r2);
r=abs(r1*60-r2*11);
r=r>360?720-r:r;
printf("%s\n",r<60?"alert":r<180?"warning":"safe");
}
}
----
*0136 Frequency Distribution of Height
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0136
伸長データからヒストグラフを求めよという問題。
解法
5ｃｍ単位であることを利用して丁寧に分類するだけです。
#include <stdio.h>
int main(void)
{
int n;
int sum[6];
scanf("%d",&n);
for(int i=0;i<6;i++){
sum[i]=0;
}
double h;
for(int i=0;i<n;i++){
scanf("%lf",&h);
if(h<165.0){
sum[0]++;
}else if(h>=185.0){
sum[5]++;
}else{
sum[((int)(h-165.0))/5+1]++;
}
}
for(int i=0;i<6;i++){
printf("%d:",i+1);
for(int j=0;j<sum[i];j++){
printf("*");
}
printf("\n");
}
return 0;
}
----
*0137 Middle-Square Method
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0137
乱数生成法である平方採中法のプログラムを書く問題。
解法
100で割って10000で余りを取ることで、平方採中法が必要とする数列の真中を得ることができます。
#include<stdio.h>
void calc(int m){
int x;
for(int i=0;i<10;i++){
m=((m*m)/100)%10000;
printf("%d\n",m);
}
}
int main(){
int n,m;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&m);
printf("Case %d:\n",i+1);
calc(m);
}
}
----
*0138 Track and Field Competition
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0138
8名参加のレースが4組が行われました。
それぞれのチームの上位2名と3位以下のなかでのトップ2名を選出するという問題。
解法
丁寧にコードを書きます。
各チームの中での上位を二人ずつ。
各チームの中での3位と4位を取得しＭａｐでソートします。
#include<stdio.h>
#include<map>
std::map<double,int> third;
std::map<double,int>::iterator it;
void calc(){
std::map<double,int> tops;
int no;
double time;
for(int i=0;i<8;i++){
scanf("%d %lf",&no,&time);
tops[time]=no;
}
it=tops.begin();
for(int i=0;i<2;i++){
printf("%d %.2lf\n",(*it).second,(*it).first);
it++;
}
third[(*it).first]=(*it).second;
it++;
third[(*it).first]=(*it).second;
}
int main(){
calc();
calc();
calc();
it=third.begin();
for(int i=0;i<2;i++){
printf("%d %.2lf\n",(*it).second,(*it).first);
it++;
}
}
----
*0139 Snakes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0139
文字列でできた蛇が与えられるので蛇の特徴からどのタイプの蛇かを答える問題。
解法
蛇の種類は2種類と少なくパタンも単純なので最も簡単な解法は正規表現を使う方法です。
私の場合は最初に全ての蛇のパタンを生成するという方法を使いました。
漸化式的に蛇を生成してsetに入れていきます。
後はsetと照合するだけです。
#include<stdio.h>
#include<string>
#include<set>
std::set<std::string> snakesA;
std::set<std::string> snakesB;
void creatSnake(){
char snake[201];
int n;
snake[0]='>';
snake[1]='\'';
for(int j=1;j<99;j++){
snake[3+j*2]='~';
snake[4+j*2]='\0';
snake[j+1]=snake[2+j*2]=snake[1+j*2]='=';
snake[j+2]='#';
snakesA.insert((std::string)snake);
}
snake[1]='^';
for(int j=1;j<99;j++){
snake[j*2]='Q';
snake[j*2+1]='=';
snake[j*2+2]=snake[j*2+3]='~';
snake[j*2+4]='\0';
snakesB.insert((std::string)snake);
}
}
int main(){
creatSnake();
int n;
char snake[201];
scanf("%d",&n);
while(n--){
scanf("%s",snake);
if(snakesA.find(snake)!=snakesA.end()){
printf("A\n");
}else if(snakesB.find(snake)!=snakesB.end()){
printf("B\n");
}else{
printf("NA\n");
}
}
}
----
*0140 Bus Line
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0140
バスラインのデータが与えられます。
入るバス停から降りるバス停までの間にどのバス停を通り過ぎるかを答えよという問題。
解法
バスラインをマトリックスに入れて右か左に降りる停留所が来るまで移動するだけです。
マトリックスはコードを短くできるのでお勧めです。
#include <stdio.h>
void search();
int bus[19]={6,7,8,9,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9};
int main(void)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
search();
}
}
void search()
{
int s,g;
scanf("%d %d",&s,&g);
if(s>5){
int p=s-6;
while(bus[p]!=g){
printf("%d ",bus[p]);
p++;
}
}else if(s<g){
for(int i=0;i<g-s;i++){
printf("%d ",s+i);
}
}else if(s>g){
for(int i=0;i<s-g;i++){
printf("%d ",s-i);
}
}
printf("%d\n",g);
}
