5037: 야구 시즌
[만든사람 : CodingPanda-admin 2024/01/15]
문제 설명
KOI 야구 리그에는 N개의 지역리그가 존재하고 각 지역리그에는 M개의 팀이 존재해서, 리그 전체로는
N × M개의 팀으로 운영되고 있다
.
한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 A로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 같은 지역리그에 있는 모든 팀 Y (6= X)와 각각 A번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 B로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 다른 지역리그에 있는 모든 팀 Z(6= X)와 각각 B 번의 경기를 한다. 단, A와 B는 A = k × B (k는 1 이상의 정수)를 만족해야 한다.
세계적 판데믹의 영향으로 올해 KOI 야구 리그는 시즌을 단축하여, 리그의 전체 경기 수가 D개 이하 이면 서 D에 가장 가깝게 되도록 정하기로 했다. 따라서 같은 지역리그 팀과의 팀당 경기 수 A와 다른 지역리그 팀과의 팀당 경기 수 B를 새롭게 결정해야 한다. 물론, A = k×B를 만족해야 하고, k는 변함없이 유지되어야 한다. 또한 각 팀은 다른 팀과 적어도 한 번이상은 경기를 해야 한다. 다시 말해서, A ≥ 1, B ≥ 1을 만족해야 한다.
예를 들어, N = 2, M = 3, k = 3일 때, 경기 수 제한 D = 60이면, A = 6, B = 2일 때, 다른 지역리그 팀들과의 총 경기 수는 18이고, 같은 지역리그 팀들과의 총 경기 수는 36이다. 따라서 리그 전체 경기 수는 54로 D에 가장 가까운 새로운 경기 수이다.
지역리그의 개수 N, 각 지역리그에 속하는 팀 수 M, 그리고 위에서 A = k × B를 만족하는 정수 k, 새로 운 경기 수 제한 D가 주어질 때, D 이하이면서 D에 가장 가까운 리그 전체 경기 수를 계산해서 출력하는 프로그램을 작성하시오.
.
한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 A로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 같은 지역리그에 있는 모든 팀 Y (6= X)와 각각 A번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 B로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 다른 지역리그에 있는 모든 팀 Z(6= X)와 각각 B 번의 경기를 한다. 단, A와 B는 A = k × B (k는 1 이상의 정수)를 만족해야 한다.
세계적 판데믹의 영향으로 올해 KOI 야구 리그는 시즌을 단축하여, 리그의 전체 경기 수가 D개 이하 이면 서 D에 가장 가깝게 되도록 정하기로 했다. 따라서 같은 지역리그 팀과의 팀당 경기 수 A와 다른 지역리그 팀과의 팀당 경기 수 B를 새롭게 결정해야 한다. 물론, A = k×B를 만족해야 하고, k는 변함없이 유지되어야 한다. 또한 각 팀은 다른 팀과 적어도 한 번이상은 경기를 해야 한다. 다시 말해서, A ≥ 1, B ≥ 1을 만족해야 한다.
예를 들어, N = 2, M = 3, k = 3일 때, 경기 수 제한 D = 60이면, A = 6, B = 2일 때, 다른 지역리그 팀들과의 총 경기 수는 18이고, 같은 지역리그 팀들과의 총 경기 수는 36이다. 따라서 리그 전체 경기 수는 54로 D에 가장 가까운 새로운 경기 수이다.
지역리그의 개수 N, 각 지역리그에 속하는 팀 수 M, 그리고 위에서 A = k × B를 만족하는 정수 k, 새로 운 경기 수 제한 D가 주어질 때, D 이하이면서 D에 가장 가까운 리그 전체 경기 수를 계산해서 출력하는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
다음 T개의 줄에 각 테스트 케이스의 정보가 한 줄에 하나씩 주어진다.
각 테스트 케이스는 하나의 줄에 네 개의 정수 N, M, k, D가 공백 하나를 사이로 두고 주어진다.
• 주어지는 모든 수는 정수이다.
• 하나의 입력 데이터에서 1개 이상 1 000개 이하의 테스트 케이스를 해결해야 한다.
• 2 ≤ N, M ≤ 100
• 1 ≤ k ≤ 100
• 1 ≤ D ≤ 1 000 000 000
(테스트 케이스 비율)
1. (5%) N = 2
2. (5%) M = 2
3. (5%) k = 1
4. (85%) 추가 제약 조건 없음
다음 T개의 줄에 각 테스트 케이스의 정보가 한 줄에 하나씩 주어진다.
각 테스트 케이스는 하나의 줄에 네 개의 정수 N, M, k, D가 공백 하나를 사이로 두고 주어진다.
• 주어지는 모든 수는 정수이다.
• 하나의 입력 데이터에서 1개 이상 1 000개 이하의 테스트 케이스를 해결해야 한다.
• 2 ≤ N, M ≤ 100
• 1 ≤ k ≤ 100
• 1 ≤ D ≤ 1 000 000 000
(테스트 케이스 비율)
1. (5%) N = 2
2. (5%) M = 2
3. (5%) k = 1
4. (85%) 추가 제약 조건 없음
출력 설명
T개의 각 줄에 각 테스트 케이스에 대해 리그 전체 경기 수를 출력한다.
만약 조건을 만족하는 경기 수가 존재하지 않으면 -1을 출력한다.
만약 조건을 만족하는 경기 수가 존재하지 않으면 -1을 출력한다.
입력 예시 Copy
3
2 3 3 60
2 2 1 18
2 2 1 4
출력 예시 Copy
54
18
-1