[Assorted-commits] SF.net SVN: assorted: [841] problems/topcoder

[<yan...@us...>]

Revision: 841
          http://assorted.svn.sourceforge.net/assorted/?rev=841&view=rev
Author:   yangzhang
Date:     2008-06-01 17:19:27 -0700 (Sun, 01 Jun 2008)

Log Message:
-----------
added some problem retries

Added Paths:
-----------
    problems/topcoder/BinaryCode/BinaryCode2.cc
    problems/topcoder/Bonuses/Bonuses2.cc

Added: problems/topcoder/BinaryCode/BinaryCode2.cc
===================================================================
--- problems/topcoder/BinaryCode/BinaryCode2.cc	                        (rev 0)
+++ problems/topcoder/BinaryCode/BinaryCode2.cc	2008-06-02 00:19:27 UTC (rev 841)
@@ -0,0 +1,340 @@
+// vim:et:sw=2:ts=2
+
+// TODO
+// - strip out all comments
+// - trim the unused includes/macros/typedefs/code
+
+// $BEGINREUSE$
+#include <algorithm>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdio>
+#include <cstdlib>
+#include <deque>
+#include <functional>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <vector>
+using namespace std;
+
+#define dd(x) cout << #x << " = " << x << endl
+#define len length()
+#define sz size()
+#define pb(x) push_back((x));
+#define all(A) (A).begin(), (A).end()
+#define rall(A) (A).rbegin(), (A).rend()
+#define each(it,xs) for (typeof(xs.begin()) it = xs.begin(); it != xs.end(); it++)
+#define bounds(i,xs) for (typeof((xs).size()) i = 0; i < (xs).size(); i++)
+#define range(i,l,h) for (typeof(l) i = (l); i < (h); i++)
+#define event(x) { cout << __FILE__ << ":" << __LINE__ << ": " << #x << endl; x; }
+#define trace(x) { cout << __FILE__ << ":" << __LINE__ << ": "; pp(x); x; }
+#define ping cout << "ping" << endl;
+#define pong cout << "pong" << endl;
+
+// CHOOSE
+//int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
+//int dx[] = {1,1,1,0,0,-1,-1,-1}, dy[] = {1,0,-1,1,-1,1,0,-1};
+
+typedef vector<int> vi;
+typedef vector<string> vs;
+typedef vector<bool> vb;
+typedef vector<vi> vvi;
+typedef vector<vs> vvs;
+typedef vector<vb> vvb;
+typedef long long ll;
+#define vec(x) vector< x >
+typedef string str;
+
+template<typename T> inline T mod(T a, T b) { return (a % b + b) % b; }
+template<typename T> inline void rev(T xs) { std::reverse(all(xs)); }
+template<typename T> inline void sort(T xs) { std::sort(all(xs)); }
+template<typename T> inline void ssort(T xs) { std::stable_sort(all(xs)); }
+template<typename T> inline void unique(T xs) { std::unique(all(xs)); }
+template<typename T> inline void uniq(T xs) { xs.erase( std::unique(all(xs)), xs.end() ); }
+template<typename T, typename U> inline void fill(T xs, U x) { std::fill(all(xs), x); }
+template<typename T, typename U> inline U minim(const T xs) { return *std::min_element(all(xs)); }
+template<typename T, typename U> inline U maxim(const T xs) { return *std::max_element(all(xs)); }
+template<typename T> inline void nextp(T xs) { return std::next_permutation(all(xs)); }
+template<typename T> inline void prevp(T xs) { return std::prev_permutation(all(xs)); }
+template<typename T> inline string tos(T x) { stringstream s; s << x; return s.str(); }
+inline int powi(int a, int b) { return int( std::pow(double(a), double(b)) ); }
+inline int powl(ll a, ll b) { return ll( std::pow(double(a), double(b)) ); }
+template<typename T> inline void print(const T & x) { cout << x << endl; }
+#define pp(x) cout << #x << ' ' << x << endl;
+
+inline ll gcd(ll a, ll b) {
+  if (a < 0 && b < 0) return gcd(-a,-b);
+  if (a == 0) return b;
+  if (b == 0) return a;
+  if (a > b) return gcd(b, a);
+  if (!(b % a)) return a;
+  return gcd(a, b % a);
+}
+
+// TODO merge the following two pieces of code together
+
+template <typename T>
+inline ostream& operator << (ostream& os, const set<T> & xs) {
+  bounds(i,xs) os << i ? ", " : "{ " << xs[i];
+  return os << " }";
+}
+
+template <typename T>
+inline ostream& operator << (ostream& os, const vector<T> & xs) {
+  bounds(i,xs) os << i ? ", " : "{ " << xs[i];
+  return os << " }";
+}
+
+template<class S,class T>
+inline ostream & operator << (ostream & os, const pair<S,T> & a) {
+  os << "(" << a.first << ", " << a.second << ")";
+  return os;
+}
+
+vs split( const string & s, const string & delim = " " ) {
+  vs res;
+  string t;
+  each(c,s) {
+    if ( delim.find( *c ) != string::npos ) {
+      if ( !t.empty() ) {
+        res.pb( t );
+        t = "";
+      }
+    } else {
+      t += *c;
+    }
+  }
+  if ( ! t.empty() ) {
+    res.push_back(t);
+  }
+  return res;
+}
+
+vi ints( const str & s, const str & delim = " " ) {
+  vs ss = split( s, delim );
+  vi is;
+  each(s,ss) is.push_back( atoi( s->c_str() ) );
+  return is;
+}
+
+string vi2str( const vi xs ) {
+  string s(xs.sz, '\0');
+  bounds(i,xs) s[i] = xs[i] + '0';
+  return s;
+}
+
+// following is needed for 'main'
+#define ARRSIZE(x) (sizeof(x)/sizeof(x[0]))
+// $ENDREUSE$
+
+
+
+
+
+
+
+// BEGIN CUT HERE
+template<typename T> void print( T a ) {
+  cerr << a;
+}
+void print( long long a ) {
+  cerr << a << "L";
+}
+void print( string a ) {
+  cerr << '"' << a << '"';
+}
+template<typename T> void print( vector<T> a ) {
+  cerr << "{";
+  bounds(i,a) {
+    if ( i != 0 ) cerr << ", ";
+    print( a[i] );
+  }
+  cerr << "}" << endl;
+}
+template<typename T> void eq( int n, T have, T need ) {
+  if ( have == need ) {
+    cerr << "Case " << n << " passed." << endl;
+  } else {
+    cerr << "Case " << n << " failed: expected ";
+    print( need );
+    cerr << " received ";
+    print( have );
+    cerr << "." << endl;
+  }
+}
+template<typename T> void eq( int n, vector<T> have, vector<T> need ) {
+  if( have.size() != need.size() ) {
+    cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements." << endl;
+    cerr << "  have: "; print( have );
+    cerr << "  need: "; print( need );
+    return;
+  }
+  for( size_t i= 0; i < have.size(); i++ ) {
+    if( have[i] != need[i] ) {
+      cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << "." << endl;
+      cerr << "  have: "; print( have );
+      cerr << "  need: "; print( need );
+      return;
+    }
+  }
+  cerr << "Case " << n << " passed." << endl;
+}
+void eq( int n, string have, string need ) {
+  if ( have == need ) {
+    cerr << "Case " << n << " passed." << endl;
+  } else {
+    cerr << "Case " << n << " failed: expected ";
+    print( need );
+    cerr << " received ";
+    print( have );
+    cerr << "." << endl;
+  }
+}
+// END CUT HERE
+
+
+
+
+
+
+
+
+
+
+
+
+
+// asdf
+class BinaryCode {
+  public:
+  vector <string> decode(string message) {
+#if 0
+    vector <string> res(2);
+    string & msg = message;
+    for (int init = 0; init <= 1; init++) {
+      bool bad = false;
+      vi xs(msg.sz);
+      xs[0] = init;
+      if (msg.sz > 1) {
+        int x = msg[0] - '0';
+        xs[1] = x - xs[0];
+
+        for (int i = 2; i < xs.sz; i++) {
+          int x = msg[i-1] - '0';
+          xs[i] = x - xs[i-1] - xs[i-2];
+          pp(i);
+          pp(x);
+          pp(xs[i]);
+          pp(xs[i-1]);
+          pp(xs[i-2]);
+          if (xs[i] != 0 && xs[i] != 1) event(bad = true);
+          cout << endl;
+        }
+        if (msg[msg.sz - 1] - '0' != xs[xs.sz - 1] + xs[xs.sz - 2]) {
+          event(bad = true);
+        }
+      } else {
+        if (msg[0] - '0' != xs[0]) event(bad = true);
+      }
+
+      ping;
+      res[init] = bad ? string("NONE") : vi2str(xs);
+      pong;
+    }
+    return res;
+#endif
+#if 0
+    vector <string> res(2);
+    string& msg = message;
+    for (int init = 0; init < 2; init++) {
+      vi xs(msg.sz);
+      bool bad = false;
+      int ln = msg.sz;
+      xs[0] = init;
+      for (int i = 1; i < msg.sz; i++) {
+        int m = msg[i-1] - '0';
+        int x = xs[i] = m - xs[i-1] - (i-2>=0 ? xs[i-2] : 0);
+        if (x != 0 && x != 1) bad = true;
+      }
+      if (msg[ln - 1] - '0' != xs[ln-1] + (ln > 1 ? xs[ln-2] : 0))
+        bad = true;
+      res[init] = bad ? string("NONE") : vi2str(xs);
+    }
+    return res;
+#endif
+    vector<string> res(2);
+    string & msg = message;
+    for (int init = 0; init < 2; init++) {
+      int ln = msg.sz;
+      vi xs(ln);
+      xs[0] = init;
+      bool bad = false;
+      for (int i = 1; i < ln; i++) {
+        int m = msg[i-1] - '0';
+        xs[i] = m - xs[i-1] - (i-2>=0 ? xs[i-2] : 0);
+        if (xs[i] != 0 && xs[i] != 1) bad = true;
+      }
+      if (msg[ln-1] - '0' != xs[ln-1] + xs[ln-2])
+        bad = true;
+      res[init] = bad ? string("NONE") : vi2str(xs);
+    }
+    return res;
+  }
+};
+
+
+
+
+
+
+
+// BEGIN CUT HERE
+int main() {
+    {
+        string retrunValueARRAY[] = { "011100011",  "NONE" };
+        vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        BinaryCode theObject;
+        eq(0, theObject.decode("123210122"),retrunValue);
+    }
+    {
+        string retrunValueARRAY[] = { "01",  "10" };
+        vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        BinaryCode theObject;
+        eq(1, theObject.decode("11"),retrunValue);
+    }
+    {
+        string retrunValueARRAY[] = { "NONE",  "11001" };
+        vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        BinaryCode theObject;
+        eq(2, theObject.decode("22111"),retrunValue);
+    }
+    {
+        string retrunValueARRAY[] = { "NONE",  "NONE" };
+        vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        BinaryCode theObject;
+        eq(3, theObject.decode("123210120"),retrunValue);
+    }
+    {
+        string retrunValueARRAY[] = { "NONE",  "NONE" };
+        vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        BinaryCode theObject;
+        eq(4, theObject.decode("3"),retrunValue);
+    }
+    {
+        string retrunValueARRAY[] = { "01101001101101001101001001001101001",  "10110010110110010110010010010110010" };
+        vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        BinaryCode theObject;
+        eq(5, theObject.decode("12221112222221112221111111112221111"),retrunValue);
+    }
+#ifdef WIN32
+  cin.get();
+#endif
+  return 0;
+}
+// END CUT HERE

