PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: tabr, yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N and X, construct a string of length N using the characters +
, -
, *
such that upon evaluation with N+1 ones, the result is X.
Multiplication is performed first, addition second, and subtraction last.
EXPLANATION:
Let’s think about the maximum and minimum values we can achieve.
Clearly, since there are no parentheses,
- The maximum is 1+1+1+\ldots + 1 = N+1
- The minimum is 1-1-1-\ldots - 1 = 1-N
So, if X \gt N+1 or X \lt 1-N, the answer is immediately -1.
Let’s solve for the remaining numbers.
Starting with 1+1+\ldots + 1, notice that replacing one +
with a *
essentially allows us to ‘combine’ two ones into a single one, thereby reducing the sum by 1.
For example,
- 1+1+1+1 = 4
- 1+1+1*1 = 3
- 1+1*1*1 = 2
- 1*1*1*1 = 1
Notice that this allows to create every X between 1 and N+1, by using X-1 occurrences of +
and N-X occurrences of *
.
A similar logic applies to the non-positive numbers, where we can start with 1-1-1-\ldots -1, and replace a -
with a *
to increase the sum by 1. For example,
- 1-1-1-1 = -2
- 1-1-1*1 = -1
- 1-1*1*1 = 0
In particular, -X can be obtained using X+1 occurrences of -
and N-X-1 occurrences of *
.
This means we can obtain every X in the range [1-N, N+1], and so we’re done.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
if x > 0:
if x > n+1: print(-1)
else: print('*'*(n-x+1) + '+'*(x-1))
else:
x = -x
if x > n-1: print(-1)
else: print('-'*(1+x) + '*'*(n-1-x))