글 읽기 - 다른 반례가 있는지 도와주세요!

2015112119 5년 전 0

일단 먼저 제가 실행해 보았던 반례입니다. 정답인 코드와 비교하여 정답이 나왔습니다.

1 5 1

1 1 1

134 23 812741700

50 6 3478761

117 23 522390800

87 65 52238750

200 200 753387060

다른 반례가 있거나 제가 모르는 것이 있으면 알려주세요!

#include <iostream>
#include <string.h>
using namespace std;

int main() {
	long long n, k, dp[100000], sum=0, check=0, temp=0, temp2=0;
	memset(dp, -1, sizeof(dp));

	cin >> n >> k;

	if (k == 1) cout << 1;
	else {
		for (int i = 2; i <= k; i++) {
			check = sum;
			sum = 0;
			for (int j = 0; j <= n; j++) {
				if (i == 2) {
					dp[j] = 1;
					sum += dp[j];
				}
				else {
					if (j == 0) {
						temp = dp[0];//21
						dp[0] = check;//220
						sum += dp[0];
					}
					else {
						temp2 = temp;//21
						temp = dp[j];//20
						dp[j] = dp[j - 1] - temp2;
						sum += dp[j];
					}
					dp[j] %= 1000000000;
					sum %= 1000000000;
				}
			}
		}
		cout << sum;
	}
}

arcane1028 4년 전 3

틀린 반례가 있어서 댓글 남깁니다.

1 5 인 경우 답이 5가 나와야 합니다.

0 0 0 0 1

0 0 0 1 0

0 0 1 0 0

0 1 0 0 0

1 0 0 0 0

이렇게 0이 중복되는 경우도 하셔야 합니다.

roigh12 4년 전 0

작성자님 혹시 acm-icpc 같이 나가실 의향 잇으시면 roigh@naver.com로 연락좀 부탁드려요.

roigh12 4년 전 0

010-5039-4015로 연락부탁드려요.

483759 3년 전 0

늦게 보시는 분들을 위해 말하자면 위의 반례 중

87 65

의 답은

522380750

입니다

embrapers263 3년 전 0

87 65의 답은 492701981 아닌가요?

제 코드 통과했는데 이 결과가 나왔습니다.

fbfbf1 3년 전 0

제 코드도 통과 됐는데

87 65 넣으면

522380750로 나옵니다.

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

문제

문제

출처

ICPC

다른 반례가 있는지 도와주세요!

2015112119 5년 전 0

arcane1028 4년 전 3

roigh12 4년 전 0

roigh12 4년 전 0

483759 3년 전 0

embrapers263 3년 전 0

fbfbf1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말