Added: problems/topcoder/Bonuses/Bonuses2.cc
===================================================================
--- problems/topcoder/Bonuses/Bonuses2.cc	                        (rev 0)
+++ problems/topcoder/Bonuses/Bonuses2.cc	2008-06-02 00:19:27 UTC (rev 841)
@@ -0,0 +1,325 @@
+// vim:et:sw=2:ts=2
+
+// TODO
+// - strip out all comments
+// - trim the unused includes/macros/typedefs/code
+
+// $BEGINREUSE$
+#include <algorithm>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdio>
+#include <cstdlib>
+#include <deque>
+#include <functional>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <utility>
+#include <vector>
+using namespace std;
+
+#define dd(x) cout << #x << " = " << x << endl
+#define len length()
+#define sz size()
+#define pb(x) push_back((x));
+#define all(A) (A).begin(), (A).end()
+#define rall(A) (A).rbegin(), (A).rend()
+#define each(it,xs) for (typeof(xs.begin()) it = xs.begin(); it != xs.end(); it++)
+#define bounds(i,xs) for (typeof((xs).size()) i = 0; i < (xs).size(); i++)
+#define range(i,l,h) for (typeof(l) i = (l); i < (h); i++)
+#define event(x) { cout << __FILE__ << ":" << __LINE__ << ": " << #x << endl; x; }
+#define trace(x) { \
+  typeof(x) __x = x; \
+  cout << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << __x << endl; \
+  __x; \
+}
+#define ping cout << "ping" << endl;
+#define pong cout << "pong" << endl;
+
+// CHOOSE
+//int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
+//int dx[] = {1,1,1,0,0,-1,-1,-1}, dy[] = {1,0,-1,1,-1,1,0,-1};
+
+typedef vector<int> vi;
+typedef vector<string> vs;
+typedef vector<bool> vb;
+typedef vector<vi> vvi;
+typedef vector<vs> vvs;
+typedef vector<vb> vvb;
+typedef long long ll;
+#define vec(x...) vector< x >
+typedef string str;
+
+template<typename T> inline T mod(T a, T b) { return (a % b + b) % b; }
+template<typename T> inline void rev(T & xs) { std::reverse(all(xs)); }
+template<typename T> inline void sort(T & xs) { std::sort(all(xs)); }
+template<typename T> inline void ssort(T & xs) { std::stable_sort(all(xs)); }
+template<typename T> inline void unique(T & xs) { std::unique(all(xs)); }
+template<typename T> inline void uniq(T & xs) { xs.erase( std::unique(all(xs)), xs.end() ); }
+template<typename T, typename U> inline void fill(T & xs, U & x) { std::fill(all(xs), x); }
+template<typename T, typename U> inline U minim(const T & xs) { return *std::min_element(all(xs)); }
+template<typename T, typename U> inline U maxim(const T & xs) { return *std::max_element(all(xs)); }
+template<typename T> inline void nextp(T & xs) { return std::next_permutation(all(xs)); }
+template<typename T> inline void prevp(T & xs) { return std::prev_permutation(all(xs)); }
+template<typename T> inline string tos(T & x) { stringstream s; s << x; return s.str(); }
+// pow, powl, powf are std
+inline double powd(double a, double b) { return std::pow(a, b); }
+inline int powi(int a, int b) { return int( std::pow(double(a), double(b)) ); }
+inline int powll(ll a, ll b) { return ll( std::pow(double(a), double(b)) ); }
+template<typename T> inline void pl(const T & x) { cout << x << endl; }
+template<typename T, typename U> inline pair<T,U> mkpair(T t, U u) { return make_pair(t,u); }
+#define pp(x) cout << #x << " = " << x << endl;
+
+inline ll gcd(ll a, ll b) {
+  if (a < 0 && b < 0) return gcd(-a,-b);
+  if (a == 0) return b;
+  if (b == 0) return a;
+  if (a > b) return gcd(b, a);
+  if (!(b % a)) return a;
+  return gcd(a, b % a);
+}
+
+// TODO merge the following two pieces of code together
+
+template <typename T>
+inline ostream& operator << (ostream& os, const set<T> & xs) {
+  os << "{ ";
+  bounds(i,xs) os << (i ? ", " : "") << xs[i];
+  return os << " }";
+}
+
+template <typename T>
+inline ostream& operator << (ostream& os, const vector<T> & xs) {
+  os << "[ ";
+  bounds(i,xs) os << (i ? ", " : "") << xs[i];
+  return os << " ]";
+}
+
+template<class S,class T>
+inline ostream & operator << (ostream & os, const pair<S,T> & a) {
+  os << "(" << a.first << ", " << a.second << ")";
+  return os;
+}
+
+vs split( const string & s, const string & delim = " " ) {
+  vs res;
+  string t;
+  each(c,s) {
+    if ( delim.find( *c ) != string::npos ) {
+      if ( !t.empty() ) {
+        res.pb( t );
+        t = "";
+      }
+    } else {
+      t += *c;
+    }
+  }
+  if ( ! t.empty() ) {
+    res.push_back(t);
+  }
+  return res;
+}
+
+vs splitstr( const str & s, const str & glue = " " ) {
+  vs res;
+  str::size_type i = 0;
+  str::size_type ln = glue.sz;
+  while (true) {
+    str::size_type pos = s.find(glue, i);
+    res.push_back(string(s, i, pos));
+    if (pos == str::npos) break;
+    i = pos + ln;
+  }
+  return res;
+}
+
+vi ints( const str & s, const str & delim = " " ) {
+  vs ss = split( s, delim );
+  vi is;
+  each(s,ss) is.push_back( atoi( s->c_str() ) );
+  return is;
+}
+
+string vi2str( const vi xs ) {
+  string s(xs.sz, '\0');
+  bounds(i,xs) s[i] = xs[i] + '0';
+  return s;
+}
+
+template<typename T, typename U> inline U realfact(T x) {
+  ll f = 1;
+  range(i,1,x+1) f *= i;
+  return f;
+}
+
+template<typename T> inline ll factl(T x) { return realfact<T,ll>(x); }
+template<typename T> inline int facti(T x) { return realfact<T,int>(x); }
+
+ll perms(ll n, ll r) {
+  assert(n >= r);
+  ll p = 1;
+  for (ll i = n; i > n-r; i--) p *= i;
+  return p;
+}
+
+ll combs(ll n, ll k) {
+  return perms(n,k) / factl(k);
+}
+
+// following is needed for 'main'
+#define ARRSIZE(x) (sizeof(x)/sizeof(x[0]))
+// $ENDREUSE$
+
+
+
+
+
+
+
+// BEGIN CUT HERE
+template<typename T> void print( T a ) {
+  cerr << a;
+}
+void print( long long a ) {
+  cerr << a << "L";
+}
+void print( string a ) {
+  cerr << '"' << a << '"';
+}
+template<typename T> void print( vector<T> a ) {
+  cerr << "{";
+  bounds(i,a) {
+    if ( i != 0 ) cerr << ", ";
+    print( a[i] );
+  }
+  cerr << "}" << endl;
+}
+template<typename T> void eq( int n, T have, T need ) {
+  if ( have == need ) {
+    cerr << "Case " << n << " passed." << endl;
+  } else {
+    cerr << "Case " << n << " failed: expected ";
+    print( need );
+    cerr << " received ";
+    print( have );
+    cerr << "." << endl;
+  }
+}
+template<typename T> void eq( int n, vector<T> have, vector<T> need ) {
+  if( have.size() != need.size() ) {
+    cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements." << endl;
+    cerr << "  have: "; print( have );
+    cerr << "  need: "; print( need );
+    return;
+  }
+  for( size_t i= 0; i < have.size(); i++ ) {
+    if( have[i] != need[i] ) {
+      cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << "." << endl;
+      cerr << "  have: "; print( have );
+      cerr << "  need: "; print( need );
+      return;
+    }
+  }
+  cerr << "Case " << n << " passed." << endl;
+}
+void eq( int n, string have, string need ) {
+  if ( have == need ) {
+    cerr << "Case " << n << " passed." << endl;
+  } else {
+    cerr << "Case " << n << " failed: expected ";
+    print( need );
+    cerr << " received ";
+    print( have );
+    cerr << "." << endl;
+  }
+}
+// END CUT HERE
+
+
+
+
+
+
+
+
+
+
+
+
+
+// asdf
+class Bonuses {
+  public:
+  vector <int> getDivision(vector <int> points) {
+#if 0
+    vector <int> res(points.size());
+    int sum = 0;
+    int n = points.size();
+    int rem = 100;
+    for (int i = 0; i < n; i++) sum += points[i];
+    vector< pair<int,int> > a(n);
+    vector<int> p(n);
+    for (int i = 0; i < n; i++) {
+      a[i] = make_pair( -points[i], i );
+      p[i] = 100 * points[i] / sum;
+      rem -= p[i];
+    }
+    std::sort(a.begin(), a.end());
+    //pp(a);
+    for (int i = 0; i < n; i++) {
+      if (rem == 0) break;
+      p[a[i].second]++;
+      rem--;
+    }
+    for (int i = 0; i < n; i++)
+      res[i] = p[i];
+    return res;
+#endif
+  }
+};
+
+
+
+
+
+
+
+// BEGIN CUT HERE
+int main() {
+    {
+        int pointsARRAY[] = {1,2,3,4,5};
+        vector <int> points( pointsARRAY, pointsARRAY+ARRSIZE(pointsARRAY) );
+        int retrunValueARRAY[] = { 6,  13,  20,  27,  34 };
+        vector <int> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        Bonuses theObject;
+        eq(0, theObject.getDivision(points),retrunValue);
+    }
+    {
+        int pointsARRAY[] = {5,5,5,5,5,5};
+        vector <int> points( pointsARRAY, pointsARRAY+ARRSIZE(pointsARRAY) );
+        int retrunValueARRAY[] = { 17,  17,  17,  17,  16,  16 };
+        vector <int> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        Bonuses theObject;
+        eq(1, theObject.getDivision(points),retrunValue);
+    }
+    {
+        int pointsARRAY[] = {485, 324, 263, 143, 470, 292, 304, 188, 100, 254, 296,
+            255, 360, 231, 311, 275,  93, 463, 115, 366, 197, 470};
+        vector <int> points( pointsARRAY, pointsARRAY+ARRSIZE(pointsARRAY) );
+        int retrunValueARRAY[] = { 8,  6,  4,  2,  8,  5,  5,  3,  1,  4,  5,  4,  6,  3,  5,  4,  1,  8,  1,  6,  3,  8 };
+        vector <int> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) );
+        Bonuses theObject;
+        eq(2, theObject.getDivision(points),retrunValue);
+    }
+#ifdef WIN32
+  cin.get();
+#endif
+  return 0;
+}
+// END CUT HERE


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.