# Google Code Jam 2019 – Qualification Round Solutions (C++ and Python) ## 1. Foregone Solution – Problem A

### Problem :

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an oversized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a `4`… and the `4` key on the keyboard of our oversized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a `4`, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

Input :

The first line of the input gives the number of test cases, TT test cases follow; each consists of one line with an integer N.

Output :

For each test case, output one line containing `Case #x: A B`, where `x` is the test case number (starting from 1), and `A` and `B` are positive integers as described above.

It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them. (See “What if a test case has multiple correct solutions?” in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2019 contest.)

Limits :

`1 ≤ T ≤ 100.`Time limit: 10 seconds per test set.
Memory limit: 1GB.
At least one of the digits of N is a 4.

Test set 1 (Visible) :

`1 < N < 105.`

Test set 2 (Visible) :

`1 < N < 109.`

Solving the first two test sets for this problem should get you a long way toward advancing. The third test set is worth only 1 extra point, for extra fun and bragging rights!

Test set 3 (Hidden)

`1 < N < 10100`.

Sample :

In Sample Case #1, notice that A and B can be the same. The only other possible answers are `1 3` and `3 1`.

### Solutions (C++) :

``````#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
for (int T = 1; T <= t; T += 1) {
auto Print = [&](string a, string b) {
cout << "Case #" << T << ": ";
{
int i = 0;
for (; i < (int)a.size() and a[i] == '0'; i += 1) { }
for (; i < (int)a.size(); i += 1) { cout << a[i]; }
}

cout << ' ';

{
int i = 0;
for (; i < (int)b.size() and b[i] == '0'; i += 1) { }
for (; i < (int)b.size(); i += 1) { cout << b[i]; }

}

cout << '\n';
};

string x; cin >> x;
string a = x, b = x;

bool only_1 = true;

for (auto& itr : x) {
if (itr != '1') {
only_1 = false;
}
}

if (only_1) {
a = '0';
b = string(x.size(), '0');
b = '1';

Print(a, b);
continue;
}

for (int i = 0; i < (int)x.size(); i += 1) {
for (int j = 0; j < 9; j += 1) {
int oth = a[i] - '0' - j;
if (0 <= oth and oth <= 9 and oth != 4 and j != 4) {
a[i] = '0' + oth;
b[i] = '0' + j;
break;
}
}
}

Print(a, b);

}
return 0;
}``````

## 2. You Can Go Your Own Way – Problem B

### Problem :

You have just entered the world’s easiest maze. You start in the northwest cell of an N by N grid of unit cells, and you must reach the southeast cell. You have only two types of moves available: a unit move to the east, and a unit move to the south. You can move into any cell, but you may not make a move that would cause you to leave the grid.

You are excited to be the first in the world to solve the maze, but then you see footprints. Your rival, Labyrinth Lydia, has already solved the maze before you, using the same rules described above!

As an original thinker, you do not want to reuse any of Lydia’s moves. Specifically, if her path includes a unit move from some cell A to some adjacent cell B, your path cannot also include a move from A to B. (However, in that case, it is OK for your path to visit A or visit B, as long as you do not go from A to B.) Please find such a path.

In the following picture, Lydia’s path is indicated in blue, and one possible valid path for you is indicated in orange:

Input :

The first line of the input gives the number of test cases, TT test cases follow; each case consists of two lines. The first line contains one integer N, giving the dimensions of the maze, as described above. The second line contains a string P of 2N – 2 characters, each of which is either uppercase `E` (for east) or uppercase `S` (for south), representing Lydia’s valid path through the maze.

Output :

For each test case, output one line containing `Case #x: y`, where `x` is the test case number (starting from 1) and `y` is a string of 2N – 2 characters each of which is either uppercase `E` (for east) or uppercase `S` (for south), representing your valid path through the maze that does not conflict with Lydia’s path, as described above. It is guaranteed that at least one answer exists.

Limits :

`1 ≤ T ≤ 100`.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
P contains exactly N – 1 `E` characters and exactly N – 1 `S` characters.

Test set 1 (Visible) :

`2 ≤ N ≤ 10`.

Test set 2 (Visible) :

`2 ≤ N ≤ 1000`.

Test set 3 (Hidden) :

For at most 10 cases, `2 ≤ N ≤ 50000`.
For all other cases, `2 ≤ N ≤ 10000`.

Sample :

In Sample Case #1, the maze is so small that there is only one valid solution left for us.

Sample Case #2 corresponds to the picture above. Notice that it is acceptable for the paths to cross.

### Solution (C++) :

``````#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
for (int T = 1; T <= t; T += 1) {
cout << "Case #" << T << ": ";
int n; cin >> n;
string x; cin >> x;
for (auto& itr : x) {
if (itr == 'S') {
cout << 'E';
} else {
cout << 'S';
}
}

cout << '\n';

}
return 0;
}``````

## 3. Cryptopangrams – Problem C

### Problem :

