By S.Acedanski, P.Chrzastowski, M.Hiron, Ł.Kowalik, M.Kubica, T.Malesinski, A.Niewiarowska, K.Onak, P.Pankov, A.Paterek, J.Pawlewicz, J.Radoszewski, P.Stanczyk, M.Stefaniak, T.Verhoeff, S.Wasik

**Read or Download International Olympiad in Informatics 2005 - tasks and solutions PDF**

**Similar international books**

Overseas Federation for info ProcessingThe IFIP sequence publishes state of the art leads to the sciences and applied sciences of knowledge and conversation. The scope of the sequence contains: foundations of computing device technological know-how; software program thought and perform; schooling; desktop purposes in know-how; conversation structures; structures modeling and optimization; details platforms; pcs and society; computers expertise; protection and safety in details processing structures; man made intelligence; and human-computer interplay.

Nuclear physics is almost immediately experiencing a thrust in the direction of primary phy sics questions. Low-energy experiments assist in checking out past latest stan dard versions of particle physics. the hunt for finite neutrino lots and neutrino oscillations, for proton decay, infrequent and forbidden muon and pion de cays, for an electrical dipole second of the neutron denote a number of the efforts to check cutting-edge theories of grand unification (GUTs, SUSYs, Superstrings, .

- Control and Automation, and Energy System Engineering: International Conferences, CA and CES3 2011, Held as Part of the Future Generation Information Technology Conference, FGIT 2011, in Conjunction with GDC 2011, Jeju Island, Korea, December 8-10, 2011.
- Computer Vision/Computer Graphics CollaborationTechniques: 4th International Conference, MIRAGE 2009, Rocquencourt, France, May 4-6, 2009. Proceedings
- Advances in Visual Computing: 6th International Symposium, ISVC 2010, Las Vegas, NV, USA, November 29 – December 1, 2010, Proceedings, Part II
- Conceptual Modeling - ER 2009: 28th International Conference on Conceptual Modeling, Gramado, Brazil, November 9-12, 2009. Proceedings

**Additional info for International Olympiad in Informatics 2005 - tasks and solutions**

**Example text**

5) . In order to compute all values of Av,t,l (respectively Av,t ), for some i,s l ∈ {0, . . , depth(v)}, we compute Bi,s v,l (respectively Cv ) for each i = 0, . . , deg(v) and s = 0, . . , k. e. n − 1. After computing all values of Av,t,l the program returns A (r, k, 0) as the final answer. Rivers Too Much Dynamic Programming Using dynamic programming twice would not be required if all the vertices in the tree had small number of children. Fortunately, we can easily construct a binary tree of villages that has the same minimal cost of transportation as the original one.

1 6 . . . . . . . . * . . 1 7 . . . . * . . . . * . . 1 8 . . . . . . . . . * . 1 9 . . * . . * . . . . . * . 2 0 . . . . . . . . . . * Fig. 1: A chart depicting winning and losing situations. The latter ones are marked with stars. (a) Let us assume, that after the first cut we have a l × m rectangle, where 2n l < n. Since n = 2k (m + 1) − 1, we have 2k−1 (m + 1) − 1 < l < 2k (m + 1) − 1. Hence, the second player can reduce the rectangle to 2k−1 (m + 1) − 1 × m, which is a losing position for the first player.

From the above we obtain that n × m is a losing position. n+1 3. Let us assume that n and m do not fulfill the above condition. Then, log2 ( m+1 ) is not an integer. Without the loss of generality, we can assume that n m. Let us denote by l the following value: l=2 n+1 ) log2 ( m+1 (m + 1) − 1 n We have n+1 l < n. So, the first player can cut a rectangle reducing it 2 < l + 1 < n + 1, and from this we obtain 2 to l × m, which is a losing position for the second player. The model solution follows the proof of the lemma and for every winning position it finds the appropriate move in logarithmic time.