Page not loading? Try clicking here.
Placeholder

#4655
Interactive
Language restricted

Combo 1s 256MB

Problems

You are playing an action video game. The game controller has buttons, A, B, X, and Y. In this game, you can get coins with combo moves. You can make a combo move by pressing buttons in sequence.

This game has a secret sequence of buttons, which can be represented as a string S of those characters. You don't know the string S, but you know its length N.

You also know that the first character of S never reappears in it. For example, S can be "ABXYY" or "XYYAA", but cannot be "AAAAA" or "BXYBX".

You can press a sequence of up to 4N buttons for a combo move. Let p be the string which represents the sequence of the buttons you pressed. The number of coins you get for this move is calculated as the length of the longest prefix of S which is also a substring of p. A substring of a string t is a contiguous (possibly empty) sequence of characters within t. A prefix of t is a substring of that is empty or contains the first character of t.

For example, if S is "ABXYY" and p is "XXYYABYABXAY", you will get 3 coins because "ABX" is the longest prefix of S that is also a substring of p.

Your task is to determine the secret string S using few combo moves.

Implementation

sdf


Subtask

# Score Condition
#15

N = 3

#295

No additional constraints. For this subtask, your score for each test case is calculated as follows. Let q be the number of calls to press.

  • if q ≤ N + 2, your score is 95.

  • if N + 2 < q ≤ N + 10, your score is 95 - 3(q - N - 2).

  • if N + 10 < q ≤ 2N + 1, your score is 25.

  • if max{N + 10, 2N + 1} < q ≤ 4N, your score is 5.

  • Otherwise, your score is 0.


Source

IOI 2018 day1 1

You must sign in to write code.