Problem Statement
Ook the Oktopus is finally bored of having his school of pet rainbow fish around, and has decided to send them to school. Specifically, to Haymouth's Pet Training Skool. The fish are still residing in their system of tanks. In school, the fish are easily distracted and like to disrupt the class by talking to each other. In order to make the fish pay attention to their lessons, Haymouth has removed all the connecting tubes between the tanks, and placed N transparent tanks in a line, numbered from 1 to N from left to right, with exactly one rainbow fish in each tank.
Each fish can only see the 2 fish in its neighboring tanks on the left and right. A fish can also tell if its left or right side is empty (i.e. it is at the end of the line). Otherwise, a fish has no information about where along the line it is.
The fish measure time in discrete time steps, synchronized among the entire school of fish. Each rainbow fish has a color, represented by a non-negative integer. Since these are magical rainbow fish, they have developed the ability to change color. At each time step, a fish will look at the colors of itself and its neighboring fish, and possibly change color. This happens simultaneously for the entire school of fish (i.e. the new color depends on the colors of that fish and its neighbors in the previous time step). Since the fish aren't very smart, these color changes happen deterministically (i.e. the color the fish will change to is always the same given the previous colors of itself and its two neighbors). Fish have a short memory, so they are not able to keep track of what time it is. Hence, you will help them choose how long they should carry on changing colors.
Ook's rainbow fish are very bored indeed, so they would like to find out some information about themselves. The fish are quite lazy, so they want to change into as few colors as possible (otherwise, they'd have to learn to recognize more colors). The fish are also quite impatient, so they want to know this information in as short a time as possible. Help the fish determine how they should change colors!
Implementation Notes
The template file, header and sample grader are included under attachments. Each subtask follows a different format, so you are advised to use the template provided.
The sample grader reads input of the following format:
The first line contains 2 integers, the subtask number and N.
The next line contains N space-seperated numbers, the initial colors of the fish.
Do not store information in any global variables in your implementation. In testing, the fish may not be updated in order.
In all subtasks, you have to implement variants of:
int fish(int C, int L, int R);
This contains the rules for the color changes of the fish for that subtask. C is the color of that fish itself, L is the color of the fish on the left, and R is the color of the fish on the right in the previous time step. If there is no left or right neighbor, L or R will be -1. This function returns what color the fish should change to for the current time step. If the fish should not change color, the function should return C.
int init(int N);
This will be called once at the start of the subtask. It should return the number of time steps the fish should change color for.
Limits
N refers to the number of tanks. In all subtasks, N ≤ 1000.
L refers to the number of time steps. The initial state is time 0. In all subtasks, L ≤ 10000. Your program will be rejected if it returns L > 10000.
K refers to the maximum color used by the fish.
Your Tasks
Subtask 1 [7 points]
Problem:
The fish would like to know if they are on an odd or even position along the line. Originally, all fish have color 0. At the end of all the color changes, fish in an odd position along the line should be color 1, and fish in an even position along the line should be color 0.
Limits:
K ≤ 1, L ≤ N.
Implementation:
You should implement
int fishEvenOrOdd(int C, int L, int R) and
int initEvenOrOdd(int N).
Subtask 2 [up to 19 points]
Problem:
The fish are getting more creative. They want to play a factorization game. Originally, all fish have color 0. At the end of all the color changes, fish in a position divisible by 3 should be color 1, fish in a position divisible by 5 should be color 2, fish in a position divisible by both 3 and 5 should be color 3, and the rest should be color 0.
Limits:
K < 19, N = 1000.
Scoring:
Your solution will receive min(1, 52/K2)*min(1, N/L)*19 points.
Implementation:
You should implement
int fishFactors(int C, int L, int R) and
int initFactors(int N).
Subtask 3 [up to 31 points]
Problem:
The fish have discovered that those in tanks which are numbered a power of 2 are particularly powerful. Hence, the fish would like to know whether they are powerful or not. The powerful fish would like to become color 1, to show how powerful they are. Any fish that is between two powerful fish must be color 0. Since fish number 20 = 1 is powerful, this means that any fish to the left of a powerful fish that is not powerful itself must be color 0.
At time 0, all the fish will be color 0. Because the fish are now more powerful than before, you can help them by calling void setFish(int P, int C) to set the color of any one fish at time 0. The function will change the color of the fish at position P to C. After this, the fish will proceed with their color changes. At the end of all the color changes, the fish in a position which is a power of 2 must be color 1, and the fish between two powerful fish must be color 0. It doesn't matter what color the other fish are.
Limits:
N = 1000, K ≤ 30.
Scoring:
Your solution will receive min(1, 102/K2)*min(1, N/L)*31 points.
Implementation:
You should implement
int fishPower(int C, int L, int R) and
int initPower(int N).
Subtask 4 [up to 17 points]
Problem:
After their afternoon nap, the fish woke up to find that something has caused them to change color! Now, the fish are either colored 0 or 1. The fish would like to know whether there are an even or odd number of fish colored 1. In order for every fish to know this, all the fish want to be colored 0 if there are an even number of fish colored 1 initially, and colored 1 if there are an odd number of fish colored 1 initially.
Limits:
K < 17.
Scoring:
Your solution will receive min(1, 52/K2)*min(1, (2*N + 1)/L)*17 points.
Implementation:
You should implement
int fishCountParity(int C, int L, int R) and
int initCountParity(int N).
Subtask 5 [up to 26 points]
Problem:
When the fish wake up the next day, they find that they are all colored 0 or 1 again! Now, the fish are a cliquey bunch, so they would like to be near other fish that are the same color as them. However, they don't want to change the balance of the number of 0s and 1s. For example, if there are x 0s and y 1s initially, the first x fish would like to be colored 0, and the next y fish would like to be colored 1.
Limits:
K < 26.
Scoring:
Your solution will receive min(1, 12/K2)*min(1, N/L)*26 points.
Implementation:
You should implement
int fishGroup(int C, int L, int R) and
int initGroup(int N).