301374: CF257D. Sum

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Sum

题意翻译

给定一个长度为 $n (1\le n\le 10^5)$ 的数组 $a$,对于任意 $1\le i\le n-1$ 满足 $a_i\le a_{i+1}\le 2\times a_i$。 你的任务是给数组中每个元素前面加一个符号 `+` 或 `-` ,使得它们的和 $s$ 满足 $0\le s \le a_1$,如果有多种解决方案,输出其中一种即可。

题目描述

Vasya has found a piece of paper with an array written on it. The array consists of $ n $ integers $ a_{1},a_{2},...,a_{n} $ . Vasya noticed that the following condition holds for the array $ a_{i}<=a_{i+1}<=2·a_{i} $ for any positive integer $ i $ ( $ i&lt;n $ ). Vasya wants to add either a "+" or a "-" before each number of array. Thus, Vasya will get an expression consisting of $ n $ summands. The value of the resulting expression is the sum of all its elements. The task is to add signs "+" and "-" before each number so that the value of expression $ s $ meets the limits $ 0<=s<=a_{1} $ . Print a sequence of signs "+" and "-", satisfying the given limits. It is guaranteed that the solution for the problem exists.

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 1<=n<=10^{5} $ ) — the size of the array. The second line contains space-separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=10^{9} $ ) — the original array. It is guaranteed that the condition $ a_{i}<=a_{i+1}<=2·a_{i} $ fulfills for any positive integer $ i $ ( $ i&lt;n $ ).

输出格式


In a single line print the sequence of $ n $ characters "+" and "-", where the $ i $ -th character is the sign that is placed in front of number $ a_{i} $ . The value of the resulting expression $ s $ must fit into the limits $ 0<=s<=a_{1} $ . If there are multiple solutions, you are allowed to print any of them.

输入输出样例

输入样例 #1

4
1 2 3 5

输出样例 #1

+++-

输入样例 #2

3
3 3 5

输出样例 #2

++-

Input

题意翻译

给定一个长度为 $n (1\le n\le 10^5)$ 的数组 $a$,对于任意 $1\le i\le n-1$ 满足 $a_i\le a_{i+1}\le 2\times a_i$。 你的任务是给数组中每个元素前面加一个符号 `+` 或 `-` ,使得它们的和 $s$ 满足 $0\le s \le a_1$,如果有多种解决方案,输出其中一种即可。

加入题单

上一题 下一题 算法标签: