DMOPC '22 Contest 2 P1 - DMOPC Crisis - Olympiads Online Judge

DMOPC '22 Contest 2 P1 - DMOPC Crisis

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

A long time ago, in a certain Dmojistan far far away, there existed a small DMOPC committee of $N$ ~N~ people. One fateful day, when the $N$ ~N~ members were sitting in a circle (with the $i$ ~i~-th member sitting next to the $(i+1)$ ~(i+1)~-th for all $1 \le i < N$ ~1 \le i < N~ and the $N$ ~N~-th member sitting next to the first) discussing new problem ideas, an evil witch appeared and stated the following: "Look to your left and to your right. By the beginning of next year, at least one of those people will be gone". Terrified about the legitimacy of her statement, the DMOPC committee banded together and wondered: if what the witch said was true, at most how many members will remain in the committee next year? Your job is to answer this question and provide an example of an optimal scenario.

Constraints

$3 \le N \le 2 \times 10^5$ ~3 \le N \le 2 \times 10^5~

Subtask 1 [20%]

$3 \le N \le 6$ ~3 \le N \le 6~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first and only line contains a single integer $N$ ~N~.

Output Specification

On the first line output an integer $M$ ~M~, representing the maximum number of people that can remain in the committee next year.

On the second line output a string of length $N$ ~N~ consisting of the characters _ and M. This string should represent an optimal scenario in which the $N$ ~N~ members used to sit in a circle and $M$ ~M~ people remain in the committee. Specifically, the $i$ ~i~-th character of the string should be M if the $i$ ~i~-th member stays, or _ if they leave. Each index $i$ ~i~ should have at least one character _ next to it, and there should be exactly $M$ ~M~ character Ms in the string. If there exist multiple optimal scenarios, output any one of them.

Scoring

For each test case:

If the integer $M$ ~M~ you output is not maximal, your score will be $0$ ~0~ and you will receive a Wrong Answer verdict.

If the integer $M$ ~M~ you output is maximal but your configuration is invalid or missing, you will receive $50$ ~50~ points.

Otherwise, you will receive $100$ ~100~ points.

Your score for a subtask will be the minimum score over all test cases in the subtask multiplied by the weight of the subtask.

Your final score will be the sum of the scores of all the subtasks.

Sample Input

Sample Output

2
_MM_

Comments

-5
gavin_chen commented on Dec. 17, 2022, 1:48 a.m. ← edit 2 →
if you were to input 6, shouldn't the answer be:

4 M_MM_M

But according to the editorial, it says it should be 2?
This comment is hidden due to too much negative feedback. Show it anyway.

-7
volcano commented on Dec. 17, 2022, 4:09 p.m. ← edit 4 →
4 M_MM_M

This output is incorrect because the second person and fifth person still have both the person to the left and the person to the right alive.
This comment is hidden due to too much negative feedback. Show it anyway.

-6

gavin_chen commented on Dec. 17, 2022, 8:12 p.m. ← edit 3 →

ohh. no wonder, also, your grammar is wrong.

This comment is hidden due to too much negative feedback. Show it anyway.

-8

volcano commented on Dec. 17, 2022, 10:47 p.m.

No, my grammar is not wrong. I was only trying to assist you, I am sorry.

This comment is hidden due to too much negative feedback. Show it anyway.

-2

JinchengLuo2007 commented on Dec. 17, 2022, 2:34 a.m.

methinks its fixd now