-
Notifications
You must be signed in to change notification settings - Fork 0
Qualification round 2011
Blue and Orange are friendly robots. An evil computer mastermind has locked them up in separate hallways to test them, and then possibly give them cake.
Blue와 Orange는 친한 로봇입니다. 사악한 컴퓨터 지도자는 그들을 테스트하기 위해 분리된 복도에 그들을 두었습니다. 그 다음에 아마 그들에게 케이크를 줄겁입니다.(?)
Each hallway contains 100 buttons labeled with the positive integers {1, 2, ..., 100}. Button k is always k meters from the start of the hallway, and the robots both begin at button 1. Over the period of one second, a robot can walk one meter in either direction, or it can press the button at its position once, or it can stay at its position and not press the button. To complete the test, the robots need to push a certain sequence of buttons in a certain order. Both robots know the full sequence in advance. How fast can they complete it?
각 복도는 양의 정수 {1,2…, 100}으로 이름붙혀진 100개의 버튼이 있습니다. 버튼 K는 항상 복도의 시작점에서 K미터 떨어져있습니다. 그리고 두 로봇은 버튼 1에서 시작합니다. 1초동안에 로봇은 어느 한쪽 방향으로 1미터를 걸어가거나 현재위치에서 버튼을 누르거나 버튼을 누르지 않고 현위치에 머물 수 있습니다. 테스트를 완료하기 위해서 로봇들은 특정한 순서의 버튼을 일정한 순서로 눌러야 합니다. 두 로봇은 진행해야 할 전체 순서를 알고 있습니다. 얼마나 빨리 그것을 완료할 수 있습니까?
For example, let's consider the following button sequence:
O 2, B 1, B 2, O 4
Here, O 2 means button 2 in Orange's hallway, B 1 means button 1 in Blue's hallway, and so on. The robots can push this sequence of buttons in 6 seconds using the strategy shown below:
예를 들면 아래의 버튼 순서를 생각해 보겠습니다.
O 2, B 1, B 2, O 4
여기서 O 2는 Orange의 복도의 버튼 2를 의미하고 B 1은 Bule의 복도의 버튼 1을 의미합니다. 로봇들은 아래 보여진 전략을 사용해서 이 순서의 버튼을 6초내에 누를 수 있습니다.
| Time | Orange | Blue |
|---|---|---|
| 1 | Move to button 2 | Stay at button 1 |
| 2 | Push button 2 | Stay at button 1 |
| 3 | Move to button 3 | Push button 1 |
| 4 | Move to button 4 | Move to button 2 |
| 5 | Stay at button 4 | Push button 2 |
| 6 | Push button 4 | Stay at button 2 |
Note that Blue has to wait until Orange has completely finished pushing O 2 before it can start pushing B 1.
Blue는 B 1을 누르는 것을 시작하기 전에 Orange가 O 2를 누르는 것을 완료할때까지 기다립니다.
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case consists of a single line beginning with a positive integer N, representing the number of buttons that need to be pressed. This is followed by N terms of the form "Ri Pi" where Ri is a robot color (always 'O' or 'B'), and Pi is a button position.
인풋의 첫번째 줄은 테스트케이스 T의 갯수입니다. T 테스트케이스가 이어서 나옵니다.
각 테스트 케이스는 눌러야하는 버튼의 수를 의미하는 양의 정수 N으로 시작하는 한줄로 구성됩니다. 이것은 "Ri Pi"의 폼의 N개의 조건을 따르고 Ri는 로봇의 칼라(항상 'O'이거나 'B'입니다.) 그리고 Pi는 버튼의 위치입니다.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of seconds required for the robots to push the given buttons, in order.
각 테스트 케이스에 대한 아웃풉은 한줄에 "Case #x: y"를 포함합니다. x는 케이스의 번호(1부터 시작)이고 y는 순서대로 주어진 번호를 누르기 위해서 필요한 최소 초(second)입니다.
1 ≤ Pi ≤ 100 for all i.
Small dataset
1 ≤ T ≤ 20.
1 ≤ N ≤ 10.
Large dataset
1 ≤ T ≤ 100.
1 ≤ N ≤ 100.
Input Output
3 Case #1: 6
4 O 2 B 1 B 2 O 4 Case #2: 100
3 O 5 O 8 B 100 Case #3: 4
2 B 2 B 1
Magicka™ is an action-adventure game developed by Arrowhead Game Studios. In Magicka you play a wizard, invoking and combining elements to create Magicks. This problem has a similar idea, but it does not assume that you have played Magicka.
Note: "invoke" means "call on." For this problem, it is a technical term and you don't need to know its normal English meaning.
As a wizard, you can invoke eight elements, which are the "base" elements. Each base element is a single character from {Q, W, E, R, A, S, D, F}. When you invoke an element, it gets appended to your element list. For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A].
We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters). For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form. In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T].
We will specify pairs of base elements that are opposed to each other. After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your whole element list will be cleared.
For example, suppose Q and F combine to make T. R and F are opposed to each other. Then invoking the following things (in order, from left to right) will have the following results:
- QF → [T] (Q and F combine to form T)
- QEF → [Q, E, F] (Q and F can't combine because they were never at the end of the element list together)
- RFE → [E] (F and R are opposed, so the list is cleared; then E is invoked)
- REF → [] (F and R are opposed, so the list is cleared)
- RQF → [R, T] (QF combine to make T, so the list is not cleared)
- RFQ → [Q] (F and R are opposed, so the list is cleared)
Given a list of elements to invoke, what will be in the element list when you're done?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line, containing the following space-separated elements in order:
First an integer C, followed by C strings, each containing three characters: two base elements followed by a non-base element. This indicates that the two base elements combine to form the non-base element. Next will come an integer D, followed by D strings, each containing two characters: two base elements that are opposed to each other. Finally there will be an integer N, followed by a single string containing N characters: the series of base elements you are to invoke. You will invoke them in the order they appear in the string (leftmost character first, and so on), one at a time.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a list in the format "[e0, e1, ...]" where ei is the ith element of the final element list. Please see the sample output for examples.
1 ≤ T ≤ 100. Each pair of base elements may only appear together in one combination, though they may appear in a combination and also be opposed to each other. No base element may be opposed to itself. Unlike in the computer game Magicka, there is no limit to the length of the element list.
Small dataset
0 ≤ C ≤ 1. 0 ≤ D ≤ 1. 1 ≤ N ≤ 10. Large dataset
0 ≤ C ≤ 36. 0 ≤ D ≤ 28. 1 ≤ N ≤ 100.
Input Output
5 Case #1: [E, A]
0 0 2 EA Case #2: [R, I, R]
1 QRI 0 4 RRQR Case #3: [F, D, T]
1 QFT 1 QF 7 FAQFDFQ Case #4: [Z, E, R, A]
1 EEZ 1 QE 7 QEEEERA Case #5: []
0 1 QW 2 QW