[Assorted-commits] SF.net SVN: assorted: [826] problems/topcoder
Brought to you by:
yangzhang
From: <yan...@us...> - 2008-05-16 00:38:56
|
Revision: 826 http://assorted.svn.sourceforge.net/assorted/?rev=826&view=rev Author: yangzhang Date: 2008-05-15 17:38:51 -0700 (Thu, 15 May 2008) Log Message: ----------- picking up topcoder again... Added Paths: ----------- problems/topcoder/Bonuses/ problems/topcoder/Bonuses/Bonuses.cc problems/topcoder/Lottery/Lottery2.cc problems/topcoder/PenLift/PenLift.top Added: problems/topcoder/Bonuses/Bonuses.cc =================================================================== --- problems/topcoder/Bonuses/Bonuses.cc (rev 0) +++ problems/topcoder/Bonuses/Bonuses.cc 2008-05-16 00:38:51 UTC (rev 826) @@ -0,0 +1,297 @@ +// 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 pl(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 +// sum +class Bonuses { + public: + vector <int> getDivision(vector <int> points) { + vector <int> res(points.sz); + int tot = 0; + bounds(i,points) tot += points[i]; + int rem = 100; + vec(pair<int,int>) pairs(points.sz); + int n = points.sz; + vi per(n); + bounds(i,points) { + int p = floor(100.0 * points[i] / double(tot)); + pairs[i] = make_pair(-points[i],i); + per[i] = p; + rem -= p; + } +#if 1 + assert(rem>=0 && rem<points.sz); + ssort(pairs); + bounds(i,pairs) { + if (rem == 0) break; + per[pairs[i].second] += 1; + rem -= 1; + } + bounds(i,pairs) res[i] = per[i]; +#endif +#if 0 + vb done(n); + while (rem-- > 0) { + int h=1,b=0; + for(int i=0;i<n;i++) + if (!done[i] && points[i] > h) { + h = points[i]; + b = i; + } + done[b] = true; + pairs[b].first--; + } + bounds(i,pairs) res[pairs[i].second] = -pairs[i].first; +#endif + return res; + } +}; + + + + + + + +// 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 Added: problems/topcoder/Lottery/Lottery2.cc =================================================================== --- problems/topcoder/Lottery/Lottery2.cc (rev 0) +++ problems/topcoder/Lottery/Lottery2.cc 2008-05-16 00:38:51 UTC (rev 826) @@ -0,0 +1,338 @@ +// 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 print(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 Lottery { + public: + vector <string> sortByOdds(vector <string> rules) { + vector <string> res; + vec(pair<double, str>) pairs; + each(rule,rules) { + vs parts = splitstr(*rule, ": "); + string name = parts[0]; + vs attrs = split(parts[1]); + int choi = atoi(attrs[0].c_str()); + int blan = atoi(attrs[1].c_str()); + bool sort = attrs[2] == "T"; + bool uniq = attrs[3] == "T"; + pp(choi); + pp(blan); + pp(sort); + pp(uniq); + double poss = -1; + if (!sort && !uniq) { + trace(poss = powd(choi, blan)); + } else if (!sort && uniq) { + trace(poss = perms(choi, blan)); + } else if (sort && !uniq) { + trace(poss = combs(choi + blan - 1, blan)); + } else if (sort && uniq) { + trace(poss = combs(choi, blan)); + } else { + assert(false); + } + pairs.push_back(mkpair(poss, name)); + } + sort(pairs); + pp(pairs); + bounds(i,pairs) res.push_back(pairs[i].second); + return res; + } +}; + + + + + + + +// BEGIN CUT HERE +int main() { + { + string rulesARRAY[] = {"PICK ANY TWO: 10 2 F F" + ,"PICK TWO IN ORDER: 10 2 T F" + ,"PICK TWO DIFFERENT: 10 2 F T" + ,"PICK TWO LIMITED: 10 2 T T"}; + vector <string> rules( rulesARRAY, rulesARRAY+ARRSIZE(rulesARRAY) ); + string retrunValueARRAY[] = { "PICK TWO LIMITED", "PICK TWO IN ORDER", "PICK TWO DIFFERENT", "PICK ANY TWO" }; + vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) ); + Lottery theObject; + eq(0, theObject.sortByOdds(rules),retrunValue); + } + { + string rulesARRAY[] = {"INDIGO: 93 8 T F", + "ORANGE: 29 8 F T", + "VIOLET: 76 6 F F", + "BLUE: 100 8 T T", + "RED: 99 8 T T", + "GREEN: 78 6 F T", + "YELLOW: 75 6 F F"} + ; + vector <string> rules( rulesARRAY, rulesARRAY+ARRSIZE(rulesARRAY) ); + string retrunValueARRAY[] = { "RED", "ORANGE", "YELLOW", "GREEN", "BLUE", "INDIGO", "VIOLET" }; + vector <string> retrunValue( retrunValueARRAY, retrunValueARRAY+ARRSIZE(retrunValueARRAY) ); + Lottery theObject; + eq(1, theObject.sortByOdds(rules),retrunValue); + } + { + Lottery theObject; + eq(2, theObject.sortByOdds(vector <string>()),vector <string>()); + } +#ifdef WIN32 + cin.get(); +#endif + return 0; +} +// END CUT HERE Added: problems/topcoder/PenLift/PenLift.top =================================================================== --- problems/topcoder/PenLift/PenLift.top (rev 0) +++ problems/topcoder/PenLift/PenLift.top 2008-05-16 00:38:51 UTC (rev 826) @@ -0,0 +1,56 @@ +class PenLift + int numTimes(str* segments, int n) + // init + var xs={} ys={} + var segs = for seg in segments + int a b c d + seg ~ "a b c d" + xs ++= [a c] + ys ++= [b d] + (a b c d) + var packs = for zs in [xs ys] + var pack = {} + var j = 0 + for v in zs + pack(v) = j++ + assert j < 100 + pack + + // adj + var adj = arr((200,200),{}) + for (a b c d) in segs + [a c] = [a c] map packs(0) + [b d] = [b d] map packs(1) + if a == c + var x = a + if b > d: swap b d + for y in [b,d) + adj(x,y) += (x,y+1) + adj(x,y+1) += (x,y) + else b == d + var y = b + order a c // if a > c: swap a c + for x in [a,c) + adj(x,y) += (x+1,y) + adj(x+1,y) += (x,y) + + // search + var num = -1 + for x to 100 + for y to 100 + if adj(x y) not empty + var q = Q() + q push (x y) + var odds = 0 + while q not empty + (x y) = x pop + var ps = adj(x y) + if ps % 2 == 1: odds++ + for p=(x y) in ps + if adj(p) not empty + q push p + ps clear + if n % 2 == 0 or odds <= 2: odds = 2 + num += odds / 2 + + num This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |