[2021 SCPC 1차 예선]
차이
개의 변수 이 있다. 처음에는 들의 값에 대한 어떤 정보도 가지고 있지 않다. 개의 명령이 주어지는데, 명령은 두가지 종류이다. 첫번째 종류는 두 변수의 차이를 알려주는 것이다. 즉, 라는 정보를 준다. 라는 정보도 주어진 것으로 간주한다. 두번째 종류는 두 변수의 차이를 묻는 것이다. 명령들은 하나하나 순서대로 주어지는 것으로 생각한다.
두번째 종류의 명령에 대한 대답은 다음의 3가지가 있다.
- 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이가 유일하게 정해지면 그 값을 출력해야 한다.
- 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 방법이 전혀 없다면 NC를 출력한다. NC의 의미는 Not Connected이다.
- 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 수 있지만 하나로 정하는 것이 불가능하다면 CF를 출력한다. CF의 의미는 Conflict이다.
위의 조건을 자세히 설명하면 다음과 같다: 두번째 종류의 명령에서 주어진 두 변수를 와 라고 하자. 에서 로의 연결은 변수의 열인데, 처음이 이고 마지막이 이며 열에서 인접한 모든 쌍이 그 시점까지 첫번째 종류의 명령으로 주어진 것이라야 한다. 인접한 쌍이 첫번째 종류의 명령에서 등장한 순서대로일 필요는 없다. 에서 로의 연결은 여러 개가 존재할 수 있음에 주의하라. 에서 로의 연결을 따라 계산한다는 것은 다음과 같이 정의된다. 가 연결이라고 하자. 의 값에 대한 정보가 여러 번 주어진 경우 어떤 것이든 사용할 수 있다. 동일한 연결에 대해서도 계산의 결과는 여러가지일 수가 있다. 선택한 정보가 라면 의 차이가 최초로 누적된다. 이후 에 도달할 때까지 동일한 방식으로 차이를 누적한다. 동일한 연결에 대해서도 계산의 결과는 여러가지일 수가 있음에 주의하라.
에서 로의 가능한 모든 연결에 따라 와 의 차이의 모든 가능한 경우를 계산했을 때 전부 동일한 값이 나온다면 위의 첫번째 경우에 해당한다. 와 의 가능한 연결이 존재하지 않는 경우 위의 두번째 경우에 해당한다. 와 의 가능한 연결들을 이용해 와 의 차이를 계산했을 때 그 결과가 여러가지라면 위의 세번째 경우에 해당한다.
아래 입출력 예의 경우를 보자 입력은 아래와 같다.
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1
첫 줄의 “1”은 테스트 케이스의 개수이다. 테스트케이스의 첫번째 줄의 “5 9”는 변수가 5개 있으며 명령이 9개 있다는 뜻이다. 다음 줄의 “1 2 3 2”는 첫번째 종류의 명령이며 라는 정보를 준다. 그 다음 줄은 라는 정보를 준다. 두 정보는 동일한 것임을 알 수 있다. 다음 줄의 “2 2 3”은 에 대한 명령이다. 에서 로의 연결의 예는 등이 있다. 모든 연결에서 계산한 값이 2로 동일함을 알 수 있다. 따라서 이 명령에 대한 답은 2이다. 다음 줄은 이라는 정보를 준다. 다음 명령은 “2 2 3”이다. 에서 로의 가능한 연결인 에 대해 라는 정보를 사용한 계산과 (동등하게 이라는 정보를 사용한 계산의 결과가 서로 다르므로 이 명령에 대한 답은 CF이다. 다음 명령인 “2 5 2”의 경우 에서 로의 가능한 연결이 없으므로 답은 NC이다. 마지막 명령의 답은 -15이다.
위와 같이 정해진 명령들을 처리하는 프로그램을 작성하시오.
- 제한시간: 전체 테스트 케이스는 35개 이하이며, 전체 수행 시간은 5초 이내. (Java 8초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다. ※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
- 제출 제한 : 최대 10회 (참고: 동점자의 경우 최고 점수에 도달한 시간에 제출 횟수 한번마다 7분의 지연을 부가하여 시간을 계산하고 이 시간이 빠른 순서대로 등수를 결정함)
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,
이후 차례로 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 변수의 개수 과 명령의 개수 가 주어진다.
둘째 줄부터 개의 각 줄에는 명령이 하나씩 주어진다. 명령의 첫 수가 1인 경우 차이를 알려주는 것이다. “1 i j d”와 같이 주어진 경우 라는 의미이다. 동일한 쌍의 변수에 대해 여러 개의 1번 종류 명령이 주어질 수 있다. 명령의 첫 수가 2인 경우 차이를 묻는 것이다. 즉, “2 i j”와 같이 주어진 경우 를 묻는 것이다. 두 종류 모두 i와 j가 같을 수도 있다. d의 절대값은 10,000 이하이다.
- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 200 점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (31 점) : 이 그룹의 테스트 케이스에서는 이다. 모든 1번 종류 쿼리에서 차이 값은 0이다.
ㆍ 그룹 2 (28 점) : 이 그룹의 테스트 케이스에서는 이다.
ㆍ 그룹 3 (20 점) : 이 그룹의 테스트 케이스에서는 모든 1번 종류 쿼리에서 차이 값은 0이다.
ㆍ 그룹 4 (121 점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
- 모든 테스트 케이스를 풀지 않고 일부분의 그룹에 속하는 테스트 케이스만을 푸는 경우에도 입력 받은 모든 케이스에 대해 (답이 틀릴지라도) 출력 양식에는 맞는 출력을 생성해야 점수가 반영되는 것이 보장된다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #”를 출력하여야 한다. 이때 는 테스트 케이스의 번호이다.
그 다음 줄부터 각 쿼리에 대한 답을 한 줄에 출력한다.
입출력예
| 입력 |
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1 |
돌아가기