HDU 2401 Baskets of Gold Coins（数学题）

HDU 2401 Baskets of Gold Coins（数学题）

Baskets of Gold Coins

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2066    Accepted Submission(s): 1241

Problem Description

You are given N baskets of gold coins. The baskets are numbered from 1 to N. In all except one of the baskets, each gold coin weighs w grams. In the one exceptional basket, each gold coin weighs w-d grams. A wizard appears on the scene and takes 1 coin from Basket 1, 2 coins from Basket 2, and so on, up to and including N-1 coins from Basket N-1. He does not take any coins from Basket N. He weighs the selected coins and concludes which of the N baskets contains the lighter coins. Your mission is to emulate the wizard's computation.

Input

The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain four positive integers, separated by one blank space. The first three integers are, respectively, the numbers N, w, and d, as described above. The fourth integer is the result of weighing the selected coins. N will be at least 2 and not more than 8000. The value of w will be at most 30. The value of d will be less than w.

Output

For each instance of the problem, your program will produce one line of output, consisting of one positive integer: the number of the basket that contains lighter coins than the other baskets.

Sample Input

10 25 8 1109

10 25 8 1045

8000 30 12 959879400

Sample Output

2

10

50

Source

​​ACM/ICPC 2008 Warmup（2）——测试帐号（杭州） ​​

题意：

有N个篮子，编号1—N，篮子中有很多金币，每个重w.但是有一个编号的篮子中，每个金币重w-d.女巫从第一个篮子中拿1个金币，第二个篮子中拿2个……第N-1中拿N-1个，第N中不拿，给出这些金币的总重量s，问：是第几个篮子中的金币重量较轻？

题解：

先求1—N篮子金币应有的总重量yuan=w*（1+n-1)(n-1)/2,然后求差值cha=原-s ，再除以金币重量差值d则得出轻金币的个数。若为0，则必在编号N的篮子中；若不为0，得到较轻金币的个数，即为所求编号。

AC代码：

#include#include#include#include#include#include#include#includetypedef long long LL;using namespace std;int main(){ int n,w,d,s,cha,yuan,ans; while(cin>>n>>w>>d>>s) { yuan=w*n*(n-1)/2; cha=yuan-s; ans=cha/d; if(ans==0) //其实就是差(cha)等于0 cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。