HAOI 2008 題目第一時間發佈!

l 上午

一、 圓上的整點

求一個給定的圓(x^2+y^2=r^2),在圓周上有多少個點的座標是整數。

輸入

r

輸出

整點個數

樣例

輸入

4

輸出

4

數據規模

n<=2000 000 000

二、 硬幣購物

一共有4種硬幣。面值分別爲c1,c2,c3,c4。某人去商店買東西,去了tot次。

每次帶dici硬幣,買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

下面nLi

輸出

長度最大的一段的最小值 形成最小值方案的個數

樣例

輸入

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

相關日誌