KOI 1차 2021 고2- 초직사각형 > 문제은행 : 정보올림피아드&알고리즘


4729 : 초직사각형

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
25 회   
시도횟수
69 회   

문제

1차원 공간에서의 선분, 

2차원 공간에서의 직사각형, 

3차원 공간에서의 직육면체를 생각해 보자.

 


 

 

선분의 크기는 변수 A로, 

직사각형의 크기는 두 개의 변수 A와 B로, 

직육면체의 크기는 세 개의 변수 A, B, C로 표현할 수 있다.

선분에 길이는 A, 직사각형의 넓이는 A*B, 직육면체의 부피는 A*B*C이다.

 

4차원 공간에 네 개의 변수 A, B, C, D로 크기를 표현할 수 있는 초직사각형이 있다. 

4차원 초직사각형의 부피는 A*B*C*D이다.

 

처음에 변수 A의 값은 A0, 변수 B의 값은 B0, 변수 C의 값은 C0, 변수 D의 값은 D0이다.

이 초직사각형의 크기를 바꿀 수 있는 카드가 N장 있다.

이 중 i(1 ≤ i ≤​ N)번째 카드에는 문자 Ti와 자연수 Ui가 적혀 있다.

TiA, B, C, D중 하나이며, 값을 바꿀 변수의 이름을 의미한다.

i번재 카드를 사용하면, Ti에 해당하는 변수의 값이 Ui만큼 증가한다.

사용한 카드는 즉시 소멸하므로 각각의 카드는 최대 한 번씩만 사용할 수 있다.

 

당신은 4차원 초직사각형의 부피를 최대화하고자 하며, 

이를 위해 주어진 카드 중 정확히 K장을 골라서 원하는 순서대로 사용할 수 있다.

어떤 카드를 순서대로 사용해야 하는지를 구하여 출력하는 프로그램을 작성하라.

 

부피를 최대화하는 사용방법이 여러 가지 있을 경우 그 중 하나만 구하여 출력하면 된다.

 

[제약 조건]

* 주어지는 모든 수는 정수이다.

* 1 ≤​ K ≤​ N ≤​ 200,000

* 1 ≤​​ A0, B0, C0, D0 ≤ 1,000,000​

* 모든 1 ≤​ i ≤​ N​에 대해, Ti​는 ABCD 중 하나이다.

* 모든 1 ≤​ i ≤​ N에 대해, Ui​는​ 1이상 1,000,000 이하의 자연수이다.

 

[부분문제]

1. (8점) 

  * ​N ≤ 10
​  * A0, B0, C0, D0 ≤ 10
  * 모든 1 ≤ i ≤ N에 대해 Ui​ ≤ 10 이다. 

 

2. (6점) ​

  * ​B0 = C0 = D0 = 1
  * 모든 1 ≤ i ≤ N에 대해 Ti 는 A이다. 

 

3. (15점) ​

  * ​​N ≤ 300

  * ​​A0, B0, C0, D0 ≤ 100

  * ​모든 1 ≤ i ≤ N에 대해 Ui​ ≤ 100 이다.

 

4. (21점) ​

  * ​모든 1 ≤ i ≤ N에 대해 Ui​ ≤ 1 이다.

 

5. (20점) ​

  * ​D0 = 1​​ 

  * 모든 1 ≤​ i ≤​ N​에 대해, Ti​는 ABC 중​ 하나이다.
  * 모든 1 ≤​ i ≤​ N에 대해, Ui​ ≤ 10​이다. 

 

6. (30점) : 추가 제약 조건 없음.

 

 


입력형식

첫 번재 줄에 두 개의 정수 N과 K가 공백 하나를 사이로 두고 주어진다.

두 번째 줄에 네 개의 정수 A0, B0, C0, D0​가 공백 하나씩을 사이로 두고 주어진다.

다음 N개의 줄에는 카드들에 대한 정보가 주어진다.
이 중 i( 1 ≤​​ i ≤​​ N)번째 줄에는 Ti​와 Ui​가 공백 하나를 사이로 두고 주어진다.


출력형식

K개의 줄에 선택한 카드들을 사용할 순서대로 입력 형식과 같은 방식으로 한 줄에 한 카드씩 출력한다.


입력 예

4 3
1 1 1 1
A 1
A 1
A 2
A 2

출력 예

A 2
A 1
A 2

입력 예

8 6
1 2 3 4
A 2
A 5
B 7
B 2
C 5
C 9
D 1
D 3

출력 예

A 2
B 7
C 5
A 5
C 9
D 3

데이타 만든사람 : ohjtgood

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP