解いた問題

5/25/2011

UVa10111

TCO2011 Qual3

参加記録。

250
Failed System Test

500
 class CoinMachinesGame {
public:
  int maxGames(int c, vector <int> need, vector <int> give) {
    int cnt = 0;

    while( true ){
      int tmp = c;

      const int size = need.size();
      int idx = 0;
      int mx = -(1 << 30 );
      for(int i=0; i<size; ++i){
        if( need[i] <= c ){
          if( mx < give[i] - need[i] ){
            idx = i;
            mx = give[i] - need[i];
          }
        }
      }

      int game = c / need[idx];
      c -= need[idx] * game;
      c += give[idx] * game;
      cnt += game;

      if( tmp == c )break;
    }

    return cnt;
  }
}; 
1000
class ComplementMachine2D {
public:
  int largestSubmatrix(vector <string> m) {

    int r = max( m.size(), m[0].size() );

    for(int begin=0; begin < m[0].size(); ++begin){
      for(int end = begin+1; end <= m[0].size(); ++end){

        for(int top = 0; top < m.size(); ++top){
          for(int bottom = top + 1; bottom <= m.size(); ++bottom){

            bool a, b;
            a = true;
            b = true;

            for(int i=begin; i<end; ++i){
              a = a && m[top][i] == m[bottom-1][i];
              b = b && m[top][i] != m[bottom-1][i];
            }

            if( !a && !b )break;

            r = max( r, (bottom - top) * (end - begin) );
          }
        }
      }
    }
    return r;
  }
};



250再挑戦
個数が多くて6個で、数値の範囲が1-15と小さいので、充分大きい数まで試せばいい。
class AllButOneDivisor {
public:
  int getMinimum(vector <int> v) {
    for(int n = 1; n < 100000; ++n){
      int cnt = 0;
      for(int i=0; i<v.size(); ++i){
        if( n % v[i] == 0 ) ++cnt;
      }
      if( cnt+1 == v.size() )return n;
    }
    return -1;
  }
};

5/22/2011

ppr

何やってんだ、オレは。
ネタ言語ぷんぷくりん
たぶん拡張子は.ppr
参考サイト
 http://kirei.biglobe.ne.jp/news/detail/20110426162331_pch19894

Source Code

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(void)
{
  map<string, char> token;
  token["ですけどぉぉお〜!"] = '>';
  token["ぷんぷくり〜ん"] = '<';
  token["私かわいそーなコ"] = '+';
  token["わかんなぁぁああい"] = '-';
  token["><"] = '.';
  token["覚えたぞぉ"] = ',';
  token["メモメモ"] = '[';
  token["キュンキュンキュン"] = ']';

  const int M = 30000;
  char mem[ M ];
  char *ptr = mem;
  fill( mem, mem + M, 0 );

  vector<string> v;
  for(string s; cin >> s; v.push_back(s));

  for(int i=0; i<v.size(); ++i){    
    if( token[ v[i] ] == '>' ) ptr++;
    else if( token[ v[i] ] == '<' ) ptr--;
    else if( token[ v[i] ] == '+' ) (*ptr)++;
    else if( token[ v[i] ] == '-' ) (*ptr)--;
    else if( token[ v[i] ] == '.' ) cout << *ptr;
    else if( token[ v[i] ] == ',' ) *ptr = cin.get();
    else if( token[ v[i] ] == '[' ){
      if( !(*ptr) ){
        int o = 0, c = 0;
        while(true){
          if( token[ v[i] ] == '[' )++o;
          if( token[ v[i] ] == ']' )++c;
          ++i;
          if( o == c )break;
        }
      }
    }
    else if( token[ v[i] ] == ']' ){
      if( *ptr ){
        int o = 0, c = 0;
        while(true){
          if( token[ v[i] ] == '[' )++o;
          if( token[ v[i] ] == ']' )++c;
          --i;
          if( o == c )break;
        } 
      }
    }
    else ;
  }
  cout << endl;
  return 0;
}
Input

私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
赤ちゃんかわいそうですぅ 赤ちゃんかわいそうですぅ 赤ちゃんかわいそうですぅ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ メモメモ ですけどぉぉお〜! 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ですけどぉぉお〜!
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私のハードディスクに記録しているのでありますっ
私のハードディスクに記録しているのでありますっ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ですけどぉぉお〜!
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ ぷんぷくり〜ん ぷんぷくり〜ん ぷんぷくり〜ん
わかんなぁぁああい キュンキュンキュン ですけどぉぉお〜! ><
ですけどぉぉお〜! 私かわいそーなコ 私かわいそーなコ ><
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ><
>< 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
>< ですけどぉぉお〜! わかんなぁぁああい ><
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
ヒヨコが死んじゃうじゃないですかぁっ
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
>< ぷんぷくり〜ん 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ >< わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい ><
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ><
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい >< わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい ><
ですけどぉぉお〜! 私かわいそーなコ ><



Output

Hello, world!


おまけ
 #include <iostream>

using namespace std;

int main(void)
{
  int cnt = 0;
  for(char c; cin >> c; ){
    if( c == '>' )cout << "ですけどぉぉお〜!" << ' ';
    if( c == '<' )cout << "ぷんぷくり〜ん" << ' ';
    if( c == '+' )cout << "私かわいそーなコ" << ' ';
    if( c == '-' )cout << "わかんなぁぁああい" << ' ';
    if( c == '.' )cout << "><" << ' ';
    if( c == ',' )cout << "覚えたぞぉ" << ' ';
    if( c == '[' )cout << "メモメモ" << ' ';
    if( c == ']' )cout << "キュンキュンキュン" << ' ';
    if( ++cnt % 4 == 0 )cout << endl;
  }
  cout << endl;
  return 0;
}

5/20/2011

sleep sort in clojure

話題のSleepSortを描いてみた。

やることは、
・配列の要素と同じ数のスレッドを作る。
・各スレッドは、1つの整数を受け取り、その時間だけsleepする。
・数字を返す。

wait() ==>> notifyAll() ==>> sleep() で実現したかったけど、やり方がよく分からない。
notifiAllしないと微妙に順番が変わる可能性がある? いや、したとしても、変わるか?
とりあえず、sleepする時間を10倍。
(defn sleep-sort [ a ]
  (if (not (empty? a))
    (do
      (.start (Thread.
               (fn []
                 (Thread/sleep (* (first a) 10))
                 (println (first a)))))
      (sleep-sort (rest a)))))

(sleep-sort '(6 1 2 3 7 4 8 9 5 0))
参考サイト
4chan BBS – Genius sorting algorithm: Sleep sort