On the Code Jam team, we enjoy sending each other pangrams, which are phrases that use each letter of the English alphabet at least once. One common example of a pangram is “the quick brown fox jumps over the lazy dog”. Sometimes our pangrams contain confidential information — for example, `CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS` — so we need to keep them secure.

We looked through a cryptography textbook for a few minutes, and we learned that it is very hard to factor products of two large prime numbers, so we devised an encryption scheme based on that fact. First, we made some preparations:

• We chose 26 different prime numbers, none of which is larger than some integer N.
• We sorted those primes in increasing order. Then, we assigned the smallest prime to the letter `A`, the second smallest prime to the letter `B`, and so on.
• Everyone on the team memorized this list.

Now, whenever we want to send a pangram as a message, we first remove all spacing to form a plaintext message. Then we write down the product of the prime for the first letter of the plaintext and the prime for the second letter of the plaintext. Then we write down the product of the primes for the second and third plaintext letters, and so on, ending with the product of the primes for the next-to-last and last plaintext letters. This new list of values is our ciphertext. The number of values is one smaller than the number of characters in the plaintext message.

For example, suppose that N = 103 and we chose to use the first 26 odd prime numbers, because we worry that it is too easy to factor even numbers. Then `A` = 3, `B` = 5, `C` = 7, `D` = 11, and so on, up to `Z` = 103. Also suppose that we want to encrypt the `CJ QUIZ`… pangram above, so our plaintext is `CJQUIZKNOWBEVYOFDPFLUXALGORITHMS`. Then the first value in our ciphertext is 7 (the prime for `C`) times 31 (the prime for `J`) = `217`; the next value is `1891`, and so on, ending with `3053`.

We will give you a ciphertext message and the value of N that we used. We will not tell you which primes we used, or how to decrypt the ciphertext. Do you think you can recover the plaintext anyway?

Input :

The first line of the input gives the number of test cases, TT test cases follow; each test case consists of two lines. The first line contains two integers: N, as described above, and L, the length of the list of values in the ciphertext. The second line contains L integers: the list of values in the ciphertext.

Output :

For each test case, output one line containing `Case #x: y`, where `x` is the test case number (starting from 1) and `y` is a string of L + 1 uppercase English alphabet letters: the plaintext.

Limits :

`1 ≤ T ≤ 100`.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
`25 ≤ L ≤ 100`.
The plaintext contains each English alphabet letter at least once.

Test set 1 (Visible) :

`101 ≤ N ≤ 10000`.

Test set 2 (Hidden) :

`101 ≤ N ≤ 10100`.

Sample :

### Solution (Python 3) :

``````def parser():
while 1:
data = list(input().split(' '))
for number in data:
if len(number) > 0:
yield(number)

input_parser = parser()

def get_word():
global input_parser
return next(input_parser)

def get_number():
data = get_word()
try:
return int(data)
except ValueError:
return float(data)

def gcd(a, b):
if a == 0:
return b
if b == 0:
return a
return gcd(b, a % b)

t = get_number()
for T in range(1, t + 1):
_ = get_number()
n = get_number()
numbers = []
for i in range(n):
numbers.append(get_number())

primes = []
final_primes =  * (n + 1)
where = 0
for i in range(0, n - 1):
if numbers[i] != numbers[i + 1]:
final_primes[i + 1] = (gcd(numbers[i], numbers[i + 1]))
where = i + 1
break

for i in range(where - 1, -1, -1):
final_primes[i] = numbers[i] // final_primes[i + 1]
for i in range(where + 1, n + 1):
final_primes[i] = numbers[i - 1] // final_primes[i - 1]

all_primes = [i for i in final_primes]
all_primes.sort()

last = -1

d = {}
j = 0
for i in all_primes:
if i == last:
continue

d[i] = chr(j + ord('A'))
j = j + 1
last = i

print("Case #" + str(T) + ": ", end = "")
for i in final_primes:
print(d[i], end='')
print("")``````

## 4. Dat Bae – Problem D

### Problem :

A research consortium has built a new database system for their new data center. The database is made up of one master computer and N worker computers, which are given IDs from 0 to N-1. Each worker stores exactly one bit of information… which seems rather wasteful, but this is very important data!

You have been hired to evaluate the following instruction for the database:

• `TEST_STORE` <bits>: The master reads in <bits>, which is a string of N bits, and sends the i-th bit to the i-th worker for storage. The master will then read the bits back from the workers and return them to the user, in the same order in which they were read in.

During normal operation, `TEST_STORE` should return the same string of bits that it read in, but unfortunately, B of the workers are broken!

The broken workers are correctly able to store the bits given to them, but whenever the master tries to read from a broken worker, no bit is returned. This causes the `TEST_STORE` operation to return only NB bits, which are the bits stored on the non-broken workers (in ascending order of their IDs). For example, suppose N = 5 and the 0th and 3rd workers are broken (so B = 2). Then:

• `TEST_STORE 01101` returns `111`.
• `TEST_STORE 00110` returns `010`.
• `TEST_STORE 01010` returns `100`.
• `TEST_STORE 11010` also returns `100`.

