You are given a list of n integers a_1, a_2, …, a_n and q commands.
One command has the form "direction operation initial-value".
An operation is a function that makes one value from two integers x and y, and there are five of them.
add is x + y, sub is x - y, max is the larger of the two, min is the smaller of the two, and gap is the absolute value of x - y.
If the direction is L, do a left fold. Start a value v at the initial value and, going from a_1 to a_n in order, replace v with operation(v, a_i).
If the direction is R, do a right fold. Start a value v at the initial value and, going backwards from a_n to a_1, replace v with operation(a_i, v).
In a right fold the list element goes in the first place of the operation and the value so far goes in the second place.
For each command, find v when the fold is finished.
Solve it by writing one fold function per direction that receives the list, an operation function and the initial value, and by choosing the function that matches the operation name and passing it in.
The list in the example is 5 2 4.
"L sub 20" is ((20 - 5) - 2) - 4 = 9, and "R sub 20" is 5 - (2 - (4 - 20)) = -13.
For "L gap 0" v becomes 5, 3, 1, so the answer is 1, and for "R gap 0" v becomes 4, 2, 3, so the answer is 3.
Input
The first line has n and q separated by a space. The second line has a_1 to a_n separated by single spaces. Each of the next q lines has one command: the direction (L or R), the operation name (one of add, sub, max, min, gap) and the initial value, separated by single spaces. 1 ≤ n ≤ 1,000, 1 ≤ q ≤ 200, -1,000,000,000 ≤ a_i ≤ 1,000,000,000, -1,000,000,000 ≤ initial value ≤ 1,000,000,000
Output
For each command, in the order given, print the answer on its own line. Write numbers as plain digits without commas
Example 1 · stdin
3 5
5 2 4
L sub 20
R sub 20
L gap 0
R gap 0
L max -7
stdout
9
-13
1
3
5
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Languages differ in how a function is handled as a value. Here the functions go into a 'name → function' table and are passed to the fold function as an argument. In Python a function's name is already a value, so built-ins go in as they are: {"add": operator.add, "max": max}. JS and TS use arrow functions (p, q) => p - q. Java stores a lambda or a method reference such as Long::sum or Math::max in a LongBinaryOperator and calls it with f.applyAsLong(p, q). C# stores a lambda or Math.Max in a Func<long, long, long>. C uses a function pointer long long (*f)(long long, long long), and C++ stores lambdas in std::function. Craykon has no lambdas, so define named functions, store one by writing its name without parentheses, as in ops["sub"] = Minus;, and call it with f(acc, x). Trap one: a right fold changes not only the direction of travel but also the argument places. Going from the right but calling f(v, a_i) turns the example's R sub 20 into ((20 - 4) - 2) - 5 = 9 (the answer is -13). JS reduceRight also calls f(value so far, element), so using it as it is goes wrong this way. Swapping only the argument places while still going from the left is wrong too, and so is ignoring L and R. Trap two: in JS do not pass a built-in directly, as in list.reduce(Math.max, init). reduce passes four things to the function (value so far, element, index, array) and Math.max turns everything it receives into numbers and compares them all, so the result is NaN (the example's L max -7). Wrap it in an arrow function that takes just two. Trap three: do not leave out the initial value. Python's functools.reduce(f, items) starts from the first element when no initial value is given, so the example's L sub 20 becomes (5 - 2) - 4 = -1 instead of 9. Trap four: adding 1,000 numbers of a billion each makes a trillion, past 32 bits. Fold in long in Java and C#, long long in C and C++. In C++, keeping the value so far in an int silently gives a wrong number. Python integers have no limit, and JS, TS and Craykon numbers are exact up to 2^53.
Pythonmain.py · 33 lines
import sysfrom operator import add, subdef gap(p, q): return abs(p - q)# 이름 → 함수. 함수도 값이라서 사전에 넣을 수 있다 (max, min은 내장 함수 그대로)OPS = {"add": add, "sub": sub, "max": max, "min": min, "gap": gap}def fold_left(items, f, init): acc = init for x in items: acc = f(acc, x) # 지금까지의 값이 왼쪽 return accdef fold_right(items, f, init): acc = init for x in reversed(items): acc = f(x, acc) # 지금까지의 값이 오른쪽 return accdef main(): lines = sys.stdin.read().split("\n") n, q = map(int, lines[0].split()) items = [int(v) for v in lines[1].split()] out = [] for line in lines[2:2 + q]: side, name, init = line.split() fold = fold_left if side == "L" else fold_right out.append(fold(items, OPS[name], int(init))) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 32 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items = lines[1].trim().split(/\s+/).map(Number);// 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS = { add: (p, q) => p + q, sub: (p, q) => p - q, max: (p, q) => Math.max(p, q), min: (p, q) => Math.min(p, q), gap: (p, q) => Math.abs(p - q),};function foldLeft(list, f, init) { let acc = init; for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc;}function foldRight(list, f, init) { let acc = init; for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽 return acc;}const out = [];for (let k = 0; k < q; k++) { const [side, name, init] = lines[2 + k].trim().split(/\s+/); const fold = side === "L" ? foldLeft : foldRight; out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
TypeScriptmain.ts · 37 lines
import { readFileSync } from "node:fs";type Op = (p: number, q: number) => number;type Fold = (list: number[], f: Op, init: number) => number;const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items: number[] = lines[1].trim().split(/\s+/).map(Number);// 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS: Record<string, Op> = { add: (p, q) => p + q, sub: (p, q) => p - q, max: (p, q) => Math.max(p, q), min: (p, q) => Math.min(p, q), gap: (p, q) => Math.abs(p - q),};const foldLeft: Fold = (list, f, init) => { let acc = init; for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc;};const foldRight: Fold = (list, f, init) => { let acc = init; for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽 return acc;};const out: number[] = [];for (let k = 0; k < q; k++) { const [side, name, init] = lines[2 + k].trim().split(/\s+/); const fold: Fold = side === "L" ? foldLeft : foldRight; out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
JavaMain.java · 48 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.StringTokenizer;import java.util.function.LongBinaryOperator;public class Main { static long foldLeft(long[] items, LongBinaryOperator f, long init) { long acc = init; for (long x : items) acc = f.applyAsLong(acc, x); // 지금까지의 값이 왼쪽 return acc; } static long foldRight(long[] items, LongBinaryOperator f, long init) { long acc = init; for (int i = items.length - 1; i >= 0; i--) acc = f.applyAsLong(items[i], acc); // 지금까지의 값이 오른쪽 return acc; } public static void main(String[] args) throws Exception { // 이름 → 함수. 이미 있는 메서드는 Long::sum처럼, 없는 것은 람다로 적는다 Map<String, LongBinaryOperator> ops = new HashMap<>(); ops.put("add", Long::sum); ops.put("sub", (p, q) -> p - q); ops.put("max", Math::max); ops.put("min", Math::min); ops.put("gap", (p, q) -> Math.abs(p - q)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] items = new long[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) items[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); String side = st.nextToken(); LongBinaryOperator f = ops.get(st.nextToken()); long init = Long.parseLong(st.nextToken()); out.append(side.equals("L") ? foldLeft(items, f, init) : foldRight(items, f, init)).append('\n'); } System.out.print(out); }}
C#Main.cs · 47 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static long FoldLeft(long[] items, Func<long, long, long> f, long init) { long acc = init; foreach (long x in items) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc; } static long FoldRight(long[] items, Func<long, long, long> f, long init) { long acc = init; for (int i = items.Length - 1; i >= 0; i--) acc = f(items[i], acc); // 지금까지의 값이 오른쪽 return acc; } static void Main() { // 이름 → 함수. Math.Max는 형이 여러 가지라 Func<long, long, long>에 넣으면 long용이 골라진다 var ops = new Dictionary<string, Func<long, long, long>> { ["add"] = (p, q) => p + q, ["sub"] = (p, q) => p - q, ["max"] = Math.Max, ["min"] = Math.Min, ["gap"] = (p, q) => Math.Abs(p - q), }; string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int q2 = int.Parse(first[1]); long[] items = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int k = 0; k < q2; k++) { string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); Func<long, long, long> f = ops[parts[1]]; long init = long.Parse(parts[2]); sb.Append(parts[0] == "L" ? FoldLeft(items, f, init) : FoldRight(items, f, init)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 47 lines
#include <algorithm>#include <cstdlib>#include <functional>#include <iostream>#include <map>#include <string>#include <vector>using Op = std::function<long long(long long, long long)>;long long foldLeft(const std::vector<long long> &items, const Op &f, long long init) { long long acc = init; for (long long x : items) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc;}long long foldRight(const std::vector<long long> &items, const Op &f, long long init) { long long acc = init; for (auto it = items.rbegin(); it != items.rend(); ++it) acc = f(*it, acc); // 지금까지의 값이 오른쪽 return acc;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); // 이름 → 함수. 람다를 std::function에 담는다 const std::map<std::string, Op> ops = { {"add", [](long long p, long long q) { return p + q; }}, {"sub", [](long long p, long long q) { return p - q; }}, {"max", [](long long p, long long q) { return std::max(p, q); }}, {"min", [](long long p, long long q) { return std::min(p, q); }}, {"gap", [](long long p, long long q) { return std::llabs(p - q); }}, }; int n, q; std::cin >> n >> q; std::vector<long long> items(n); for (auto &x : items) std::cin >> x; for (int k = 0; k < q; k++) { std::string side, name; long long init; std::cin >> side >> name >> init; const Op &f = ops.at(name); std::cout << (side == "L" ? foldLeft(items, f, init) : foldRight(items, f, init)) << '\n'; }}
Cmain.c · 46 lines
#include <stdio.h>#include <string.h>/* 함수를 가리키는 포인터의 형: long long 둘을 받아 long long을 돌려주는 함수 */typedef long long (*Op)(long long, long long);long long op_add(long long p, long long q) { return p + q; }long long op_sub(long long p, long long q) { return p - q; }long long op_max(long long p, long long q) { return p > q ? p : q; }long long op_min(long long p, long long q) { return p < q ? p : q; }long long op_gap(long long p, long long q) { return p > q ? p - q : q - p; }/* 이름 → 함수 표 */struct { const char *name; Op f; } OPS[] = { {"add", op_add}, {"sub", op_sub}, {"max", op_max}, {"min", op_min}, {"gap", op_gap},};long long fold_left(const long long *items, int n, Op f, long long init) { long long acc = init; for (int i = 0; i < n; i++) acc = f(acc, items[i]); /* 지금까지의 값이 왼쪽 */ return acc;}long long fold_right(const long long *items, int n, Op f, long long init) { long long acc = init; for (int i = n - 1; i >= 0; i--) acc = f(items[i], acc); /* 지금까지의 값이 오른쪽 */ return acc;}long long items[1000];int main(void) { int n, q; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%lld", &items[i]); for (int k = 0; k < q; k++) { char side[4], name[8]; long long init; scanf("%3s %7s %lld", side, name, &init); Op f = NULL; for (int j = 0; j < 5; j++) if (strcmp(OPS[j].name, name) == 0) f = OPS[j].f; printf("%lld\n", side[0] == 'L' ? fold_left(items, n, f, init) : fold_right(items, n, f, init)); } return 0;}
Craykonmain.cray · 70 lines
더하기(p, q){ return p + q;}덜기(p, q){ return p - q;}큰쪽(p, q){ return Mathf.Max(p, q);}작은쪽(p, q){ return Mathf.Min(p, q);}차이(p, q){ return Mathf.Abs(p - q);}// 이름 → 함수. 함수 이름을 괄호 없이 쓰면 함수 자체가 값이 된다ops = Dict();ops["add"] = 더하기;ops["sub"] = 덜기;ops["max"] = 큰쪽;ops["min"] = 작은쪽;ops["gap"] = 차이;왼쪽접기(items, f, init){ acc = init; foreach (x in items) { acc = f(acc, x); // 지금까지의 값이 왼쪽 } return acc;}오른쪽접기(items, f, init){ acc = init; for (i = items.Count - 1; i >= 0; i--) { acc = f(items[i], acc); // 지금까지의 값이 오른쪽 } return acc;}첫줄 = Console.ReadNumbers();q = 첫줄[1];items = Console.ReadNumbers();for (k = 0; k < q; k++){ parts = Console.ReadLine().Split(" "); f = ops[parts[1]]; init = parts[2].ToNumber(); if (parts[0] == "L") { Console.WriteLine(왼쪽접기(items, f, init)); } else { Console.WriteLine(오른쪽접기(items, f, init)); }}