28344번 - rograms 초등학교
안녕하세요. 질문 게시판에서 검색해 보았으나 같은 내용의 글/반례를 찾지 못해 문의드립니다.
문제 설명에는 보물 가치 TiT_iTi에 대해 별도의 “서로 다름” 조건이 없고(중복 가능해 보임), 또 “항상 정답이 존재하는 입력만 주어진다”고 되어 있습니다.
그런데 중복이 허용되는 경우, UCPC 원문(Programs 초등학교)에서 알려진 구성 방식(정렬 후 역순으로 리더 변화면 큰 값 / 유지면 작은 값 선택 등)과 같은 유형의 구성은 일반적으로 성립하지 않는 것으로 보입니다.
아래 입력은 문제 조건을 만족하며(정답이 존재), 실제로 정답 예시가 있습니다.
입력:
1 3 3 3 4 1 1 2
가능한 정답 출력 예:
4 1 3 2 3 2
(누적합을 계산해 보면 리더가 1 → 1 → 2가 되며, 중간 동점도 없습니다.)
따라서,
TiT_iTi가 항상 서로 다른 값이라는 조건이 누락된 것인지, 또는
중복이 허용되는 것이 맞다면 “항상 정답 존재”를 보장하는 추가 제약/데이터 조건이 따로 있는지
확인 부탁드립니다. 필요하다면 조건 보완/데이터 점검 및 리저지도 요청드립니다.
감사합니다.
댓글을 작성하려면 로그인해야 합니다.
qnffidfhqht 10달 전
안녕하세요. 질문 게시판에서 검색해 보았으나 같은 내용의 글/반례를 찾지 못해 문의드립니다.
문제 설명에는 보물 가치 TiT_iTi에 대해 별도의 “서로 다름” 조건이 없고(중복 가능해 보임),
또 “항상 정답이 존재하는 입력만 주어진다”고 되어 있습니다.
그런데 중복이 허용되는 경우, UCPC 원문(Programs 초등학교)에서 알려진 구성 방식(정렬 후 역순으로 리더 변화면 큰 값 / 유지면 작은 값 선택 등)과 같은 유형의 구성은 일반적으로 성립하지 않는 것으로 보입니다.
아래 입력은 문제 조건을 만족하며(정답이 존재), 실제로 정답 예시가 있습니다.
반례 (정답 존재)
입력:
가능한 정답 출력 예:
(누적합을 계산해 보면 리더가 1 → 1 → 2가 되며, 중간 동점도 없습니다.)
따라서,
TiT_iTi가 항상 서로 다른 값이라는 조건이 누락된 것인지, 또는
중복이 허용되는 것이 맞다면 “항상 정답 존재”를 보장하는 추가 제약/데이터 조건이 따로 있는지
확인 부탁드립니다. 필요하다면 조건 보완/데이터 점검 및 리저지도 요청드립니다.
감사합니다.