Measuring Traffic
Implementación
Complejidad temporal
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
// Un número arbitrario grande comparado con los del problema.
const int LARGE = 1e9;
int main() {
std::ifstream read("traffic.in");
int num_miles;
read >> num_miles;
vector<std::string> segment_type(num_miles);
vector<int> start(num_miles);
vector<int> end(num_miles);
for (int m = 0; m < num_miles; m++) {
read >> segment_type[m] >> start[m] >> end[m];
}
// Fijamos un rango grande que viene a ser [0, infinito)
int low = 0;
int high = LARGE;
for (int m = num_miles - 1; m >= 0; m--) {
if (segment_type[m] == "none") {
// Fijamos un rango nuevo según la lectura del sensor.
low = std::max(low, start[m]);
high = std::min(high, end[m]);
} else if (segment_type[m] == "off") {
// Actualizamos el rango de flujos de tráfico posibles
low += start[m];
high += end[m];
} else if (segment_type[m] == "on") {
low -= end[m];
high -= start[m];
// Lo ponemos en cero si low se vuelve negativo
low = std::max(0, low);
}
}
std::ofstream write("traffic.out");
write << low << ' ' << high << endl;
low = 0;
high = LARGE;
// Procesamos de nuevo, esta vez recorriendo en el otro sentido
for (int m = 0; m < num_miles; m++) {
if (segment_type[m] == "none") {
low = std::max(low, start[m]);
high = std::min(high, end[m]);
} else if (segment_type[m] == "on") {
low += start[m];
high += end[m];
} else if (segment_type[m] == "off") {
low -= end[m];
high -= start[m];
low = std::max(0, low);
}
}
write << low << ' ' << high << endl;
}import java.io.*;
import java.util.*;
public class MeasuringTraffic {
// Un número arbitrario grande comparado con los del problema.
static final int LARGE = (int)1e9;
public static void main(String[] args) throws IOException {
Kattio io = new Kattio("traffic");
int numMiles = io.nextInt();
String[] segmentType = new String[numMiles];
int[] start = new int[numMiles];
int[] end = new int[numMiles];
for (int m = 0; m < numMiles; m++) {
segmentType[m] = io.next();
start[m] = io.nextInt();
end[m] = io.nextInt();
}
// Fijamos un rango grande que viene a ser [0, infinito)
int low = 0;
int high = LARGE;
for (int m = numMiles - 1; m >= 0; m--) {
if (segmentType[m].equals("none")) {
// Fijamos un rango nuevo según la lectura del sensor.
low = Math.max(low, start[m]);
high = Math.min(high, end[m]);
} else if (segmentType[m].equals("off")) {
// Actualizamos el rango de flujos de tráfico posibles
low += start[m];
high += end[m];
} else if (segmentType[m].equals("on")) {
low -= end[m];
high -= start[m];
// Lo ponemos en cero si low se vuelve negativo
low = Math.max(0, low);
}
}
io.println(low + " " + high);
low = 0;
high = LARGE;
// Procesamos de nuevo, esta vez recorriendo en el otro sentido
for (int m = 0; m < numMiles; m++) {
if (segmentType[m].equals("none")) {
low = Math.max(low, start[m]);
high = Math.min(high, end[m]);
} else if (segmentType[m].equals("on")) {
low += start[m];
high += end[m];
} else if (segmentType[m].equals("off")) {
low -= end[m];
high -= start[m];
low = Math.max(0, low);
}
}
io.println(low + " " + high);
io.close();
}
// CodeSnip{Kattio}
}with open("traffic.in") as read:
num_miles = int(read.readline())
segment_type = []
start = []
end = []
for m in range(num_miles):
curr_type, s, e = read.readline().split()
segment_type.append(curr_type)
start.append(int(s))
end.append(int(e))
low = 0
high = float("inf")
for m in range(num_miles - 1, -1, -1):
if segment_type[m] == "none":
# Fijamos un rango nuevo según la lectura del sensor.
low = max(low, start[m])
high = min(high, end[m])
elif segment_type[m] == "off":
# Actualizamos el rango de flujos de tráfico posibles
low += start[m]
high += end[m]
elif segment_type[m] == "on":
low -= end[m]
high -= start[m]
# Lo ponemos en cero si low se vuelve negativo
low = max(0, low)
write = open("traffic.out", "w")
print(low, high, file=write)
low = 0
high = float("inf")
# Procesamos de nuevo, esta vez recorriendo en el otro sentido
for m in range(num_miles):
if segment_type[m] == "none":
low = max(low, start[m])
high = min(high, end[m])
elif segment_type[m] == "on":
low += start[m]
high += end[m]
elif segment_type[m] == "off":
low -= end[m]
high -= start[m]
low = max(0, low)
print(low, high, file=write)Solución en video
Por Jay Fu
Video de YouTube (RZBnIYC3GTw)
Código de la solución en video
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
int main() {
int N, A[100], B[100];
string T[100];
ifstream fin("traffic.in");
fin >> N;
for (int i = 0; i < N; i++) { fin >> T[i] >> A[i] >> B[i]; }
ofstream fout("traffic.out");
// Abajo está el rango inicial [a,b]. Vamos a estrechar/modificar este rango a
// medida que recorremos los componentes de la carretera de la milla N a la milla 1.
// El rango resultante será el rango de flujos de tráfico iniciales posibles.
int a = 0, b = 999999999;
// Notemos que recorremos hacia atrás, de la milla N a la milla 1.
for (int i = N - 1; i >= 0; i--) {
// si no hay rampa, el rango posible [a,b] se
// estrecha al rango dado por el sensor.
if (T[i] == "none") {
a = max(a, A[i]);
b = min(b, B[i]);
}
// si hay una rampa de salida con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a+a',b+b']
if (T[i] == "off") {
a += A[i];
b += B[i];
}
// si hay una rampa de entrada con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a-b',b-a']
if (T[i] == "on") {
a -= B[i];
b -= A[i];
a = max(0, a);
}
}
// Imprimimos el rango de flujos de tráfico iniciales posibles.
fout << a << " " << b << "\n";
// Abajo está el rango inicial [a,b]. Vamos a estrechar/modificar este rango a
// medida que recorremos los componentes de la carretera de la milla 1 a la milla N.
// El rango resultante será el rango de flujos de tráfico finales posibles.
a = 0, b = 999999999;
for (int i = 0; i < N; i++) {
// si no hay rampa, el rango posible [a,b] se
// estrecha al rango dado por el sensor.
if (T[i] == "none") {
a = max(a, A[i]);
b = min(b, B[i]);
}
// si hay una rampa de entrada con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a+a',b+b']
if (T[i] == "on") {
a += A[i];
b += B[i];
}
// si hay una rampa de salida con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a-b',b-a']
if (T[i] == "off") {
a -= B[i];
b -= A[i];
a = max(0, a);
}
}
fout << a << " " << b << "\n";
return 0;
}import java.io.*;
import java.util.StringTokenizer;
public class traffic {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("traffic.in"));
PrintWriter pw = new PrintWriter("traffic.out");
int N = Integer.parseInt(br.readLine());
int[] A = new int[100];
int[] B = new int[100];
String[] T = new String[100];
for (int i = 0; i < N; i++) {
StringTokenizer s = new StringTokenizer(br.readLine());
T[i] = s.nextToken();
A[i] = Integer.parseInt(s.nextToken());
B[i] = Integer.parseInt(s.nextToken());
}
PrintWriter out = new PrintWriter("traffic.out");
// Abajo está el rango inicial [a,b]. Vamos a estrechar/modificar este rango a
// medida que recorremos los componentes de la carretera de la milla N a la milla 1.
// El rango resultante será el rango de flujos de tráfico
// iniciales posibles.
int a = 0;
int b = 999999999;
// Notemos que recorremos hacia atrás, de la milla N a la milla 1.
for (int i = N - 1; i >= 0; i--) {
// si no hay rampa, el rango posible [a,b] se
// estrecha al rango dado por el sensor.
if (T[i].equals("none")) {
a = Math.max(a, A[i]);
b = Math.min(b, B[i]);
}
// si hay una rampa de salida con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a+a',b+b']
if (T[i].equals("off")) {
a += A[i];
b += B[i];
}
// si hay una rampa de entrada con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a-b',b-a']
if (T[i].equals("on")) {
a -= B[i];
b -= A[i];
a = Math.max(0, a);
}
}
// Imprimimos el rango de flujos de tráfico iniciales posibles.
out.println(a + " " + b);
// Abajo está el rango inicial [a,b]. Vamos a estrechar/modificar este rango a
// medida que recorremos los componentes de la carretera de la milla 1 a la milla N.
// El rango resultante será el rango de flujos de tráfico
// finales posibles.
a = 0;
b = 999999999;
for (int i = 0; i < N; i++) {
// si no hay rampa, el rango posible [a,b] se
// estrecha al rango dado por el sensor.
if (T[i].equals("none")) {
a = Math.max(a, A[i]);
b = Math.min(b, B[i]);
}
// si hay una rampa de entrada con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a+a',b+b']
if (T[i].equals("on")) {
a += A[i];
b += B[i];
}
// si hay una rampa de salida con rango [a',b'],
// el nuevo rango de flujos de tráfico posibles es [a-b',b-a']
if (T[i].equals("off")) {
a -= B[i];
b -= A[i];
a = Math.max(0, a);
}
}
out.println(a + " " + b);
out.close();
}
}