HAOI 2008 題目第一時間發佈！
本文正體字版由OpenCC轉換
l 上午
一、 圓上的整點
求一個給定的圓(x^2+y^2=r^2)，在圓周上有多少個點的座標是整數。
輸入
r
輸出
整點個數
樣例
輸入
4
輸出
4
數據規模
n<=2000 000 000
二、 硬幣購物
一共有4種硬幣。面值分別爲c1,c2,c3,c4。某人去商店買東西，去了tot次。
每次帶di枚ci硬幣，買si的價值的東西。請問每次有多少種付款方法。
輸入
第一行
c1,c2,c3,c4,tot
下面tot行
d1,d2,d3,d4,s
輸出
每次的方法數
樣例
輸入
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
輸出
4
27
數據規模
di,s<=100000
tot<=1000
三、 下落的圓盤
有n個圓盤從天而降，後面落下的可以蓋住前面的。求最後形成的封閉區域的周長。
輸入
n
ri xi y1
...
rn xn yn
輸出
最後的周長，保留三位小數
樣例
輸入
2
1 0 0
1 1 0
輸出
10.472
數據規模
n<=1000
l 下午
一、 木棍分割
有n根木棍粘在一起，每個長度爲Li，允許最多砍斷m個連接處。求長度最大的一段的最小值，並輸出構成最小值方案的個數。
輸入
第一行n m
下面n行Li
輸出
長度最大的一段的最小值 形成最小值方案的個數
樣例
輸入
3 2
1
1
10
輸出
10 2
數據規模
n<=50000
m<=1000
Li<=1000
二、 糖果傳遞
有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價爲1。求使所有人獲得均等糖果的最小代價。
輸入
小朋友個數n
下面n行 ai
樣例
輸入
4
1
2
5
4
輸出
4
數據規模
30% n<=1000
100% n<=1000000
上次修改時間 2017-05-22