GREEDYAINTA

AOJ GREEDYAINTA

SOL)
i번째가 가지고 있는 사탕의 수가 앞의 인원의 수의 배수가 안되면 IMPOSSIBLE
매번 0 ~ i-1까지 값을 더해주면 시간초과 이므로 sum이라는 변수에 원래 더해 줘야하는
값을 가지고 있는다.
사탕의 수는 10^9까지 들어오기 때문에 long long 타입을 사용한다.

[-] Collapse

#include<cstdio>
long long arr[100000];
int main(){
    int t; scanf("%d", &t);
    while (t--){
        long long n, i, sum = 0; scanf("%lld", &n);
        for (i = 0; i < n; i++) scanf("%lld", &arr[i]);
        for (i = n-1; i > 1; i--){
            if ((arr[i] + sum) % i == 0) sum += (arr[i] + sum) / i;
            else break;
        }
        puts(i == 1 ? "POSSIBLE" : "IMPOSSIBLE");
    }
}