Info (1) Cup 2019

This is one of the not interactive question. (2 out of 4 questions are interactive questions). You can try it !

InfO(1) CUP 2019 Third edition International Round

COSTINLAND

Costin is the dictator of Costinland, a country located on a very small island in the middle of Pacific Ocean. One day, Costin started feeling depressed because his island was very small. In order to stop his own depression, he decided to conquer other countries, so that the territory of Costinland and his influence as a dictator

will be even bigger! In order to do that, he needs an army! But no citizen of Costinland fits the dictator’s requirements... So what army would be better than an army of Costins? Thus, being the smartest person living in Costinland, he invented cloning on a Saturday evening. Being a very playful person (the most playful person in Costinland), he wanted to play with his clones while creating them.

Maximum time of execution: 0.5seconds/test. Maximum available memory: 64 MB

For that, Costin chose a piece of land consisting of N x M cells. There are 4 types of cells:“X” (if a Costin steps on this cell, he clones himself; one of the Costins goes right and the other one goes down), “r” (if a Costin steps on this cell, he will go right, regardless of his initial direction), “d” (if a Costin steps on this cell, he will go down, regardless of his initial direction),“.” (if a Costin steps on this cell, he will not change his initial direction and will move to the next cell indicated by his direction).
Costin leaves from (1,1) and wants to reach (N,M), along with all of the created clones. Costin is also very lazy (the laziest person in Costinland), so he asks you “nicely” to help him build such a matrix, such that exactly K clones will reach (N,M). Clones cannot be “lost” on their way (read the constraints carefully).

TASK

Given K, help Costin generate such a (small) matrix that will bring to (N,M) exactly KCostins.

INPUT FORMAT

The first line contains one integer: K.

OUTPUT FORMAT

The first line will contain to integers: N, M (the size of the matrix). The following N lines will contain M characters, describing the matrix.

Page 1 of 3

CONSTRAINTS

•   The character situated on (1,1) must be different from “.”, in order to give a direction
  to the first Costin. (It can be “X”, “d” or “r”)
•   None of the Costins stops until he reaches (N,M).
•   In order not to waste Costins or to lose them somehow during their path, the last line
  of the matrix will consist only of “r” and the last column will consist only of “d”. By exception, the character situated on (N,M) will be “.” (There is no need to give the Costins a direction since they reached their destination)
•   In order to get 100 points, you need to generate a matrix with both of its sides smaller than or equal to 5, for the first subtask, and one with both of its sides smaller than or equal to 49, for the second subtask (more details below in the SCORING section).

Subtask	Score	Restrictions
1	20 points	3 <= K <= 19
2	Another 80 points	19 < K <= 1018

The scoring is very hard to read on the blog, sorry.

SCORING:
Let CxD be the contestant’s matrix size. Subtask 1:

•   If max{C,D} <= 5, you will receive 100% of the points on that test case.
•   If max{C,D} = 6, you will receive 60% of the points on that test case.

                                                                                         If 6 < max{C,D} <= 500, you will receive 60*𝟓𝟎𝟎−𝒎𝒂𝒙{𝑪,𝑫}/500/6 % of the points on

that test case. If max{C,D} > 500, you will receive 0% of the points on that test case.

Subtask 2: If max{C,D} <= 49, you will receive 100% of the points on that test case.

 If 49 < max{C,D} < 62, you will receive 60+40*1.262−max {𝐶,𝐷}/1.262−49 % of the points

on that test case. If max{C,D} = 62, you will receive 60% of the points on that test case.

𝟓𝟎𝟎−𝒎𝒂𝒙{𝑪,𝑫} If 62 < max{C,D} <= 500, you will receive 60* 𝟓𝟎𝟎−𝟔𝟐 % of the points on

that test case. If max{C,D}>500, you will receive 0% of the points on that test case.

Page 2 of 3

COMPILER MESSAGES:

•   "The output does not fit the requirements": You will get this message if your
  matrix does not respect the CONSTRAINTS or the OUTPUT FORMAT.
•   "Matrix size too big": You will get this message if max{C,D}>500.
•   "The matrix does not generate the required number of Costins": You will get
  this message if, in the end, there won’t be exactly K Costins in (N,M).
•   If you don’t get any of these messages, you will receive a score according to the formulas from above and a message which specifies the size of your generated matrix for that test case.

EXAMPLE:

Input:
11
Output:
4 4
XXXd
.XXd
.XXd
rrr.