For security reasons, the database is hidden in an underground mountain vault, so calls to `TEST_STORE` take a very long time. You have been tasked with working out which workers are broken using at most F calls to `TEST_STORE`.

Input and output :

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.

Initially, your program should read a single line containing a single integer T indicating the number of test cases. Then, you need to process T test cases.

For each test case, your program will first read a single line containing three integers NB, and F, indicating the number of workers, the number of broken workers, and the number of lines you may send (as described below).

Then you may send the judge up to F lines, each containing a string of exactly N characters, each either `0` or `1`. Each time you send a line, the judge will check that you have not made more than F calls. If you have, the judge will send you a single line containing a single `-1`, and then finish all communication and wait for your program to finish. Otherwise, the judge will send a string of length NB: the string returned by `TEST_STORE`, as described above.

Once your program knows the index of the B broken workers, it can finish the test case by sending B space-separated integers: the IDs of the broken workers, in sorted order. This does not count as one of your F calls.

If the B integers are not exactly the IDs of the B broken workers, you will receive a Wrong Answer verdict, and the judge will send a single line containing `-1`, and then no additional communication. If your answer was correct, the judge will send a single line with `1`, followed by the line that begins the next test case (or exit, if that was the last test case).

Limits :

Time limit: 20 seconds per test set.
Memory limit: 1GB.
`1 ≤ T ≤ 100`.
`2 ≤ N ≤ 1024`.
`1 ≤ B ≤ min(15, N-1)`.

Test set 1 (Visible) :

`F = 10`.

Test set 2 (Hidden) :

`F = 5`.

Testing Tool :

You can use this testing tool to test locally or on our servers. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the Interactive Problems section of the FAQ.

Local Testing Tool :

To better facilitate local testing, we provide you the following script. Instructions are included inside. You are encouraged to add more test cases for better testing. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.

If your code passes the testing tool but fails the real judge, please check here to make sure that you are using the same compiler as us.

Sample Interaction :

The following interaction meets the limits for Test set 1.

``````t = readline_int()           // Reads 2 into t
n, b, f = readline_int_list()  // Reads 5, 2, 10 into n, b, f
printline 01101 to stdout    // The next four outputs match the example in
// the problem statement.
flush stdout
response = readline_str()    // Reads 111 into response. (At this point, we
// could determine the answer; the remaining
// queries are just examples!)
printline 00110 to stdout
flush stdout
printline 01010 to stdout
flush stdout
printline 11010 to stdout
flush stdout
printline 0 3 to stdout      // Guesses the answer. Notice that we were
// not required to use all 10 of our allowed
// queries.
flush stdout
verdict = readline_int()     // Reads 1 into verdict. We got that test case
// right!
n, b, f = readline_int_list()  // Reads 2, 1, 10 into n, b, f.
printline 01 to stdout       // 01 is a query, not a guess at the final
// answer (if we wanted to guess that just
// worker 1 were broken, we would have to
// send 1 as we do below)
flush stdout
printline 1 to stdout        // Makes a (bad) wild guess.
exit                         // exits to avoid an ambiguous TLE error``````

### Solution (C++) :

``````#include <iostream>
#include <vector>
using namespace std;

int main() {
int t; cin >> t;
while (t--) {
int n, b, f; cin >> n >> b >> f;

int num_batches = (n + 15) / 16;
vector<int> batch_len;
vector<int> num_good_here(num_batches);

{
int aux = n;
while (aux > 0) {
batch_len.push_back(min(aux, 16));
aux -= 16;
}
}

for (int i = 0; i < n; i += 1) {
cout << (!!(i & 16));
}
cout << endl;

string s; cin >> s;
for (int i = 0, current = 0, batch_num = 0; i < (int)s.size(); current ^= 1, batch_num += 1) {
while (i < (int)s.size() and s[i] == '0' + (current)) {
num_good_here[batch_num] += 1;
i += 1;
}
}

// testing out stuff
for (int j = 0; j < 4; j += 1) {
string s = "";
for (int i = 0; i < n; i += 1) {
s += (!!(i & (1 << j))) + '0';
}

cout << s << endl;
string x; cin >> x; received[j] = x;
}

int start_index = 0;
for (int i = 0; i < num_batches; i += 1) {
vector<int> current_numbers = {};
int num_here = num_good_here[i];
//            cerr << "Num here: ... " << num_here << '\n';
for (int j = 0; j < num_here; j += 1) {
int x = 0;
for (int l = 0; l < 4; l += 1) {
x += ((received[l][start_index + j]) - '0') << l;
}
current_numbers.push_back(x);
//                cerr << "Inserting: " << x << '\n';
}

for (int p = 0; p < batch_len[i]; p += 1) {
bool ok = false;
for (auto& itr : current_numbers) {
if (itr == p) {
ok = true;
}
}

if (ok == false) {
cout << i * 16 + p << ' ';
}
}

start_index += num_here;
}

cout << '\n';
string x; cin >> x;
}
}``````

1,015 total views,  2 views today