글 읽기 - 1024 수열의합 질문합니다... 반례 부탁드립니다..

chkwon91 4년 전 0

문제를 푼 알고리즘은 코드 밑에 주석으로 제시해두었습니다.

제 보잘것없는 수학 지식과 직관으로 만들었기 때문에 이러이러해서 이렇다고 명료하게 증명하기는 어렵습니다

제가 직접 몇가지 값들을 대입해보면 값이 잘 나오는데

제출하면 계속 틀렸다 나오네요....

반례를 부탁드립니다...

											#include<stdio.h>
#include<math.h>

int main()
{
	long long int i, j;
	long long int start, end, sum, temp, middle;
	long long int goal, length;

	scanf("%lld %lld", &goal, &length);

    
    
    /*length가 홀수인 경우는 goal값과 나누어 떨어지면 같은 결과값을 가질수있고, 
    length가 짝수이면 나머지 값이 length/2와 같을때 같은 결과값을 가질수 있다*/
	while(length<=100&&(length*(length+1)/2)<=goal)
	{
		if(length%2==1)/*홀수인 경우*/
		{
			if(goal%length==0)
			{middle=goal/length; end=middle+length/2; start=middle-length/2;
			printf("%lld",start);
			for(j=start+1; j!=end+1; j++)	{printf(" %lld", j);}printf("\n");
			return 0;}
		}
		else		/*짝수인 경우*/
		{
			if(goal%length==length/2)
			{middle=goal/length; end=middle+length/2; start=end-length+1;
			printf("%lld",start);
			for(j=start+1; j!=end+1; j++)	{printf(" %lld", j);}printf("\n");
			return 0;}
		}

		length++;
	}
	printf("-1\n");
	return 0;
}
										

RiKang 4년 전 1

문제에선 음이 아닌 정수들의 리스트라고 했는데 자연수들의 리스트로 푸신듯 하네요. 3 3 -> 0 1 2

chkwon91 4년 전 0

@RiKang 3 3 경우는 while의 조건문인 length*(length+1)/2<=goal의 조건에 맞지 않아 미리 제외 되도록 했습니다...

다른 반례가 필요한것 같아요.. 감사합니다.

baekjoon 4년 전 1

@Rikang의 반례가 맞는 것 같습니다.

음이 아닌 정수이기 때문에, 0으로 시작하는 결과가 나올 수 있습니다.

length*(length+1)/2 를 length*(length-1)/2로 고쳐야 할 것 같습니다.

chkwon91 4년 전 0

@Rikang @baekjoon 아... 고맙습니다. 음이아닌 정수라는 조건을 놓쳤네요.. Rikang님의 답변을 좀 더 유의깊게 들었어야 했는데

두분 덕분에 문제를 풀었네요 고맙습니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ACM-ICPC

1024 수열의합 질문합니다... 반례 부탁드립니다..

chkwon91 4년 전 0

RiKang 4년 전 1

chkwon91 4년 전 0

baekjoon 4년 전 1

chkwon91 4년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태