글 읽기 - 반례가 뭐가 있을까요

(追記) (追記ここまで)

반례가 뭐가 있을까요

15956번 - 숏코딩

hun3555 3년 전 0

게시판에 있는 반례들 다 넣어봤는데 문제가 없는거 같은데 20퍼에서 계속 틀리네요

들어오는 논리식을 && 단위로 구분한 다음

==인 식들에 대해서는 union-find로 합쳐줬고

!=인 식들은 나중에 처리하려고 저장했습니다

==인 식을 다 처리한 후에는 같은 단항식들을 전부 모은 다음

해당 단항식들 중 길이가 가장 짧은 것, 그리고 만일 있다면 해당 단항식들의 값을 찾아서 == 관계를 전부 찾아주었고

(이 과정 중 정수가 두번 나오면 항상 거짓인 논리식이니 1==0을 출력하고 종료)

이후 !=인 식들을 해당 길이가 가장 짧은 단항식으로 바꿔서 처리했습니다

만일 !=로 연결된 두 값이 서로 같거나 ==로 연결된 두 값이 서로 다르면 1==0을 출력하였고

!=인 식들을 처리할 때도 해당 식이 처리되었는지 여부를 acted라는 set에 이들을 구분할 값을 집어넣어서 처리했습니다

만일 모든 식을 처리하고 나서 처리한 식 목록이 비었을 경우 1==1을 출력하였습니다

코드가 난잡하지만 게시판에서 확인한 반례들은 다 넣어보았고 제대로 출력되는거 같은데

뭐가 문제일까요

import sys
input = sys.stdin.readline
def find(s):
 if p[s] == None:
 return s
 p[s] = find(p[s])
 return p[s]
def merge(s1, s2):
 s1 = find(s1)
 s2 = find(s2)
 
 if s1 == s2:
 return
 p[s1] = s2
def init(a, b):
 if "0" <= a[-1] <= "9":
 a = int(a)
 if "0" <= b[-1] <= "9":
 b = int(b)
 
 if a not in p:
 p[a] = None
 if b not in p:
 p[b] = None
 
 return a, b
def add_equiv(a, b):
 global fail
 
 if type(a) == int and type(b) == int:
 if a != b:
 fail = True
 return
 
 merge(a, b)
def intlen(n):
 if n < 0:
 res = 2
 n *= -1
 else:
 res = 1
 while n >= 10:
 n //= 10
 res += 1
 
 return res
def length(v):
 if type(v) == int:
 return intlen(v)
 return len(v)
def actkey(par1, par2):
 if type(par1) == int:
 if type(par2) == int:
 if par1 > par2:
 par1, par2 = par2, par1
 return f"{par1}{par2}"
 return f"{par1}{par2}"
 if type(par2) == int:
 return f"{par2}{par1}"
 if par1 > par2:
 par1, par2 = par2, par1
 return f"{par1}{par2}"
def add_nonequiv(a, b):
 global fail
 
 if type(a) == int and type(b) == int:
 if a == b:
 fail = True
 return
 
 nonequiv.append((a, b))
if __name__ == "__main__":
 s = input().strip().split("&&")
 
 p = dict()
 nonequiv = []
 fail = False
 
 for term in s:
 v = term.split("=")
 if len(v) == 3:
 a = v[0]
 b = v[2]
 a, b = init(a, b)
 add_equiv(a, b)
 else:
 a = v[0][:-1]
 b = v[1]
 a, b = init(a, b)
 add_nonequiv(a, b)
 
 if fail:
 break
 
 if fail:
 print("1==0")
 
 else:
 equiv_vals = dict()
 
 for v in p.keys():
 par = find(v)
 
 if par not in equiv_vals:
 equiv_vals[par] = [v]
 else:
 equiv_vals[par].append(v)
 
 key_terms = dict()
 final_terms = []
 
 for par in equiv_vals.keys():
 exist_int = False
 
 for v in equiv_vals[par]:
 if par not in key_terms:
 key_terms[par] = [v, None] # shortest, true value
 else:
 l = length(v)
 
 if length(key_terms[par][0]) > l:
 key_terms[par][0] = v
 
 if type(v) == int:
 if exist_int:
 fail = True
 break
 exist_int = True
 key_terms[par][1] = v
 
 if fail:
 break
 
 if len(equiv_vals[par]) == 1:
 continue
 elif len(equiv_vals[par]) == 2:
 final_terms.append(f"{equiv_vals[par][0]}=={equiv_vals[par][1]}")
 else:
 term = []
 for v in equiv_vals[par]:
 if v != key_terms[par][0]:
 final_terms.append(f"{v}=={key_terms[par][0]}")
 
 if fail:
 print("1==0")
 
 else:
 acted = set()
 
 for a, b in nonequiv:
 par1 = find(a)
 par2 = find(b)
 
 key = actkey(par1, par2)
 if key in acted:
 continue
 
 acted.add(key)
 
 if par1 == par2:
 fail = True
 break
 
 if key_terms[par1][1] is not None and key_terms[par2][1] is not None:
 if key_terms[par1][1] != key_terms[par2][1]:
 continue
 else:
 fail = True
 break
 
 final_terms.append(f"{key_terms[par1][0]}!={key_terms[par2][0]}")
 
 if fail:
 print("1==0")
 else:
 if len(final_terms) > 0:
 print("&&".join(final_terms))
 else:
 print("1==1")

ediya 3년 전 0

반례드립니다.

INPUT : ab==cde&&abc==de&&a!=bcde&&abcd!=e

WA : ab==cde&&abc==de&&a!=bcde

ANS : abc==de&&cde==ab&&e!=abcd&&bcde!=a

!= 처리할때 key방식을 다시 짜면 통과 할 것 같습니당

저도 이문제 푸느라 되게 고생 많이했는데 도움이 됐으면 좋겠네요!

hun3555 3년 전 0

감사합니다

!= 처리할때 문제가 있는걸 알고 뒤늦게 key 방식을 추가하다가 잘못 짰네요

고쳐봐야겠네요

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)