#P6926. [ICPC2016 WF] String Theory

[ICPC2016 WF] String Theory

题目描述

Nested quotations are great not only for writing literature with a complex narrative structure, but also in programming languages. While it may seem necessary to use different quotation marks at different nesting levels for clarity, there is an alternative. We can display various nesting levels using kk-quotations, which are defined as follows.

A 11-quotation is a string that begins with a quote character, ends with another quote character and contains no quote characters in-between. These are just the usual (unnested) quotations. For example, 'this is a string' is a 11-quotation.

For k>1k > 1, a kk-quotation is a string that begins with kk quote characters, ends with another kk quote characters and contains a nested string in-between. The nested string is a non-empty sequence of (k1)(k-1)-quotations, which may be preceded, separated, and/or succeeded by any number of non-quote characters. For example, ''All 'work' and no 'play''' is a 22-quotation.

Given a description of a string, you must determine its maximum possible nesting level.

输入格式

The input consists of two lines. The first line contains an integer nn (1n1001 \le n \le 100). The second line contains nn integers a1,a2,,ana_1, a_2, \ldots , a_ n (1ai1001 \le a_ i \le 100), which describe a string as follows. The string starts with a1a_1 quote characters, which are followed by a positive number of non-quote characters, which are followed by a2a_2 quote characters, which are followed by a positive number of non-quote characters, and so on, until the string ends with ana_ n quote characters.

输出格式

Display the largest number kk such that a string described by the input is a kk-quotation. If there is no such kk, display no quotation instead.

题目大意

定义 11 级引用是一个以引号字符 ' 开头和结尾,中间不包含引号字符的字符串。定义 kk 级引用为两端各有连续 k(k>1)k(k>1) 个引号,中间有若干个 k1k-1 级引用的字符串,其中第一个 k1k-1 级引用前,最后一个 k1k-1 级引用后,相邻两个 k1k-1 级引用之间都可以添加任意个非引用字符。

现给定一个字符串中极长连续引号段的个数 n(n100)n(n\le100),和这 nn 个极长连续引号段的长度 a1,...,ana_1,...,a_n,求最大的 kk,使得这个字符串是一个 kk 级引用。 若这样的 kk 不存在,输出 no quotation

translated by @Starlight237

5
2 1 1 1 3

2

1
22

4

1
1

no quotation

提示

Time limit: 2000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2016