Problema electromovil

Problemas Selectivo
#1

Hola, estoy resolviendo este problema.
Mi idea es la siguiente:
Primero, me fijo hasta qué ubicación puedo llegar desde mi posición actual, sin recargar batería en ninguna estación. Al mismo tiempo, me fijo cual es la estación en el rango [posición actual+1;hasta cuál puedo llegar] que más me conviene (esta es la que maximiza la suma de su ubicación y la recarga de la batería que se puede hacer en ella). Luego, hago lo mismo, pero ahora mi posición actual es la estación que más me conviene en el rango anteriormente nombrado.
Dejo el código:

Código 
#include <vector>
#include <iostream>

using namespace std;

typedef long long tint;

vector<int> electromovil(int E, vector<int> ubicacion, vector<int> autonomia)
{
    vector<int> ret;
    int bat = autonomia[0];
    int posAct = 0;
    int pos = 0, maxi = 0;
    for(int i=(posAct+1);i<E;i++){
		if(ubicacion[i] > posAct+bat){
			ret.push_back(ubicacion[pos]);
			posAct = pos;
			bat = autonomia[pos];
			maxi = 0;
			pos = 0;
		}else{
			if(ubicacion[i]+autonomia[i] > maxi){
				maxi = ubicacion[i]+autonomia[i];
				pos = i;
			}
		}
	}
    return ret;
}

Sin embargo, esta solución no funciona, ya que si corro el siguiente ejemplo:
10
0 300
100 800
300 300
700 200
800 400
900 200
1100 500
1200 400
1600 400
2000 8192

el output es el siguiente:
6
100
800
0
0
0
0
Alguien podría decirme dónde está el error en mi solución?

1 me gusta
#2

La idea entiendo que está bien :grinning:. La implementación por otro lado tiene algunos detalles :thinking:.

Detalle 1

Fijate que en el lado derecho estás sumando posAct+bat, el primero parece ser un índice, el segundo parece ser una cantidad en kilómetros. Entiendo que querés ubicacion[posAct].

Detalle 2

Otra cosa que creo que tampoco estaría siendo tenida en cuenta es qué ocurriría en un caso donde no se puede alcanzar la salida (el enunciado dice que en esos casos hay que devolver un arreglo vacío).

Detalle 3

Me parece que cuando una de las estaciones que tenés que elegir es la primera de uno de estos rangos no lo estarías implementando bien (salvo al comenzar), pero no le corrí un ejemplo, solo mirando el código. Entiendo que uno siempre quiere hacer el chequeo que está en el else, no veo por qué no hacerlo cuando se cambia de rango (o en caso de hacerlo, creo que maxi y pos no deberían volver a 0).

Fijate de correrle casos donde ocurran esas cosas.

1 me gusta
#3

Hola,
Muchas gracias por la respuesta! Obtuve 96 puntos, solo me falta implementar el caso en el que no se pueda llegar a la salida.
Dejo el código.

Resumen 
#include <vector>
#include <iostream>

using namespace std;

typedef long long tint;

vector<int> electromovil(int E, vector<int> ubicacion, vector<int> autonomia)
{
    vector<int> ret;
    if(E == 2){
		if(ubicacion[0]+autonomia[0] < ubicacion[1]){
			ret.clear();
			return ret;
		}else{
			ret.push_back(ubicacion[1]);
			return ret;
		}
	}
    int bat = autonomia[0];
    int posAct = 0;
    int pos = 0, maxi = 0;
    for(int i=(posAct+1);i<E;i++){
		if(ubicacion[i] > ubicacion[posAct]+bat){
			ret.push_back(ubicacion[pos]);
			posAct = pos;
			bat = autonomia[pos];
			maxi = 0;
			pos = 0;
		}
		if(ubicacion[i]+autonomia[i] > maxi){
			maxi = ubicacion[i]+autonomia[i];
			pos = i;
		}
	}
	ret.push_back(ubicacion[E-1]);
    return ret;
}
2 Me gusta