0111 Doctor's Memorable Codes
#include<iostream>
#include<map>
#include<string>
using namespace std;
map<char,string> e;
map<string,char> d;
std::string noToCode(int no){
std::string ans="01234";
for(int i=0;i<5;i++){
ans[4-i]=no%2+'0';
no=no/2;
}
return ans;
}
void setMap(){
for(int i=0;i<26;i++){
e['A'+i]=noToCode(i);
}
e[' '] = "11010";
e['.'] = "11011";
e[','] = "11100";
e['-'] = "11101";
e['\'']= "11110";
e['?'] = "11111";
d["101"] = ' ';
d["000000"] = '\'';
d["000011"] = ',';
d["10010001"] = '-';
d["010001"] = '.';
d["000001"] = '?';
d["100101"] = 'A';
d["10011010"] = 'B';
d["0101"] = 'C';
d["0001"] = 'D';
d["110"] = 'E';
d["01001"] = 'F';
d["10011011"] = 'G';
d["010000"] = 'H';
d["0111"] = 'I';
d["10011000"] = 'J';
d["0110"] = 'K';
d["00100"] = 'L';
d["10011001"] = 'M';
d["10011110"] = 'N';
d["00101"] = 'O';
d["111"] = 'P';
d["10011111"] = 'Q';
d["1000"] = 'R';
d["00110"] = 'S';
d["00111"] = 'T';
d["10011100"] = 'U';
d["10011101"] = 'V';
d["000010"] = 'W';
d["10010010"] = 'X';
d["10010011"] = 'Y';
d["10010000"] = 'Z';
}
int main(){
setMap();
string line,put1,ans;
int p,k,size;
while(getline(cin,line)){
put1="";
for(int i=0;i<line.size();i++){
put1.append(e[line[i]]);
}
ans="";
p=0;
size=put1.size();
while(p<size){
for(int k=3;k<9;k++){
if(p+k>size){
p=size;
break;
}
line=put1.substr(p,k);
if(d.find(line)!=d.end()){
ans+=d[line];
p=p+k-1;
break;
}
}
p++;
}
cout<<ans<<"\n";
}
}
0112 A Milk Shop
解法
long long intを使わないとintだとあふれるということにさえ注意すれば中学生でも解ける問題です。
気楽に解きましょう。
#include <algorithm>
#include <iostream>
long long int t[10001];
void calc(int n){
long long int ans=0;
for(int i=0;i<n;i++){
std::cin>>t[i];
}
std::sort(t,t+n);
for(int i=0;i<n;i++){
ans+=t[i]*(n-i-1);
}
std::cout<<ans<<"\n";
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
0113 Period
#include<stdio.h>
#include<map>
void calc(int p,int q){
std::map<int,int> memo;
int t,i=0;
memo[p]=-1;
while(1){
p*=10;
t=(p/q)%10;
p=p%q;
if(p==0){
printf("%d\n",t);
return;
}else if(memo.find(p)==memo.end()){
printf("%d",t);
memo[p]=i;
}else{
printf("%d\n",t);
break;
}
i++;
}
for(q=0;q<=i;q++){
printf("%c",q<=memo[p]?' ':'^');
}
printf("\n");
}
int main(){
int p,q;
while(scanf("%d %d",&p,&q)!=EOF){
calc(p,q);
}
}
0114 Electro-Fly
解法
x、y、zそれぞれが1に戻るまでの最小回数を求めます。
答えはx、y、zともに揃う時なので、最小回数の最小公倍数を求めます。
intだと桁あふれが起こるのでlong long intを使う点に注意すれば簡単な問題です。
#include <iostream>
#include<stdio.h>
long long int gcd(long long int a, long long int b)
{
long long int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
long long int re(long long int x,long long int m){
long long int ans=1,t=x%m;
while(t!=1){
t=(t*x)%m;
ans++;
}
return ans;
}
int main(){
long long int a1,a2,a3,m1,m2,m3,t,n1,n2,n3,c;
while(1){
std::cin>>a1>>m1>>a2>>m2>>a3>>m3;
if(a1==0) break;
n1=re(a1,m1);
n2=re(a2,m2);
n3=re(a3,m3);
c=n1*(n2/gcd(n1,n2));
c=c*(n3/gcd(n3,c));
std::cout<<c<<"\n";
}
}
0116 Rectangular Searching
#include<stdio.h>
#include<string.h>
int map[2][503];
char row[503];
void setMap(int h,int w){
char t;
int lp,rp,cp,sum,max=0,up,y;
memset(map,0,2*503*4);
for(int i=0;i<h;i++){
y=i%2;
up=(i+1)%2;
scanf("%s",row);
for(int x=0;x<w;x++){
map[y][x+1]=row[x]=='.'?map[up][x+1]+1:0;
}
for(int x=1;x<=w;x++){
if(map[y][x]!=0){
cp=map[y][x];
lp=rp=0;
while(map[y][x-lp-1]>=cp) lp++;
while(map[y][x+rp+1]>=cp) rp++;
sum=cp*(rp+lp+1);
max=max<sum ? sum:max;
}
}
}
printf("%d\n",max);
}
int main()
{
int w,h;
scanf("%d %d",&h,&w);
while(h!=0 && w!=0){
setMap(h,w);
scanf("%d %d",&h,&w);
}
}
0117 A reward for a Carpenter
解法
サイズが小さいので最も素朴なダイクストラで解くことができます。
ダイクストラ法を丁寧に実装するだけです。
#include<stdio.h>
int max=1000000000;
int g[21][21];
int Dijkstras(int start,int goal,int n){
int cost[21],flag[21]={0},p,min;
for(int i=1;i<=n;i++){
cost[i]=max;
flag[i]=0;
}
cost[start]=0;
while(1){
min=max;
p=-1;
for(int i=1;i<=n;i++){
if(cost[i]<min && flag[i]==0){
min=cost[i];
p=i;
}
}
if(p==-1) break;
flag[p]=1;
for(int j=1;j<=n;j++){
if(g[p][j]+cost[p]<cost[j]){
cost[j]=g[p][j]+cost[p];
}
}
}
return cost[goal];
}
int main(){
int n,m,a1,b1,c1,d1,x1,x2,y1,y2;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=max;
}
}
for(int i=0;i<m;i++){
scanf("%d,%d,%d,%d",&a1,&b1,&c1,&d1);
g[a1][b1]=c1;
g[b1][a1]=d1;
}
scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
int ans=y1-y2-Dijkstras(x1,x2,n)-Dijkstras(x2,x1,n);
printf("%d\n",ans);
}
0118 Property Distribution
#include<stdio.h>
char map[101][101];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
int h,w;
void saiki(int x,int y,char t){
int nx,ny;
map[y][x]='.';
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(nx<0 || w<=nx || ny<0 || h<=ny || map[ny][nx]!=t) continue;
saiki(nx,ny,t);
}
}
void calc(){
for(int i=0;i<h;i++){
scanf("%s",map[i]);
}
int count=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(map[i][j]!='.'){
count++;
saiki(j,i,map[i][j]);
}
}
}
printf("%d\n",count);
}
int main(){
while(1){
scanf("%d %d",&h,&w);
if(w==0 && h==0) break;
calc();
}
}
0119 Taro's Obsession
解法
こんな簡単な問題なら頭にグラフを思い浮かべれば10分で解けます。
グラフ化すると最後に入った人の後には誰も入ってないのでまずはその人が最後と判明します。
するとその最後に入った人をグラフから消去するとその人の直前に入った人が最後に入った人になります。
これを繰り返していけば簡単に答えがでコードサイズ491バイトとコードサイズで2位を取れました。
がこの問題をコードサイズ165byteという変態コードでクリアしてる人がいました。
どんなコードを書いたのやらもはや尊敬するレベルです。
#include<stdio.h>
#include<set>
#include<vector>
std::set<int> G[21];
std::vector<int> ans;
int spents[21]={0};
int main(){
int m,n,x,y;
scanf("%d %d",&m,&n);
for(int i=0;i<n;i++){
scanf("%d %d",&x,&y);
G[x].insert(y);
}
for(int i=0;i<m;i++){
int no=-1;
for(int j=1;j<=m;j++){
if(G[j].empty()==true&&spents[j]==0){
no=j;
spents[j]=1;
break;
}
}
ans.push_back(no);
for(int j=1;j<=m;j++)G[j].erase(no);
}
for(int i=m-1;i>=0;i--)printf("%d\n",ans[i]);
}
0120 Patisserie
n個のケーキを箱に詰められるかを答える問題。
箱に詰められるならOK、詰められないならNAと答えます。
解法
動的計画法で解きます。
左からケーキを詰めていきます。
この時今まで入れたケーキの組を1bit単位で管理し、一番右端のケーキの番号をmemo[13]に割り当てて探索します。
計算の途中入れた順番が違うだけで同じケーキの組になっている組み合わせを比べ、一番詰め込めている組み合わせのみを残すことで計算量を下げます。
#include<stdio.h>
#include<map>
#include<math.h>
void calc(int n,double wide,double size[13]){
std::map<int,double> memo[13];
std::map<int,double> next[13];
std::map<int,double>::iterator it;
double sizeMemo[13][13];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sizeMemo[i][j]=sqrt((size[i]+size[j])*(size[i]+size[j])-(size[i]-size[j])*(size[i]-size[j]));
}
}
for(int i=0;i<n;i++){
memo[i][int(1<<i)]=size[i];
}
int state;
double len;
for(int i=1;i<n;i++){
for(int j=0;j<n;j++){
it=memo[j].begin();
while(it!=memo[j].end()){
for(int k=0;k<n;k++){
if((((*it).first)&(1<<k))==0){
state=(*it).first|(1<<k);
len=(*it).second+sizeMemo[j][k];
if(next[k].find(state)==next[k].end()){
next[k][state]=len;
}else if(next[k][state]>len){
next[k][state]=len;
}
}
}
it++;
}
}
for(int j=0;j<n;j++){
memo[j].clear();
memo[j].insert(next[j].begin(),next[j].end());
next[j].clear();
}
}
for(int i=0;i<n;i++){
it=memo[i].begin();
if(wide-size[i]-(*it).second>=0){
printf("OK\n");
return ;
}
}
printf("NA\n");
}
int main(){
double wide,size[13];
int i;
char t;
while(scanf("%lf",&wide)!=EOF){
i=0;
t=' ';
while(t!='\n'){
scanf("%lf%c",&size[i],&t);
i++;
}
calc(i,wide,size);
}
}
最終更新:2013年03月09日 05:22