vvv3334   2년 전

바이너리 서치를 통해서 각자의 문자열을 hashing 한 후, 라빈 카프 알고리즘을 이용하여 문제를 풀었습니다.

그런데 mod를 할 때, 100010은 답이 나오고 100011로 나누면 답이 틀립니다.

문제의 특정상 정답 이하의 수는 check 함수를 호출 할때 1이 나와야 하는데 디버깅을 해보면, 답이 불연속적으로 나옵니다.

그외 특정 수(#define TEST)는 답이 되고 특정 수는 답이 안되게 됩니다.

로직 상 TEST에 어떤 값이 들어가도 답이 돼야 할 것 같은데...

뭐가 문제일까요? ㅠㅠ


(아래는 테스트 케이스입니다. 정답은 526이 나와야 합니다.)

6955 bcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbdbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaacbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbababcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddabcbcdbbabcbbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaaddbbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcbcbcdbbabcbabbcdbbbbcbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadbcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacbabcbcdbbabcbabcbcdbbabcbabbcdbbbbcdbbbdcddacbcdaaadddbbbaabacb

leehosu01   2년 전

아마 숫자가 안좋기 때문일것 같습니다.

소수를 사용하는것이 더 나을 것 같습니다

vvv3334   2년 전

숫자가 안좋아도 답은 나오지 않나요? 

leehosu01   2년 전

나오겠죠? RTE나 TLE 만 아니라면 출력을 할테니까요

vvv3334   2년 전

디버깅 해보면 답이 안나옵니다 TLE나 RTE 문제가 아닙니다 ㅠㅠ

leehosu01   2년 전

저는 잘 나오는것 같습니다. https://ideone.com/g5WdRe

혹시 출력이 없다는 것 이었던건가요?

jangzzang   1년 전

와.. 이거 저도 그래요....

미치겠네요 혹시 해결하셨나요? 왜 어떤 MOD연산은 되고 어떤 MOD는 안되고 ㅠㅠ

그냥 틀렸습니다가 뜨니까 뭐 답이없네요 ..

jangzzang   1년 전

원래 해시테이블 만들때 MOD를 무조건 소수로 잡긴했었는데, 이번 문제에서는 그냥 아무 숫자나 잡았었거든요,

그거 문제인가 싶기도하다가도 아닌게,  중복되는 해시값을(HASH+KEY)%MOD  로 선형적으로 찾아서 다시 해싱해

줬는데,  시간초과가 났으면 났지 왜 자꾸 틀렸습니다가 뜨는지 모르겠네요 ㅠ

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