-
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.
Magicka™(이하 매직카)는 Arrowhead Game Studios가 개발한 액션어드벤쳐게임이다. 매직카에서 위자드로 플레이하면, 매직을 생성하는 요소들을 불러내고 조합한다. 이 문제는 유사한 발상을 가지고 있지만 여러분이 매지카를 플레이해봤을 거라고 추정하지는 않는다.
Note: "invoke" means "call on." For this problem, it is a technical term and you don't need to know its normal English meaning.
주: invoke는 call on을 뜻한다. 이 문제에서는 기술적인 용어이며 여러분은 일반적인 영어에서 가리키는 바를 알 필요는 없다.
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].
위자드인 여러분은 8개의 "기본" 요소들을 부를 수 있다. 각각의 기본 요소는 {Q, W, E, R, A, S, D, F}로 된 단일 문자이다. 여러분이 하나의 요소를 부르면 그 요소는 여러분이 만든 요소리스트에 덧붙여진다. 예를 들어, 여러분이 W를 부르고 A를 부르면(줄여서 "WA 소환"이라고 하겠다) 리스트는 [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].
기본 요소의 쌍은 결합하여 기본외 요소(다른 18개의 대문자)를 만들어 낸다. 예를 들어, Q와 F는 결합하여 T를 만들어 낸다. 만약 두 요소가 리스트의 끝에 위치하면 쌍을 이루는 두 요소는 삭제되고 요소들 만들어내는 새로운 요소로 바뀐다. 요소리스트가 [A, Q, F]이거나 [A, F, Q]라고 하면, 요소리스트는 [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:
예를 들어, Q와 F가 결합하여 T를 만들어낸다고 하자. R과 F는 서로에 대해 반대한다. 그리고나서 다음의 것들(순차로, 왼쪽에서 오른쪽)을 부르면 결과는 다음과 같다.
- 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:
입력의 첫라인은 테스트케이스 T의 수이다. T 테스트케이스는 이어서 나온다. 각 테스트케이스는 공백으로 분리된 요소들이 순차적으로 구성된 싱글라인으로 되어 있다.
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.
첫 번째 정수 C에 이어 C 스트링 나오며 각 3개의 문자를 포함하고 있다. - 2개의 기본 요소와 기본외 요소 이것은 두 개의 기본 요소가 결합하여 기본외 요소를 만들어 냄을 표현한다. 다음에 정수 D가 나오며, 그 뒤에 2개의 문자를 가진 D 스트링이 나온다. - 2개의 기본 요소는 서로 반대한다. 마지막으로 정수 N에 이어 N개의 문자를 가진 싱글 스트링이 나온다. - 여러분이 불러야 할 기본 요소 시리즈. 여러분은 순차적으로 요소를 불러야 하며, 요소들은 차례대로(가장 왼쪽 문자가 첫번째 등등) 스트링에 나타난다.
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.
각 테스트 케이스에서 아웃풋 한줄에 "Case #x: y"를 포함한다. x는 케이스의 번호(1부터 시작)이고 y는 "[e0, e1, ...]" 형태의 리스트이며 ei은 마지막 요소리스트의 ith 요소이다. 예제의 샘플 아웃풋을 보길 바란다.
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
Sean and Patrick are brothers who just got a nice bag of candy from their parents. Each piece of candy has some positive integer value, and the children want to divide the candy between them. First, Sean will split the candy into two piles, and choose one to give to Patrick. Then Patrick will try to calculate the value of each pile, where the value of a pile is the sum of the values of all pieces of candy in that pile; if he decides the piles don't have equal value, he will start crying.
Sean 그리고 Partick 은 그들의 부모들에게 멋진 캔디 가방을 받았다. 각 캔디의 조각은 어떤 정수의 값을 가지고 있고 , 그 아이들은 그들 사이에 사탕을 나누고 싶어 한다. 첫째로 Sean는 캔디를 두개로 나눈 다음 하나를 선택하고 Patrick에게 줄 것임. 그리고 더미의 값이 그 더미에 캔디의 모든 조각의 합계이고,Patrick는 각 더미의 값을 계산할것입니다. 만약 그는 더미의 동등한 값이 없다고 결정하면 그는 울기 시작할 것입니다.
Unfortunately, Patrick is very young and doesn't know how to add properly. He almost knows how to add numbers in binary; but when he adds two 1s together, he always forgets to carry the remainder to the next bit. For example, if he wants to sum 12 (1100 in binary) and 5 (101 in binary), he will add the two rightmost bits correctly, but in the third bit he will forget to carry the remainder to the next bit:
불행히도 , Patrick은 매우 어리고 정확히 어떻게 추가 해야하는지 알지 못합니다. 그는 이진수 안에 어떻게 숫자들을 추가 하는지 거의 알고 있다. 그러나 두개의 1의 값을 함께 추가 할때, 항상 다음비트에 나머지를 나르는 것을 잊어버린다. 예를 들어 만약 12(1100 바이너리) 랑 5(101 바이너리) 의 합계를 원할때, 가장 오른쪽 두 비트들은 정확하게 추가할 것인데 3번째 비트는 나머지를 다음 비트로 가져가는 것을 잊어버릴 것입니다.
1100
+ 0101
------
1001
So after adding the last bit without the carry from the third bit, the final result is 9 (1001 in binary). Here are some other examples of Patrick's math skills:
그래서 3번째 비트에서 나머지를 가지고 오지 않고 마지막 비트를 더하면 결국 결과는 9(1001 바이너리). Patrick's의 수학 능력들의 다른 예제들.
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
Sean is very good at adding, and he wants to take as much value as he can without causing his little brother to cry. If it's possible, he will split the bag of candy into two non-empty piles such that Patrick thinks that both have the same value. Given the values of all pieces of candy in the bag, we would like to know if this is possible; and, if it's possible, determine the maximum possible value of Sean's pile.
Sean은 더하기를 매우 잘하고, 그의 동생을 울리지 않고 값을 잘 가지기를 원한다. 만약 그것이 가능 하면 그는 Patrick이 두개 모두 같은 값을 가졌다고 생각하도록 캔디 가방을 두개의 비지 않은 덩어리로 나눌 것입니다. 그 가방안에 캔디의 모든 조각들의 값이 주어지면 우리는 그것이 가능할 것인지 알고 싶어 할 것입니다. 그리고 그것이 가능하면, Sean의 더미에 최고의 값의 값을 결정할 것입니다.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described in two lines. The first line contains a single integer N, denoting the number of candies in the bag. The next line contains the N integers Ci separated by single spaces, which denote the value of each piece of candy in the bag.
입력의 제일 첫라인은 테스트 케이스의 숫자(T)를 줄 것이다. T 테스트 케이스들이 따라 올것이다. 각 테스트 케이스는 두개의 라인을 묘사한다. 첫 줄은 single integer N을 포함하고, 그 가방안에 숫자를 나타낸다. 다음 라인은 가방안 캔디의 각 조각의 값을 나타내는 N 숫자들의 single 공백으로 구분되어 있는 Ci을 포함한다.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1). If it is impossible for Sean to keep Patrick from crying, y should be the word "NO". Otherwise, y should be the value of the pile of candies that Sean will keep.
각 테스트 케이스에 대한 아웃풋은 한줄에 "Case #x: y"를 포함합니다. x는 케이스의 번호임(1부터 시작). 만약 Sean 이 Patrick 울음으로 부터 지키기 불가능 하면 , y는 "NO" 문자이어야 합니다. 만약 그렇지 않으면 y는 Sean이 계산한 캔디의 더미의 값이어야 합니다.
1 ≤ T ≤ 100.
1 ≤ Ci ≤ 106.
Small dataset
2 ≤ N ≤ 15.
Large dataset
2 ≤ N ≤ 1000.
Input Output
2 Case #1: NO
5 Case #2: 11
1 2 3 4 5
3
3 5 6
Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of N different integers. Algorithms are not Goro's strength; strength is Goro's strength. Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible. This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations.
Goro wants to sort the array as quickly as possible. How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table? Goro has an infinite number of fingers on the two hands he uses to hold down the array.
More precisely, before each hit, Goro may choose any subset of the elements of the array to freeze in place. He may choose differently depending on the outcomes of previous hits. Each hit permutes the unfrozen elements uniformly at random. Each permutation is equally likely.
The first line of the input gives the number of test cases, T. T test cases follow. Each one will consist of two lines. The first line will give the number N. The second line will list the N elements of the array in their initial order.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the expected number of hit-the-table operations when following the best hold-down strategy. Answers with an absolute or relative error of at most 10-6 will be considered correct.
1 ≤ T ≤ 100;
The second line of each test case will contain a permutation of the N smallest positive integers.
Small dataset
1 ≤ N ≤ 10;
Large dataset
1 ≤ N ≤ 1000;
Input Output
3 Case #1: 2.000000
2 Case #2: 2.000000
2 1 Case #3: 4.000000
3
1 3 2
4
2 1 4 3
In test case #3, one possible strategy is to hold down the two leftmost elements first. Elements 3 and 4 will be free to move. After a table hit, they will land in the correct order [3, 4] with probability 1/2 and in the wrong order [4, 3] with probability 1/2. Therefore, on average it will take 2 hits to arrange them in the correct order. After that, Goro can hold down elements 3 and 4 and hit the table until 1 and 2 land in the correct order, which will take another 2 hits, on average. The total is then 2 + 2 = 4 hits.