401, 10010, 10361, 537, 409, 10878, 10815, 644, 10115

UVa

401 - Palindromes
10010 - Where's Waldorf?
10361 - Automatic Poetry
537 - Artificial Intelligence?
409 - Excuses, Excuses!
10878 - Decode the tape
10815 - Andy's First Dictionary
644 - Immediate Decodability
10115 - Automatic Editing

問題概要

401 ある文が、回文/鏡に映しても同じ文 になるかどうか判定
10010 文字グリッドで、ある場所から8方位に読んだ時、ある文字列がどこに現れるか
10361 置換
537 物理の文章題を自動回答するプログラム
409 いくつかの文から、指定語句を最大に含む文を探す
10878 "Machines take me by surprise with great frequency." Alan Turing
10815 アンディ君の辞書を作る
644 一意復号(だったような)可能な符号化かどうか
10115 置換

Palindromes

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define INV '#'
char mirror_map[128];
void MakeMirrorMap(){
  for(int i = 0; i < sizeof(mirror_map)/sizeof(*mirror_map); ++i){
    mirror_map[i] = INV;
  }
  string from("AEHIJLMOSTUVWXYZ012358");
  string   to("A3HILJMO2TUVWXY501SEZ8");
  for(unsigned int i = 0; i < from.length(); ++i){
    mirror_map[ from[i] ] = to[i];
  }
}
bool CheckPalindrome( string s ){
  string tmp = s;
  reverse( tmp.begin(), tmp.end() );
  string s_sub = s.substr(0,s.length()/2);
  string tmp_sub = tmp.substr(0,s.length()/2);
  if( tmp_sub == s_sub ) return true;
  else return false;
}
bool CheckMirrored( string s ){
  string tmp = s;
  reverse( tmp.begin(), tmp.end() );
  for(unsigned int i = 0; i < tmp.length(); ++i){
    if( mirror_map[ tmp[i] ] != INV )
      tmp[i] = mirror_map[ tmp[i] ];
    else return false;
  }
  if( tmp == s )
    return true;
  return false;
}
int main(){
  bool bFirst = true;
  MakeMirrorMap();
  while(true){
    string s,t;

    cin >> s;
    t = s;
    for(int i = 0; i < s.length(); ++i){
      t[i] = s[i] == '0' ? 'O' : s[i];
    }
    if( cin.eof() )break;
    
    bool palindrome, mirror;

    palindrome = CheckPalindrome( t );
    mirror = CheckMirrored( t );

    if( palindrome && mirror ){
      cout << s << " -- is a mirrored palindrome.\n";
    }else if( palindrome ){
      cout << s << " -- is a regular palindrome.\n";
    }else if( mirror ){
      cout << s << " -- is a mirrored string.\n";
    }else{
      cout << s << " -- is not a palindrome.\n";
    }
    cout << endl;
  }
  return 0;
}

Where's Waldorf?

#include<iostream>
#include<vector>
#include<string>
#include<cctype>

#define MAX 52

using namespace std;

const int di[] = {-1,-1,0,1,1, 1, 0,-1};
const int dj[] = { 0, 1,1,1,0,-1,-1,-1};

inline bool inside(int m, int n, int i, int j){
  return 0 <= i && i < m && 0 <= j && j < n;
}

string tolower_s(string s){
  for(unsigned int i = 0; i < s.length(); ++i){
    s[i] = tolower( s[i] );
  }
  return s;
}

int main(){
  int cases;

  cin >> cases;
  for(int tc=0;tc<cases;++tc){
    pair<int,int> ans[MAX];
    vector<string> grid;
    vector<string> search;
    int m,n;

    if( tc != 0 ) cout << endl;

    cin >> m >> n;
    for(int i = 0; i < m; ++i){
      string s;
      cin >> s;
      s = tolower_s( s );
      grid.push_back( s );
    }
    int p;
    cin >> p;
    for(int i = 0; i < p; ++i){
      string s;
      cin >> s;
      s = tolower_s( s );
      search.push_back( s );
      ans[i] = make_pair(m,n);
    }

    for(int i = 0; i < m; ++i){
      for(int j = 0; j < n; ++j){
	for(int k = 0; k < 8; ++k){

	  int matched[MAX] = {0,};
	  for(int q=0;;++q){
	    int ti = i + q * di[k];
	    int tj = j + q * dj[k];
	    if( !inside(m,n,ti,tj) )break;
	    for(int l = 0; l < search.size(); ++l){
	      if( q < search[l].size() ){
		if( grid[ ti ][ tj ] == search[ l ][ q ] ){
		  ++matched[l];
		}
	      }
	    }
	  }
	  
	  for(int l = 0; l < search.size(); ++l){
	    if( search[l].length() == matched[l] ){
	      ans[l] = min(ans[l], make_pair(i,j));
	    }
	  }

	}
      }
    }

    for(int i = 0; i < search.size(); ++i){
      cout << ans[i].first+1 << ' ' << ans[i].second+1 << endl;
    }
    
  }
  return 0;
}

