HDOJ 4525 위 웨 이 고양이 닭 다리 먹 기

위 웨 이 고양이 시리즈 - 닭 다리 먹 기
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 3003    Accepted Submission(s): 610
Problem Description
웨 이 고양 이 는 보통 고양이 가 아니 라 보통 고양 이 는 생선 을 좋아 하지만 웨 이 고양 이 는 닭 다 리 를 가장 좋아한다.그 는 매일 쉬 지 않 고 닭 다 리 를 먹었다.지금 그 는 어 려 운 문제 에 부 딪 혔 다. 만약 그의 체중 이 너무 뚱뚱 하 다 면 그의 주인 은 그 에 게 닭 다 리 를 먹 이지 않 을 것 이다. 그래서 그 는 너의 도움 이 필요 하 다.
웨 이 고양이 의 몸 은 n 개의 기관 으로 구성 되 어 있 으 며, 그의 몸 은 매우 특수 하기 때문에 그의 성장 도 매우 특수 하 다.그의 성장 은 k1 과 k2 계수 가 있 고 매일 성 장 량 은 전날 과 관련 이 있다. 우 리 는 이 n 개 기관 이 i 일 째 의 수치 가 각각 a (i, 1), a (i, 2), a (i, 3) 라 고 가정 하면 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
   
   
   
   

 
이 문 제 는 간소화 해 야 합 니 다. 사실은 매번 의 곱 하기 (k1 + k2) 입 니 다.
a1*k1+a1*k2+a2*k1+a2*k2.....=sum*（k1+k2);
k1 + k2 가 발산 되 어야 k 에 도달 할 수 있 고 수렴 된다 면 점점 작 아 질 수 밖 에 없다 는 점 을 고려 해 야 한다.
그래서 k1 + k2 > 1 또는 k1 + k2 < - 1 시 발산 되 어 도달 할 수 있 습 니 다.
특수 상황 에 주의 하여 처음부터 K 에 이 르 렀 다.
AC CODE

#include <stdio.h>
 int main(){ int t, T, n, i; double k1, k2, k, sum; int a[10010];

    scanf("%d", &T); for (t = 1; t <= T; t++){
        scanf("%d%lf%lf%lf", &n, &k1, &k2, &k);
        sum = 0; for (i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            sum = sum + a[i]; } if (sum > k){
            printf("Case #%d: 0
",t); continue; } if ((k1 + k2 <= 1) && (k1 + k2 >= -1)){
            printf("Case #%d: inf
", t); continue; } int ans = 0; while (1){
            ans++;
            sum = sum * (k1 + k2); if (sum > k) break; }
        printf("Case #%d: %d
", t, ans); } return 0; }