Logaritam
레이팅 미적용의견: 0
Hrvoje has recently learned about the logarithm function. He really likes the
property log(\(xy\)) = log(\(x\)) + log(\(y\)), for each pair of positive real numbers \(x\) and \(y\).
He is actually not interested in the function itself, but in logarithmic sequences.
A logarithmic sequence of length \(n\) is a sequence of real numbers (\(a\)1, a2, . . . , a\(n\))
for which \(a@@RISE_MATH_BLOCK_0@@x + a@@RISE_MATH_BLOCK_1@@i\) of the element Matej had changed in the
\(i-th\) sequence.
Note: It can be proven that for any starting logarithmic sequence the minimal number of changes is the
same.
Subtask 1 (19 points): \(n \le 20\), \(q \le 20\)
Subtask 2 (26 points): \(q \le 8\)
Subtask 3 (29 points): \(n \le 10^{4}\)
Subtask 4 (36 points): No additional constraints.
In the first line there are two positive integers \(n\) and \(q\) (\(1 \le n \le 10^{8}\), \(1 \le q \le 10^{4}\)), the length of each
sequence and the number of sequences.
In the \(i-th\) of the next \(q\) lines there is a positive integer \(x@@RISE_MATH_BLOCK_0@@i \le n\)), the index of the element Matej
had changed in the \(i-th\) sequence.
In the \(i-th\) line outp\(ut -1\) if Hrvoje cannot change the other elements of the \(i-th\) sequence such that the
sequence becomes logarithmic again, otherwise output the minimal number of changes needed to make
the sequence logarithmic again.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 19점 | \(n \le 20\), \(q \le 20\) |
2 | 26점 | \(q \le 8\) |
3 | 29점 | \(n \le 10^{4}\) |
4 | 36점 | No additional constraints. |
6 6
1
2
3
4
5
6-1
2
1
2
0
120 5
7
8
2
19
121
9
9
0
510000 4
1234
2345
3456
789015
148
3332
37Clarification of the first example:
If the starting sequence was 0, 1, π, 2, 0.7, 1 + π and Matej changes the fourth element to 8, Hrvoje can
change the second element to 4 and the sixth to 4 + π, after which the sequence 0, 4, π, 8, 0.7, 4 + π will be
logarithmic again.
평가 및 의견
Logaritam
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Logaritam