Automatic Poetry

#include<iostream>
#include<vector>
#include<string>
using namespace std;
void parse(const string &s,vector<string> &ret){
  string now;
  for(unsigned int i = 0; i < s.length(); ++i){
    if( s[i] == '<' ){
      ret.push_back( now );
      now.clear();
    }else if( s[i] == '>' ){
      ret.push_back( now );
      now.clear();
    }else now += s[i];
  }
  ret.push_back( now );
}
int main(){
  int cases;
  string dam;
  cin >> cases;
  getline(cin,dam);
  for(int tc=0;tc<cases;++tc){
    string poet, autopoet;
    vector<string> s;
    getline(cin,poet);
    getline(cin,autopoet);

    parse(poet,s);

    cout << s[0] << s[1] << s[2] << s[3] << s[4] << endl;
    autopoet.erase( autopoet.begin() + autopoet.find("..."), autopoet.end() );
    cout << autopoet << s[3] << s[2] << s[1] << s[4] << endl;
  }
  return 0;
}

Artificial Intelligence?

#include<iostream>
#include<string>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cstdlib>
using namespace std;

struct concept{
  double val;
  char c,unit;
};
typedef pair<concept,concept> parsed;
double realnumber(const char *c, char &unit){
  //sscanf(c,"%ld",&ret);
  double ret=0;
  int sign=1;
  int i = 0;
  bool decimal=false;
  int decim=0;

  if(c[i]=='-'){sign=-1;++i;}
  while(isdigit(c[i])||c[i]=='.'){
    if(c[i]=='.'){
      decimal = true;
      ++i;continue;
    }
    if(decimal){
      decim++;
    }else{
      ret *= 10;
    }
    int d=c[i]-'0';
    ret += d * ( decimal ? pow(10.0,-decim) : 1 );
    ++i;
  }
  if(c[i]=='m'||c[i]=='k'||c[i]=='M'){
    ret *= c[i]=='m'?0.001:(c[i]=='k'?1000:(c[i]=='M'?1000000:1));
    ++i;
  }
  unit = c[i];
  return sign * ret;
}
void parser(const string &s, parsed &p){
  bool first = true;
  concept con;
  for(unsigned int i = 0; i < s.length(); ++i){
    if( s[i] == '=' ){
      con.c = s[i-1];
      con.val = realnumber( s.c_str() + i + 1, con.unit );
      if(first){
	first=false;
	p.first=con;
      }else{
	p.second=con;
      }
    }
  }
  if(p.first.c == 'U' && p.second.c == 'P'){
    swap(p.first,p.second);
  }
  if(p.first.c == 'I' && p.second.c == 'P'){
    swap(p.first,p.second);
  }
  if(p.first.c == 'I' && p.second.c == 'U'){
    swap(p.first,p.second);
  }
}
int main(){
  int n;
  string s;
  cin >> n;
  getline(cin,s);
  for(int tc=0;tc<n;++tc){
    parsed p;
    concept c;
    getline(cin,s);
    parser(s,p);

    //cout << p.first.c << ":" << p.first.val << " " << p.second.c << ":" << p.second.val << endl;
    if(p.first.c == 'P' && p.second.c == 'U'){
      c.c = 'I';
      c.unit = 'A';
      c.val = p.first.val / p.second.val;
    }
    if(p.first.c == 'P' && p.second.c == 'I'){
      c.c = 'U';
      c.unit = 'V';
      c.val = p.first.val / p.second.val;
    }
    if(p.first.c == 'U' && p.second.c == 'I'){
      c.c = 'P';
      c.unit = 'W';
      c.val = p.first.val * p.second.val;
    }

    printf("Problem #%d\n", tc+1);
    printf("%c=%.2lf%c\n\n", c.c, c.val, c.unit);
  }
  return 0;
}

Excuses, Excuses!

#include<sstream>
#include<iostream>
#include<cctype>
#include<set>

using namespace std;

#define MAX 21

string tolower_s(string s){
  for(unsigned int i = 0; i < s.length(); ++i){
    s[i] = tolower(s[i]);
    if(!isalpha(s[i])){
      s[i] = ' ';
    }
  }
  return s;
}

int main(){
  int tc = 1;
  while(true){
    int n,e;
    int max_occur = 0;
    set<string> keys;
    string org_lines[MAX];
    int occurs[MAX] = {0,};
    string lines[MAX];
    
    cin>>n;
    if(cin.eof())break;
    cin>>e;

    cout << "Excuse Set #" << tc++ << endl;

    for(int i = 0; i < n; ++i){
      string s;
      cin >> s;
      keys.insert( s );
    }

    getline(cin,org_lines[0]);
    for(int i = 0; i < e; ++i){
      getline(cin,org_lines[i]);
      lines[i] = tolower_s(org_lines[i]);

      istringstream iss(lines[i]);
      while(!iss.eof()){
	string s;
	iss>>s;
	if(keys.find(s)!=keys.end()){
	  ++occurs[i];
	}
      }
    }

    for(int i = 0; i < e; ++i){
      max_occur = max( max_occur, occurs[i] );
    }
    for(int i = 0; i < e; ++i){
      if( occurs[i] == max_occur ){
	cout << org_lines[ i ] << endl;
      }
    }
    cout << endl;
  }
}

