Professor Vasechkin is studying evolution of worms. Recently he put forward hypotheses…
- User
Professor Vasechkin is studying evolution of worms. Recently he put forward hypotheses that all worms evolve by division. There are n forms of worms. Worms of these forms have lengths a1, a2, ..., an. To prove his theory, professor needs to find 3 different forms that the length of the first form is equal to sum of lengths of the other two forms. Help him to do this. Input
The first line contains integer n (3 ≤ n ≤ 100) — amount of worm's forms. The second line contains n space-separated integers ai (1 ≤ ai ≤ 1000) — lengths of worms of each form.
Output
Output 3 distinct integers i j k (1 ≤ i, j, k ≤ n) — such indexes of worm's forms that ai = aj + ak. If there is no such triple, output -1. If there are several solutions, output any of them. It possible that aj = ak.
Examples
Input
5 1 2 3 5 7
Output
3 2 1
Input
5 1 8 1 5 1
Output
-1
Assistant
We need to read the problem: Given n (3 <= n <= 100) and a list of n positive integers (1..1000). We need to find three distinct indices i, j, k such that a_i = a_j + a_k. Note that j and k must be distinct from each other? They say 3 distinct integers i, j, k, so all three indices are distinct. And they say "It possible that aj = ak." But j and k distinct indices, so values can be equal but indices distinct. So we need three different indices such that one's length equals sum of other two.
We need to output any such triple. If none, output -1.
Constraints small: n <= 100, so O(n^3) is acceptable (1e6), but we can also do O(n^2) with hash map.
We must careful: i, j, k must be distinct. So we need to ensure i != j, i != k, j != k.
Simple solution: For each i from 1..n, for each j from 1..n, for each k from 1..n, if i != j != k and a_i == a_j + a_k, output. Complexity O(n^3) = up to 1e6, fine.
But careful about j and k: j != k also required because distinct indices. So we need to check i,j,k all distinct.
Alternatively, we can create a mapping from value to list of indices (positions). Then for each pair (j,k) distinct indices, compute sum = a_j + a_k. Then look up if there exists an index i distinct from j,k such that a_i == sum. Since there could be multiple indices for the same value, we need to find one not equal to j or k. Because mapping from value to list of indices, we can pick an index that is not j or k. Complexity O(n^2) to enumerate pairs.
Given n <= 100, both fine.
Edge Cases: Could be multiple solutions; any is fine.
Implementation details: Input reading, array a (1-indexed probably). Output indices (1-indexed) separated by spaces.
If no solution, output -1.
Example: Input 5, [1,2,3,5,7] -> Output 3 2 1: a3=3, a2=2, a1=1, indeed 3=2+1.
Second: [1,8,1,5,1] no triple.
Note: The problem statement: "output 3 distinct integers i j k (1 ≤ i, j, k ≤ n) — such indexes of worm's forms that ai = aj + ak." So ordering: i is the index of the sum, j and k are the addends. But output order is i j k. Could be any.
Now we need to ensure we don't output same index multiple times.
Let's implement O(n^3) approach for simplicity:
for i in range(n): for j in range(n): for k in range(n): if i != j and i != k and j != k and a[i] == a[j] + a[k]: print(i+1, j+1, k+1) return
If loop completes, print -1.
But careful: We need to ensure j and k distinct, but condition j!=k already covered.
But O(n^3) is okay.
But could there be cases where a[i] = a[j] + a[k] but i equals j or k? That would violate distinctness, but the condition would prevent. So fine.
But there is nuance: if we use three nested loops, we might output j and k in different order than expected but any order is accepted? The problem says output any such triple, but the triple is i j k. So we need to maintain that i is the sum index. In our loops, we are explicitly setting i as the sum index. That's correct.
But we must be careful: We might also find a case where a[j] = a[i] + a[k] or something, but we are only checking a[i] as sum. So we are fine.
But is it possible that a[j] + a[k] equals a[i] but i is same as j? Then condition i!=j will fail.
So algorithm correct.
Potential improvement: We can break early after found.
Now testing with examples:
Example1: n=5, a=[1,2,3,5,7]. loops: i=2 (value 3), j=1 (value2), k=0 (value1) => 3==2+1 true, indices (3,2,1) output => matches.
But careful: Our indices start 0 in code, so print i+1=3, j+1=2, k+1=1 => 3 2 1.
Second example: No triple, so -1.
Edge Cases: n=3: we need to check all three distinct.
But what if there is triple where j and k are the same index? Not allowed because distinct. So we must ensure j!=k.
Now what about scenario where a_i = a_j + a_k and there is multiple possibilities. Our loops will find first in order. Fine.
Now confirm constraints: n up to 100, a up to 1000, sums up to 2000, but we don't care.
Implementation in Python:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) a = list(map(int, data[1:1+n])) for i in range(n): for j in range(n): for k in range(n): if i != j and i != k and j != k and a[i] == a[j] + a[k]: print(i+1, j+1, k+1) return print(-1)
Works.
But maybe we should consider the case where a[i] = a[j] + a[k] but j and k are same value? That's okay as long as indices distinct.
Now let's ensure we handle input correctly. The problem states "The second line contains n space-separated integers ai". So there might be more whitespace, but our split handles.
Test with given examples.
Test1: Input: "5\n1 2 3 5 7\n" => data = ['5','1','2','3','5','7']; n=5; a=[1,2,3,5,7]. Then loops: i=2 (value 3), j=1 (2), k=0 (1) => condition true => print 3 2 1 => correct.
Test2: "5\n1 8 1 5 1\n" => a=[1,8,1,5,1]. Check all triples: likely none => -1.
Now code.
But we should consider that sometimes using Python's O(n^3) with n=100 gives 1,000,000 iterations, each with simple operations. That's fine.
We can also reduce to O(n^2) for practice, but not necessary.
However, there is nuance: The triple must be distinct indices. In the O(n^3) approach we check all.
One potential pitfall: The condition if i != j and i != k and j != k ensures distinctness. That's fine.
But what about case where j and k are swapped? We might output i j k, but any order is acceptable. However, note that the problem says "3 distinct integers i j k (1 ≤ i, j, k ≤ n) — such indexes of worm's forms that ai = aj + ak." So they want i as the sum index. So we should output i as the index of the sum. In our loops we have that. Good.
But what if there exists solution where a_i = a_j + a_k but also a_j = a_i + a_k? That would involve different roles, but we only check the case where the current i is the sum.
Now confirm that j and k can be any order, but we output j then k? The problem says output "i j k". So we output i then j then k. Our print prints i+1, j+1, k+1. That's correct.
Now what about multiple solutions: they say "If there are several solutions, output any of them." So fine.
Edge Cases: Could there be a solution where a_i = a_j + a_k with i=j? That can't happen because then a_i = a_i + a_k implies a_k=0, but a_i >=1. So no.
Similarly i=k leads to a_i = a_j + a_i => a_j=0 impossible. So no need to worry about those.
But j and k could be equal if values equal but indices distinct, but we ensure j!=k.
Now final solution.
But note that we can also store mapping from value to indices. For each pair (j, k) with j<k (distinct), compute sum and look for i in list of indices for sum that is not j or k. Since n small, it's fine.
Let's also think: If there are duplicate values, mapping will help. But O(n^3) also handles duplicates.
Complexities: O(n^3) 1e6, Python will be quick.
We'll implement O(n^3) for simplicity.
But note: In some judges, Python might be slower but 1e6 loops with simple operations is fine (approx <0.1 seconds).
Now final code.
But we must include solve() call if main.
I'll write:
def main(): import sys data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) a = list(map(int, data[1:1+n])) for i in range(n): for j in range(n): for k in range(n): if i != j and i != k and j != k and a[i] == a[j] + a[k]: print(i+1, j+1, k+1) return print(-1)
if name == "main": main()
That's it.
But could there be situation where we get i j k but j>k? That's fine.
Now we should consider the possibility that j and k might be equal indices if we didn't check, but we check.
All good.
Now we are done.
But sometimes problems like this can be solved by sorting, but not needed.
Now write final answer.
Also add comment maybe.
I'll now produce final solution. ```python
import sys
def main() -> None: data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) a = list(map(int, data[1:1 + n]))
# Brute-force over all triples of distinct indices for i in range(n): for j in range(n): for k in range(n): if i != j and i != k and j != k and a[i] == a[j] + a[k]: # indices are 1‑based in the output print(i + 1, j + 1, k + 1) return print(-1)if name == "main": main()