Sum of Three Values
Solución
Explicación
Este problema es una extensión del problema de la suma de dos valores (two sum), ahora con tres valores. Podemos fijar el tercer puntero en cierto valor del arreglo y entonces el problema se convierte en el de la suma de dos valores discutido antes en este módulo.
Primero ordenaremos el arreglo. Luego recorremos todos los valores posibles para el
tercer puntero y comprobamos si los tres punteros suman la cantidad objetivo, ,
teniendo posiciones distintas. Podemos mantener las posiciones originales de todos
los valores guardando los pares {a[i],i}.
Implementación
Complejidad temporal:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
vector<pair<int, int>> arr;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
pair<int, int> p;
p.first = a;
p.second = i;
// el primero del par representa el valor, el segundo el índice
arr.push_back(p);
}
sort(begin(arr), end(arr));
for (int i = 0; i < n; i++) {
int l, r;
l = 0;
r = n - 1;
while (l != r) {
int target;
target = x - arr.at(i).first;
if (l != i && r != i && arr.at(l).first + arr.at(r).first == target) {
cout << arr.at(i).second << " " << arr.at(l).second << " "
<< arr.at(r).second << endl;
return 0;
}
if (arr.at(l).first + arr.at(r).first < target) {
l++;
} else {
r--;
}
}
}
cout << "IMPOSSIBLE" << endl;
}import java.io.*;
import java.util.*;
public class SumOfThreeValues {
static class Group implements Comparable<Group> {
int value, index;
Group(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Group other) {
return Integer.compare(this.value, other.value);
}
}
public static void main(String[] args) {
Kattio io = new Kattio();
int n = io.nextInt();
int x = io.nextInt();
Group[] data = new Group[n];
for (int i = 1; i <= n; i++) {
// guardamos la entrada en una clase que tiene un valor y un índice
int value = io.nextInt();
Group group = new Group(value, i);
data[i - 1] = group;
}
Arrays.sort(data); // dejamos los valores en orden creciente
for (int i = 0; i < n; i++) {
int left = 0;
int right = n - 1;
while (left != right) {
int target = x - data[i].value;
// si los tres valores suman el objetivo y no provienen del
// mismo índice, encontramos nuestra respuesta
if (left != i && right != i &&
data[left].value + data[right].value == target) {
// tenemos una respuesta, la imprimimos
io.println(data[i].index + " " + data[left].index + " " +
data[right].index);
io.close();
System.exit(0); // ya podemos terminar el programa
}
// no es igual al objetivo: aumentamos left si la suma es menor
if (data[left].value + data[right].value < target) {
left++;
}
// no es igual al objetivo: disminuimos right si la suma
// es mayor que el objetivo
else {
right--;
}
}
}
// imprimimos IMPOSSIBLE si llegamos al final sin respuesta
io.println("IMPOSSIBLE");
io.close();
}
// CodeSnip{Kattio}
}n, x = map(int, input().split())
a = list(map(int, input().split()))
p = [(a[i], i + 1) for i in range(n)]
p.sort()
for i in range(n):
left = 0
right = n - 1
while left < right:
target = x - p[i][0]
"""
si los valores suman el objetivo y no provienen del mismo índice,
encontramos la respuesta
"""
if left != i and right != i and p[left][0] + p[right][0] == target:
print(p[left][1], p[right][1], p[i][1])
exit()
# aumentamos left si la suma es menor
elif p[left][0] + p[right][0] < target:
left += 1
# en caso contrario disminuimos right
else:
right -= 1
print("IMPOSSIBLE")