Decode the tape

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cassert>
#include<iomanip>

using namespace std;

char decode(const string &s)
{
  int pw=0;
  char ret=0;
  for(int i = s.length()-1; i >= 0; --i){
    if( s[i] == ' ' )
      ++pw;
    else if( s[i]=='o' ){
      ret += ( 1 << pw );
      ++pw;
    }
  }
  return ret;
}

int main()
{
  cin >> noskipws;
  while(true){
    char c;
    cin >> c;
    if(cin.eof())break;
    if(iscntrl(c))continue;
    if(c=='|'){
      string s;
      cin>>c;
      while(c!='|'){
	s+=c;
	cin>>c;
      }
      cout<<decode(s);
    }
  }
  return 0;
}

// nagamonmon

Andy's First Dictionary

#include<iostream>
#include<set>
#include<algorithm>
#include<cctype>
#include<iomanip>
using namespace std;
char Tolower(char c){
  return tolower(c);
}
int main(){
  char c;
  set<string> dictionary;
  while(true){
    bool bEnd=false;
    char s[201];
    int n = 0;
    while(true){
      if(1!=scanf("%c", &c)){bEnd=true;break;}
      if(isalpha(c)){
	s[n++] = c;
      }else{
	break;
      }
    }
    s[n]=0;
    if(n==0){if(bEnd)break;continue;}
    transform( s, s+n, s, Tolower );
    string t = s;
    dictionary.insert( t );
    if( bEnd )
      break;
  }

  for(set<string>::iterator itd=dictionary.begin(); itd!=dictionary.end(); ++itd){
    printf("%s\n", itd->c_str());
  }
  
  return 0;
}

Immediate Decodability

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
  int tc = 0;
  bool bEnd=false;
  while(true){
    vector<string> vs;
    string s;
    bool immediately = true;
    while(true){
      cin >> s;
      if(cin.eof()){
	bEnd=true;
	break;
      }
      if(s[0]=='9'){
	break;
      }
      vs.push_back( s );
    }
    if(bEnd)break;
    for(unsigned int i = 0; i < vs.size(); ++i){
      for(unsigned int j = 0; j < vs.size(); ++j){
	if( i != j ){
	  if( vs[j].find( vs[i] ) == 0 ){
	    immediately = false;
	  }
	}
      }
    }
    ++tc;
    if( immediately ){
      cout << "Set " << tc << " is immediately decodable\n";
    }else{
      cout << "Set " << tc << " is not immediately decodable\n";
    }
  }
  return 0;
}

Automatic Editing

#include<iostream>
#include<vector>
#include<string>
#include<cassert>
#include<climits>

using namespace std;

int BMMatcher(const char *str,
	      unsigned int strlen,
	      const char *pat,
	      unsigned int patlen){
  unsigned int pstr;
  unsigned int save;
  unsigned int ppat;
  unsigned int skip[UCHAR_MAX+1];

  for(pstr=0;pstr<UCHAR_MAX;++pstr)
    skip[pstr]=patlen;
  if(patlen == 0)
    return -1;
  for(pstr=0;pstr<patlen-1;++pstr)
    skip[pat[pstr]]=patlen-pstr-1;
  if(patlen>strlen)
    return -1;
  while(pstr<strlen){
    save=pstr;
    ppat=patlen-1;
    while(str[pstr]==pat[ppat]){
      if(ppat==0)
	return pstr;
      --ppat;
      --pstr;
    }
    pstr=max(save+1,pstr+skip[str[pstr]]);
  }
  return -1;
}

void Replace(string &s, const vector<string> &rep, const vector<string> &by){
  for(unsigned int r = 0; r < rep.size(); ++r){
    bool bCont = true;
    int p = -1;
    while(bCont){
      p = BMMatcher(s.c_str(),s.length(),rep[r].c_str(),rep[r].length());
      if( p != -1 ){
	s.replace( p, rep[r].length(), by[r] );
      }else{
	bCont = false;
      }
    }
  }
}

int main(){
  while(true){
    int n;
    string text,r,b;
    vector<string> replace;
    vector<string> by;

    cin >> n;
    if(cin.eof())break;
    if(n == 0) break;
    
    getline(cin,r);
    for(int i = 0; i < n; ++i){
      getline(cin,r);
      getline(cin,b);
      if(r==b)continue;
      replace.push_back( r );
      by.push_back( b );
    }
    getline(cin,text);

    Replace(text,replace,by);

    cout << text << endl;
  }
  return 0;
}

解法

実装するのみ。ただ、テープデコードの問題はいろいろとひどかった。