|
Problem Description 威威猫不是一只普通的猫，普通的猫喜欢吃鱼，但威威猫最喜欢吃鸡腿。他每天都在不停的吃啊吃，吃了一只又一只鸡腿。现在他遇到了一个难题，如果他的体重太胖那么他的主人就不给他吃鸡腿了，所以他需要你的帮助。 威威猫的身体由n个器官构成，由于他的身体很特殊所以他的增长也很特殊（不要问为什么，喜欢吃鸡腿的猫已经够奇怪了）。他的增长有个k1和k2系数，而且每天的增长量和前一天有关，我们假设这n个器官在第i天的数值分别是a(i,1), a(i,2), a(i,3) …… a(i,n)，那么，第i+1天他每个器官的数值就会变成: a(i+1,1) = k1 * a(i,1) + k2 * a(i,2) a(i+1,2) = k1 * a(i,2) + k2 * a(i,3) ...... a(i+1,n) = k1 * a(i,n) + k2 * a(i,1) 威威猫的体重等于他的所有器官的数值之和，并且他还拥有一个特殊的机能，就是会自动检测自己的体重，如果他的体重比K大，那么就会自动停止生长（为了每天都能吃到鸡腿），由于威威猫的特殊身体构造他的体重是可能会变成负数的。 现在我给你n个器官的初始数值和他的增长系数k1,k2，请问他几天之后会停止生长，如果他永远无法停止生长那么就输出"inf"。(引号不用输出)
Input 输入数据第一行是一个正整数T，表示有T组测试数据； 每组数据的第一行包含4个数字n,k1,k2,k，代表威威猫有n个器官，他的生长系数是k1,k2，当体重超过k的时候他就停止生长。 接下来的一行是n个数ai，代表威威猫每个器官第一天的数值是多少。
[Technical Specification] T <= 100 1 <= n <= 10000 -100 <= k1, k2 <= 100 1 <= k <= 10 ^ 18 1 <= ai <= 1000（1 <= i <= n）
Output 对于每组测试数据，请首先输出"Case #X: "，X代表测试用例的编号，然后输出一个数ans，代表ans天之后他会停止生长，如果不会停止就输出inf. 具体可参见sample output。
Sample Input 2 5 1 1 10 1 1 1 1 1 5 1 1 500 1 1 1 1 1 Sample Output Case #1: 2 Case #2: 7
这是一哥们编的：
[Java] 纯文本查看 复制代码 import java.io.*;
import java.util.ArrayList;
public class Cat {
public int T;// 测试的数据组数
public int n; // n个器官
public int k1; // 初始系数k1
public int k2;// 初始系数k2
public int k;// 限制体重
public int firstWeight;// 第一天的体重
public int weight;// 体重
ArrayList<String> out = new ArrayList();// 用来装输出结果
public static void main(String[] args) {
Cat cat = new Cat();
cat.input();
cat.output();
}
// 猫第m天的体重
public int catWeight(int m) {
weight = firstWeight;
for (int i = 1; i < m; i++) {
weight = (k1 + k2) * weight;
}
return weight;
}
// 测试猫的体重是否达标
public String testWeight() {
int i = 1;
if (catWeight(1) >= catWeight(2) && catWeight(1) <= k)
return "inf";
else {
while (catWeight(i) <= k) {
i++;
}
if (i == 1)
return ((Integer) i).toString();
else
return ((Integer) (i - 1)).toString();
}
}
// 数据输入和检验
public void input() {
String s;
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
try {
s = br.readLine();
T = Integer.parseInt(s);
if (T <= 0)
System.out.println("测试组数应该大于0");
} catch (IOException e) {
e.printStackTrace();
}
for (int i = 1; i <= T; i++) {
String s1;
String s2;
String s3[];
String s4[];
int b1[] = new int[4];
try {
s1 = br.readLine();
s3 = s1.split(" ");
if (s3.length != 4) {
out.add("第" + i + "组数据第一行的格式不正确");
} else {
for (int j = 0; j < 4; j++) {
b1[j] = Integer.parseInt(s3[j]);
}
n = b1[0];
k1 = b1[1];
k2 = b1[2];
k = b1[3];
firstWeight = 0;
s2 = br.readLine();
s4 = s2.split(" ");
if (s4.length != n) {
out.add("第" + i + "组数据第二行的格式不正确");
} else {
for (int d = 0; d < n; d++) {
firstWeight = Integer.parseInt(s4[d]) + firstWeight;
}
out.add("case #" + i + ':' + testWeight());
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
// 结果输出
public void output() {
for (int i = 0; i < T; i++) {
System.out.println(out.get(i));
}
}
}
| 
发表于 2013-8-12 23:18
腾讯你麻痹啊
