prac 1104

[javelinsman]

No description provided.

[javelinsman]

Practice 1104 #1

이 문제는 테스트케이스가 여러 개의 소문제로 구성되어 있습니다. 문제의 일부분만 풀어도 부분점수를 얻을 수 있습니다. 이번 문제에서는 Adam Grant의 Give & Take의 상황을 시뮬레이션 하는 것이 목표입니다. 총 N명의 사람들로 이루어진 세계에서 1:1의 상호작용이 여러 번 발생하는데, 각 사람마다 전략이 다릅니다. 구체적인 내용은 아래의 문제들을 참조하세요. Class를 사용하여 문제를 해결하기를 적극적으로 권장합니다.

Subproblem 1. Giver & Taker (40pts)

이 문제에서 등장하는 사람은 모두 Giver 혹은 Taker입니다. 예를 들어 5명이 있다고 하면 아래와 같이 한 줄에 입력이 주어집니다.

GGTGT

각 사람은 왼쪽부터 순서대로 id를 0부터 N-1까지 가지게 됩니다. 즉, 위의 상황은 0번 사람이 Giver, 1번 사람이 Giver, 2번 사람이 Taker, 3번 사람이 Giver, 4번 사람이 Taker인 상황을 나타냅니다. 같은 Giver(혹은 Taker)라도 id가 다르면 다른 사람입니다. 이후로는 여러 줄에 걸쳐 어떤 사람들이 상호작용하는지가 주어집니다. 각 줄은 1:1 상호작용을 하는 사람 두명의 id를 나타냅니다. 예를 들면 다음과 같습니다.

0 1
0 2
2 4
done

이는 총 3번의 1:1 상호작용이 있는데, 첫 번째 상호작용은 0번 사람과 1번 사람이, 두 번째 상호작용은 0번 사람과 2번 사람이, 세 번째 상호작용은 2번 사람과 4번 사람이 한다는 것을 의미합니다. 입력은 "done"이라는 sentinel이 주어지기 전까지 계속 받아야 합니다.

각 상호작용마다 두 명의 사람은 각자 give와 take라는 두 가지 옵션 중 무엇을 할 지를 결정해야 합니다. 각 사람이 무엇을 선택했는지에 따라 다음과 같이 score를 얻게 됩니다. 모든 사람의 초기 score는 0입니다.

사람 A	사람 B	결과
give	give	둘 다 2점씩 얻는다
give	take	A는 1점을 잃고, B는 3점을 얻는다
take	give	A는 3점을 얻고, B는 1점을 잃는다
take	take	둘 다 점수 변화가 없다

이 소문제에서는 Giver와 Taker밖에 없다는 것을 다시 떠올리세요. Giver는 무조건 give라는 선택만 취하고, Taker는 무조건 take라는 선택만 취합니다. 따라서 위에 주어진 것과 같이 상호작용을 한다면 다음과 같은 결과가 나옵니다.

1. 0번 사람(Giver)과 1번 사람(Giver)가 서로 give하여 2점씩 얻습니다. (사람 별 점수: 2 2 0 0 0)
2. 0번 사람(Giver)과 2번 사람(Taker)가 각각 give, take하여 0번 사람은 1점을 잃고, 2번 사람은 3점을 얻습니다. (사람 별 점수: 1 2 3 0 0)
3. 2번 사람(Taker)과 4번 사람(Taker)가 서로 take하여 점수 변화가 없습니다. (사람 별 점수: 1 2 3 0 0)

프로그램은 최종 결과를 다음과 같이 각 사람의 id, type, score를 포함해서 출력해야 합니다. 이때, 점수에 따라 내림차순으로 정렬하고, 점수가 같은 사람끼리는 id에 따라 오름차순으로 정렬하여 출력해주세요.

2: Taker (3pts)
1: Giver (2pts)
0: Giver (1pts)
3: Giver (0pts)
4: Taker (0pts)

다음은 문제의 전체 input과 output을 나타낸 것입니다. 나머지는 모두 지금까지 설명한 것과 같으며, 2번째 줄은 이후 소문제를 위한 것으로 여기서는 무시해도 됩니다.

Input

GGTGT
0 0 0 0 0
0 1
0 2
2 4
done

Output

2: Taker (3pts)
1: Giver (2pts)
0: Giver (1pts)
3: Giver (0pts)
4: Taker (0pts)

Subproblem 2. Matcher (30pts)

이 소문제에서는 Matcher라는 타입이 추가됩니다. Matcher는 각 사람별로 그 사람이 직전에 한 행동이 무엇인지를 기억하고 있습니다. Matcher는 상호작용을 할 때 처음 보는 사람에게는 give하지만, 아는 사람에게는 그 사람이 직전에 한 행동을 그대로 돌려줍니다. 다음과 같은 상황을 봅시다.

MGT
0 0 0
0 1
0 2
0 1
0 2

