COCI 2012/2013 Round #1

Brief description:

Problem A. Dom

... 刪除一個字元串中的所有的 「CAMBRIDGE」 中的字元。。

import re
print re.sub("[CAMBRIDGE]","",raw_input())
Problem B. F7

。。n 個人參加一個比賽,(沒有並列。。
。。其中第 i 名 獲得 n-i+1 分。。
現在給定 n 個人一個初始分數,問最後有多少人可能獲得總分第一?(並列第一也可以。。

I = lambda: map(int, raw_input().split())

n = input() 
a = [0] * n
for i in range(0, n):
	a[i] = input()

a.sort()

i = n		
best = 0

while i>=0:	
	i -= 1
	if (a[i]+n < best): break	
	if (a[i]+n-i > best): best = a[i]+n-i
print n-i-1	

(貪心。。Python 後三個點超時。。

。。。

Problem C. Koncert

。。。我這個蠢飛了啊。這個簡直就是 bug 啊。
。。。進去會場裡面還能帶票出來給別人。跪跪跪。。。
。模擬。。

Problem D. Ljubomora

。。n 個人 m 堆石子,第 i 堆石子有 ai 個。。現在要把這 m 堆石子分給這 n
個人,要求每個人拿到的石子必須來自同一堆。。。求方案使得拿到石子最多的人拿到的最少。。
二分答案判定。。(假設答案為 x,若滿足 則合法。。

Problem E. Snaga

定義 K(x) 為最小的不能整除 x 的數,定義 ( 。。

Problem F. Mars

要求構造一個 2^k 階的排列。。
滿足以此排列構造的滿二叉樹的每個結點,(每個結點是一個集合,以 ai 位置的數為葉子,然後每個結點由其左右子樹合併而成。。
。都是一段連續的數字。。已知每對數字之間存在一個斥力。。
最小化排列相鄰數字之間的斥力和。。。

ゆっくり読んでください ...

Codeforces Round #125

Brief description:

Problem A. About Bacteria
... 培養皿中的 x 只細菌下一秒會繁衍出 kx+b 只細菌。。(。。。
問如果初始培養皿中有 t 只細菌,至少多少秒才可以繁衍出不少於 z 只細菌。
。。。z 為初始為一隻細菌時,繁衍 n 秒的細菌總數。。。(。。。
(略,算術題。。不要把 z 真給算出來即可。。

Problem B. Jumping on Walls
一個忍者在一個坑裡, 左右各有一面牆,牆上有一些障礙,初始在最下角。
每秒鐘可以上下移動一格,或者跳到對面牆的恰好 +k 位置。。
。。問最終能出跳出這個坑。。
(略, Hash Dp 或者 BFS() 都行。。。。

Problem C. Delivering Carcinogen
給定一顆行星坐標 (xp, yp),軌道半徑 R,圍繞恆心運轉的線速度 vp,
以及一個飛船坐標 (x, y),飛船速度 v。。問到達 p 星球的最少時間。。
。。飛船運行過程中距恆星的距離不得低於 r。。(r ≤ R) ...

Problem D. Cube Snake
給定一個 n 階立方體,要求構造滿足下列性質的路徑:
對任意的 k < n, 存在至少 2 個 k 階子立方體, 滿足其中的數字取自一段連續區間。 Problem E. Gripping Story 空間中有一堆吸盤。 。。每個吸盤用 (xi, yi, mi, pi, ri) 表示。。。 。。自身坐標,重量。。。能抓起來的最大物品的重量,以及作用範圍。。。。 。。現給定飛船初始坐標。。(x0, y0)。。初始吸盤(p0, r0)... 問最多可以收集多少個吸盤。。。 (。。一旦得到一個吸盤以後以後就可以無限更換使用。。 (。。。注意注意飛船本身不動不動不動!。。並且吸盤吸到飛船里才能使用。。。OOrz。。 ゆっくり読んでください ...