0131 Doctor's Strange Particles
#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
#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
#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
#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
解法
時計の短軸が長軸の位置に影響を受けるということに注意すれば簡単な問題。
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
#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
解法
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
解法
丁寧にコードを書きます。
各チームの中での上位を二人ずつ。
各チームの中での3位と4位を取得しMapでソートします。
#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
解法
蛇の種類は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
#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);
}
最終更新:2011年08月24日 18:44