FESTIVAL

https://www.algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

선형시간에 해결은 힘들고 O(n^2)에 해결했다.

 

Trouble Shooting

1. MIN값을 전역변수로 두고 초기화작업이 누락되어 오답처리됨

2. 예외 케이스 중에 <333 4 111111> 인 경우

첫 번째, 알고리즘에서 3 < 4 이므로 for문을 종료했는데 모든 index를 더한다면 19/10 = 1.9 이다.

두 번째, 수정 알고리즘에서는 index마다 last까지 for루프안의 값을 MIN에 업데이트함으로써 해결했다.

 

 

#include<stdio.h>
void check(double N_A [], int start, int last, double val, int index, double *MIN)
{
	int i;
	if (*MIN > val) *MIN = val;
	for (i = start; i < last; i++){
		val = (val * index + N_A[i]);
		val /= ++index;
		if (*MIN > val) *MIN = val;
	}
}
int main(){
	int CASE;
	for (scanf("%d", &CASE); CASE > 0; CASE--)
	{
		int i;
		double N_A[1001];
		double VAL = 0, MIN = 999;
		int N, L;

		scanf("%d %d", &N, &L);
		for (i = 0; i < N; i++)
			scanf("%lf", &N_A[i]);

		for (i = 0; i < L; i++)
			VAL += N_A[i];	// first 0~N HAP

		check(N_A, L, N, VAL / L, L, &MIN);

		for (i = 0; i < N - L; i++){
			VAL += N_A[i + L] - N_A[i];
			check(N_A, i + L + 1, N, VAL / L, L, &MIN);
		}

		printf("%.12lf\n", MIN);
	}
	return 0;
}