1. 0번 사람(Matcher)과 1번 사람(Giver)가 상호작용합니다. 0번은 1번을 처음 보기 때문에 give합니다. 모두 give를 내고 2점씩 얻습니다. (점수: 2 2 0)
2. 0번 사람(Matcher)과 2번 사람(Taker)가 상호작용합니다. 0번은 2번을 처음 보기 때문에 give합니다. 각각 give, take하여 -1점, 3점을 얻습니다. (점수: 1 2 3)
3. 0번 사람(Matcher)과 1번 사람(Giver)가 상호작용합니다. 0번은 1번이 직전에 give했다는 걸 기억하고 있기 때문에 이번에도 give합니다. 모두 give를 내고 2점씩 얻습니다. (점수: 3 4 3)
4. 0번 사람(Matcher)과 2번 사람(Taker)가 상호작용합니다. 0번은 2번이 직전에 take했다는 걸 기억하고 있기 때문에 take를 냅니다. 모두 take를 내고 점수 변화가 없습니다. (점수: 3 4 3)

Matcher는 어떤 사람이 직전에 한 행동을 그대로 돌려준다는 것을 명심하세요. 이 소문제까지는 그럴 일이 없지만, 어떤 사람들이 matcher에게 give도 했다가 take도 했다가 한다면, matcher도 똑같이 따라서 그 사람의 직전 행동에 따라 give를 주거나 take를 주거나 할 것입니다.

Input

MGT
0 0 0
0 1
0 2
0 1
0 2
done

Output

1: Giver (4pts)
0: Matcher (3pts)
2: Taker (3pts)

Subproblem 3. Mistakes (30pts)

누구나 실수를 합니다. 이 문제에서는 모든 사람이 일정 횟수마다 한 번씩 "실수"를 하여, 자신이 하려던 선택과 반대되는 선택을 합니다. 예를 들어, 3번에 한 번씩 실수하는 Giver가 있다면, 이 사람은 give, give, take, give, give, take... 순서대로 행동하게 됩니다.

이 문제에서는 지금까지 입력에서 사용되지 않았던 2번째 줄을 사용합니다. 2번째 줄에는 사람수와 같은 개수의 0 이상의 정수가 주어집니다. 각각의 숫자는 해당하는 사람이 실수하는 빈도수를 나타냅니다. 실수하는 빈도수가 0이면 실수하지 않습니다. 실수하는 빈도수가 1이면, 모든 선택을 실수합니다. 빈도수가 2이면, 2번에 한번 꼴로 실수합니다. 구체적으로는 다음과 같습니다.

• 실수하는 빈도수가 0이면 실수하지 않습니다. 실수하는 빈도수가 n(>0)이면, i=1, 2, 3, ...번째 선택을 할 때, i % n == 0이면 실수합니다.

다음과 같은 경우를 봅시다.

MMM
3 2 2
0 1
0 1
0 2
0 1
0 2
0 1

사람 A	A의 원래 의도	A의 상호작용 수	A의 실수	A의 실제 선택	사람 B	B의 원래 의도	B의 상호작용 수	B의 실수	B의 실제 선택
0	give	1	N	give	1	give	1	N	give
0	give	2	N	give	1	give	2	Y	take
0	give	3	Y	take	2	give	1	N	give
0	take	4	N	take	1	give	3	N	give
0	give	5	N	give	2	take	2	Y	give
0	give	6	Y	take	1	take	4	Y	give

1. 0번과 1번이 서로 상호작용해서 give합니다.
2. 0번과 1번이 서로 상호작용해서 give합니다. 근데 1번에게 2번째 상호작용이라 1번이 실수해서 take를 합니다.
3. 0번과 2번이 서로 상호작용합니다. 서로 give하려 하지만, 0번에게 3번째 상호작용이라 실수해서 take를 냅니다.
4. 0번과 1번이 서로 상호작용합니다. 0번은 1번이 직전에 take했다는 것을 기억하고 take를 선택합니다. 1번은 0번이 직전에 give했단 것을 기억하고 give를 선택합니다.
5. 0번과 2번이 서로 상호작용합니다. 0번은 2번이 직전에 give했다는 것을 기억하고 give합니다. 2번은 0번이 직전에 take를 했다는 것을 기억하고 take를 하려 하지만, 이것이 2번에게 2번째 상호작용이라 실수해서 give를 냅니다.
6. 0번과 1번이 서로 상호작용합니다. 0번은 1번이 직전에 give했다는 것을 기억하고 give를 하려 하지만, 0번에게 6번째 상호작용이라서 실수로 take를 선택합니다. 1번은 0번이 직전에 take했다는 것을 기억하고 take를 하려 하지만, 1번에게 4번째 상호작용이기 때문에 실수로 give를 선택합니다.

Input

MMM
3 2 2
0 1
0 1
0 2
0 1
0 2
0 1
done

Output

0: Matcher (12pts)
1: Matcher (3pts)
2: Matcher (1pts)