HAOI 2008 题目第一时间发布!

This post is written in Chinese. Please consider using Google Translate

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

Related posts