#PU1280. USACO 2023 January Contest, Silver — Problem 3. Moo Route

USACO 2023 January Contest, Silver — Problem 3. Moo Route

USACO 2023 January Contest, Silver — Problem 3. Moo Route

题目描述

Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0t=0, Bessie is located at x=0x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 11 unit each second. However, there actually is no exit and after TT seconds, Bessie is back at x=0x=0, tired and resigned. Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5,1.5,2.5,…,(N−1).5x=.5, 1.5, 2.5, \ldots, (N-1).5, given by an array A0,A1,…,AN−1A_0,A_1,\dots,A_{N-1} (1≤N≤1051\leq N \leq 10^5, 1≤Ai≤1061 \leq A_i \leq 10^6, ∑Ai≤106\sum A_i\le 10^6). Bessie never reaches x>Nx>N nor x<0x<0. In particular, Bessie's route can be represented by a string of T=∑i=0N−1AiT = \sum_{i=0}^{N-1} A_i LLs and RRs where the iith character represents the direction Bessie moves in during the iith second. The number of direction changes is defined as the number of occurrences of LRLRs plus the number of occurrences of RLRLs. Please help Farmer Nhoj find any route Bessie could have taken that is consistent with AA and minimizes the number of direction changes. It is guaranteed that there is at least one valid route.

输入格式

The first line contains NN. The second line contains A0,A1,…,AN−1A_0,A_1,\dots,A_{N-1}.

输出格式

(见题面原文)

数据范围

Inputs 3-5: N≤2N\le 2 Inputs 3-10: T=A0+A1+⋯+AN−1≤5000T = A_0 + A_1 + \cdots + A_{N-1} \leq 5000 Inputs 11-20: No additional constraints. Problem credits: Brandon Wang and Claire Zhang

样例

样例 1

2
2 4
RRLRLL
There is only 1 valid route, corresponding to the route
$0\to 1 \to 2 \to 1\to 2 \to 1\to 0$. Since this is the only possible route, it
also has the minimum number of direction changes.

样例 2

3
2 4 4
RRRLLRRLLL
There are 3 possible routes:
RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL
The first two routes have 5 direction changes, while the last one has only 3. 
Thus the last route is the only correct output.