Friday, December 22, 2006
How to Look After Your Batteries
Finally! A real guide to treatment and maintenance of rechargeable batteries that are invading our lives. After a long time that we had to go on hearsay and rumors, this guide is really useful.
Before I forget, I found the article through Tom's Hardware Guide, which is one of the websites I (try to) frequent and a worthy site onto its own.
Tuesday, December 19, 2006
Sharif ICPC Regionals 2006 - Problem D
1:#include <map>
2:#include <string>
3:#include <vector>
4:#include <fstream>
5:#include <iomanip>
6:#include <iostream>
7:#include <algorithm>
8:
9:using namespace std;
10:
11:#define PROB_NAME "D"
12:
13:struct Emp
14:{
15: pair<int, bool> data [2];
16: Emp () {data[0].first = -1; data[0].second = true; data[1].first = -1; data[1].second = true;}
17:};
18:
19:pair<int, bool> Q (int cur, const vector<vector<int> > & children, vector<Emp> & mem);
20:
21:pair<int, bool> P (int cur, const vector<vector<int> > & children, vector<Emp> & mem)
22:{
23: if (mem[cur].data[0].first >= 0) return mem[cur].data[0];
24:
25: pair<int, bool> ret (1, true);
26: for (unsigned i = 0; i < children[cur].size(); ++i)
27: {
28: pair<int, bool> r = Q(children[cur][i], children, mem);
29: ret.first += r.first;
30: ret.second = (ret.second && r.second);
31: }
32: return mem[cur].data[0] = ret;
33:}
34:
35:pair<int, bool> Q (int cur, const vector<vector<int> > & children, vector<Emp> & mem)
36:{
37: if (mem[cur].data[1].first >= 0) return mem[cur].data[1];
38:
39: pair<int, bool> ret (0, true);
40: for (unsigned i = 0; i < children[cur].size(); ++i)
41: {
42: pair<int, bool> rp = P(children[cur][i], children, mem);
43: pair<int, bool> rq = Q(children[cur][i], children, mem);
44:
45: ret.first += max (rp.first, rq.first);
46: if (rp.first > rq.first) ret.second = (ret.second && rp.second);
47: else if (rp.first < rq.first) ret.second = (ret.second && rq.second);
48: else ret.second = false;
49: }
50: return mem[cur].data[1] = ret;
51:}
52:
53:int main ()
54:{
55: ifstream fin (PROB_NAME ".in");
56:
57: int n;
58: while (fin >> n && n != 0)
59: {
60: map<string, int> empnum;
61: #define EMPNUM(name) ((empnum.find(name) == empnum.end()) ? empnum[name] = (int)empnum.size() - 1 : empnum[name])
62:
63: vector<int> parent (n, -1);
64: vector<vector<int> > children (n);
65:
66: string foo, bar;
67: fin >> foo;
68:
69: empnum[foo] = 0;
70: for (int i = 1; i < n; ++i)
71: {
72: fin >> foo >> bar;
73: parent[EMPNUM(foo)] = EMPNUM(bar);
74: children[EMPNUM(bar)].push_back (EMPNUM(foo));
75: }
76:
77: vector<Emp> mem (n);
78: pair<int, bool> rp = P (0, children, mem);
79: pair<int, bool> rq = Q (0, children, mem);
80:
81: cout
82: << max(rp.first, rq.first) << " "
83: << ((rp.first == rq.first ||
84: (rp.first > rq.first && !rp.second) ||
85: (rq.first > rp.first && !rq.second)
86: ) ? "NO" : "YES") << endl;
87: cout << rp.first << ", " << rp.second << ", " << rq.first << ", " << rq.second << endl;
88: }
89:
90: return 0;
91:}
92:
Sharif ICPC Regionals 2006 - Problem C
1:#include <string>
2:#include <vector>
3:#include <fstream>
4:#include <iomanip>
5:#include <iostream>
6:#include <algorithm>
7:
8:using namespace std;
9:
10:#define PROB_NAME "C"
11:
12:bool duringnight (int b, int e) // [b,e)
13:{
14: b %= 24 * 60; e %= 24 * 60;
15: if (0 <= b && b < 6 * 60 + 1) return true; // Rules are not clear about the length
16: if (0 < e && e <= 6 * 60 + 1) return true; // of night. Is it 6 hours or 361 minutes?
17: return false;
18:}
19:
20:int main ()
21:{
22: ifstream fin (PROB_NAME ".in");
23:
24: while (0 == 0)
25: {
26: vector<string> name;
27: vector<int> length, minute;
28:
29: string foo;
30: while ((fin >> foo) && foo != "$" && foo != "--")
31: {
32: name.push_back (foo); length.push_back (-1); minute.push_back (-1);
33: fin >> length.back() >> minute.back();
34: }
35: if (foo == "--") break;
36:
37: string stname, enname;
38: int sth = -1, stm = -1;
39: char bar;
40:
41: fin >> stname >> enname >> sth >> bar >> stm;
42: fin >> foo;
43:
44: int st = int(find(name.begin(), name.end(), stname) - name.begin());
45: int en = int(find(name.begin(), name.end(), enname) - name.begin());
46:
47: int stt = (sth * 60 + stm) % (24 * 60);
48: int curt = stt;
49: int totallen = 0;
50: double fare = 0.0;
51: for (int i = st; i <= en; ++i)
52: {
53: for (int j = 0; j < length[i]; ++j)
54: {
55: bool night = duringnight (curt, curt + minute[i]);
56: double rate = (night ? 1.2 : 1.0);
57:
58: if (totallen < 10) fare += 1000 * rate;
59: else if (totallen < 30) fare += 250 * rate;
60: else fare += 100 * rate;
61:
62: totallen++;
63: curt += minute[i];
64: }
65: }
66: double avgkph = totallen / (60 * (curt - stt));
67: if (avgkph < 30) fare *= 1.1;
68:
69: cout << fare << endl;
70: }
71: return 0;
72:}
73:
Monday, December 18, 2006
Sharif ICPC Regionals 2006 - Problem B
1:#include <string>
2:#include <vector>
3:#include <fstream>
4:#include <iomanip>
5:#include <iostream>
6:#include <algorithm>
7:
8:using namespace std;
9:
10:#define PROB_NAME "B"
11:
12:typedef unsigned long long u64;
13:
14:u64 Pow10 [14] = {
15: 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
16: 100000000, 1000000000, 10000000000, 100000000000,
17: 1000000000000, 10000000000000
18:};
19:
20:u64 WildCount (const string & w, const string & x, unsigned i, unsigned remw)
21:{
22: if (i >= w.size()) return 0;
23: else if (w[i] == '?') return WildCount(w, x, i + 1, remw - 1) + Pow10[remw - 1] * ('9' - x[i]);
24: else if (w[i] > x[i]) return Pow10[remw];
25: else if (w[i] < x[i]) return 0;
26: else return WildCount(w, x, i + 1, remw);
27:}
28:
29:int main ()
30:{
31: ifstream fin (PROB_NAME ".in");
32:
33: string w, x;
34: while ((fin >> w >> x) && w != "#")
35: cout << WildCount(w, x, 0, (unsigned)count(w.begin(), w.end(), '?')) << endl;
36:
37: return 0;
38:}
39:
Sharif ICPC Regionals 2006 - Problem A
1:#include <string>
2:#include <vector>
3:#include <fstream>
4:#include <sstream>
5:#include <cassert>
6:#include <iostream>
7:#include <algorithm>
8:
9:using namespace std;
10:
11:#define PROB_NAME "A"
12:
13:struct Player
14:{
15: string name;
16: int number, role, exp;
17: bool captain, inarrange;
18:
19: Player (const string & line)
20: : number (0), exp (0), captain (false), inarrange (false)
21: {
22: stringstream ss (line);
23: ss >> number;
24: if (0 == number) return;
25:
26: char foo;
27: ss >> name >> foo;
28: role = (int)string("GDMS").find(foo);
29: assert (role >= 0 && role < 4);
30:
31: int y1, y2;
32: while (ss >> y1 >> foo >> y2)
33: exp += y2 - y1 + 1;
34: }
35: // Compare according to precedence in arrange
36: static bool CompArrange (const Player & p1, const Player & p2)
37: {
38: if (p1.role != p2.role) return p1.role < p2.role;
39: else return p1.number < p2.number;
40: }
41: // Compare according to precedence for captaincy(!)
42: static bool CompCaptaincy (const Player & p1, const Player & p2)
43: {
44: if (p1.inarrange != p2.inarrange) return p1.inarrange;
45: else if (p1.exp != p2.exp) return p1.exp > p2.exp;
46: else return p1.number > p2.number;
47: }
48: // Compare according to precedence for display
49: static bool CompListing (const Player & p1, const Player & p2)
50: {
51: if (p1.inarrange != p2.inarrange) return p1.inarrange;
52: else if (p1.captain != p2.captain) return p1.captain;
53: else if (p1.role != p2.role) return p1.role < p2.role;
54: else return p1.number < p2.number;
55: }
56:};
57:
58:int main ()
59:{
60: ifstream fin (PROB_NAME ".in");
61:
62: while (0 == 0)
63: {
64: vector<Player> p;
65: int avroles [4] = {0, 0, 0, 0};
66:
67: for (unsigned i = 0; i < 22; ++i)
68: {
69: string ln;
70: getline (fin, ln);
71: p.push_back (Player(ln));
72: if (0 == p.back().number) break;
73: avroles[p.back().role]++;
74: }
75: if (0 == p.size() || 0 == p.back().number) break;
76:
77: int a[4] = {1, 0, 0, 0};
78: char foo;
79: fin >> a[1] >> foo >> a[2] >> foo >> a[3];
80:
81: if (a[0] > avroles[0] || a[1] > avroles[1] ||
82: a[2] > avroles[2] || a[3] > avroles[3])
83: cout << "IMPOSSIBLE TO ARRANGE" << endl;
84: else
85: {
86: sort (p.begin(), p.end(), Player::CompArrange);
87: for (unsigned i = 0; i < p.size(); ++i)
88: if (a[p[i].role]-- > 0) p[i].inarrange = true;
89: sort (p.begin(), p.end(), Player::CompCaptaincy);
90: p[0].captain = true;
91: sort (p.begin(), p.end(), Player::CompListing);
92: for (unsigned i = 0; i < 11; ++i)
93: cout << p[i].number << " " << p[i].name
94: << " " << "GDMS"[p[i].role] << endl;
95: cout << endl;
96: }
97: }
98: return 0;
99:}
ICPC - Tehran Regionals 2006
(Background: I have been a participant in and/or an interested bystander of almost all programming contests in Iran over the past 5 years. The ICPC Regional is the most important such event in Iran on the course of a year. The latest one (2006) concluded this past Friday.)
The problem statements seem quite manageable this year (last year's was good too, only a bit numerous at 10.) I really believe 8 to be the ideal number of problems though (this year had 9,) for three-member teams in a 5-hour contest.
Aside from the number, this year's was the first time in the past 6 (7?) years that a team solved all the presented problems during the contest. And unfortunately, it wasn't an Iranian team. (Congratulations to the Singaporean team, by the way!)
Anyways, since I was not involved in this year's contest in any way, I feel left out! So I've decided to try and solve as many of the 9 as I can, and I'll post the codes here. I have to do it during my really busy days, and I don't think I can do all in less than a week. In any event, I want to try my hand at them before the judge data come out.
I'm trying to measure myself, so I won't read any more of the problems, until I have time to implement each one (I have read the first four, oops!)
Actually, two of them are already done. I'll post the codes in individual... posts.
Monday, December 11, 2006
Search for Extra-terrestrial Intelligence at Home
Have you ever looked at the stars and felt a fear of what they might hold or what they might not? A chilling fear, being alone for some, or not being alone for others! (This so sounded like something out of a bad TV show!)
Of course I'm talking about SETI@home! What else do you think I can be talking about? If you don't know what it is, read the home site, or here.
If you know and you're not a participant, go sign up. (This is me.)
If you are participating and not part of a team yet (and I know you) consider joining our team, the Deities of Cori Celesti! If you don't know what that is, well, Google and Wikipedia are your friends! And beware of lightning!
For those of you who are seriously considering to join: you have to have done greater-than-zero work units to be able to join any team.
One more thing. Another worthy project is Rosetta@home. And yes, you can participate in two projects at the same time! And they use the same client!
(By the way, I've just discovered that I have a xenophobic streak! Maybe Ender was doing the right thing after all! Go read the books. Their awesome!)
Sunday, December 10, 2006
Movie List Update
I've been experimenting with an H.264 codec lately (x264 obviously,) and while I'm not mightily impressed, the quality is a tad better. But it's much slower to encode, and definitely less portable (to standalone players and to codec-challenged people's computers.)
Anyway, here's the list:
Subscribe to:
Posts (Atom)