You are given the prices p_1, p_2, …, p_n of an item over n days, in day order.
A trading robot can hold only one of this item at a time, and at first it holds none.
Every day the robot looks at that day's price p and follows exactly one of the rules below.
On a day when it is holding the item, let c be the price it bought at and h the highest price from the day it bought through yesterday; it does one of these three.
Rule 1: if p is at least c + g, it sells at p.
Rule 2: if rule 1 does not apply and p is at most h - w, it sells at p. If p is then less than c, it has lost money, so it rests for k days starting the next day.
Rule 3: if neither applies, it does not sell, and if p is greater than h it raises h to p.
On a day when it is not holding the item, it does one of these two.
Rule 4: if rest days remain, it does nothing whatever the price is, and the remaining rest days go down by one.
Rule 5: if no rest days remain and p is at most B, it buys at p. Then c and h both become p. If p is greater than B, it does nothing.
On a day when it sells, it does not buy again even if the price is at most B.
That is because a day when it sells is a day it started holding the item.
Find the robot's record of buying and selling in day order, the profit obtained by adding up the selling price minus the buying price for every sale, and whether it is holding the item after the last day.
In the example B = 50, g = 20, w = 10, k = 2.
It buys at 48 on day 2, h becomes 55 on day 3, and on day 4 the price 44 is at most 55 - 10, so it sells, and since that is a loss it rests on days 5 and 6.
It buys at 50 on day 7 and sells at 70 on day 8.
It buys at 30 on day 9, h becomes 42 on day 10, and on day 11 the price 32 is at most 42 - 10, so it sells.
This time there is no loss, so it does not rest, but it does not buy on day 11 because it sold that day, and it buys at 31 on day 12.
The profit is -4 + 20 + 2 = 18.
Input
The first line has n, B, g, w and k separated by spaces. The second line has p_1 to p_n separated by single spaces. All are integers. 1 ≤ n ≤ 10,000, 1 ≤ B ≤ 100,000, 1 ≤ g ≤ 100,000, 1 ≤ w ≤ 100,000, 0 ≤ k ≤ 100, 1 ≤ p_i ≤ 100,000
Output
For every day on which the robot buys or sells, print one line, in day order. Write a buying day as "buy day price" and a selling day as "sell day price", counting days from 1. On the last line print the profit and then 1 if it is holding the item after the last day or 0 if not, separated by a space. Write numbers as plain digits without commas
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
The rules first split into 'holding day / not-holding day' and then split again inside, so write exactly that shape: an if … else if … else inside an outer if … else. The skeleton is the same in every language and only the words differ. Python uses elif and indentation, JS, TS, C, C++, Java and C# use else if and braces, and Craykon uses if … else if … else. Trap one: do not write the outer split without else, as two separate ifs if (holding) { … } and if (not holding) { … }. After a sale in the first if, the second condition has become true, so rule 4 or 5 also runs on the same day. On day 11 of the example it sells at 32 and at once buys again at 32, and on day 4 the selling day is counted as a rest day, so it buys at 45 on day 6. else does not mean 'when the condition above is false now' but 'when the branch above was not taken'. Trap two: the inner if that checks for a loss exists only inside rule 2. Leaving it out and resting after every rule 2 sale makes the robot rest two days after day 11 of the example, so it cannot buy on day 12. Selling at exactly the buying price is not a loss (<, not <=). Trap three: rest days are counted from the day after the sale. Counting the selling day as a rest day leaves one day too few, and it buys at 45 on day 6 of the example. Trap four: h goes up only in rule 3 and returns to the buying price at every purchase. Forgetting to raise it means no sale on day 4 of the example, and not resetting it at a purchase leaves the last trade's high of 55, so it sells at 42 on day 10. Trap five: every boundary is 'at least' or 'at most'. In the example, 50 on day 7 (= B), 70 on day 8 (= c + g) and 32 on day 11 (= h - w) all sit exactly on a boundary. The profit is at most about 500 million, so it fits in a 32-bit integer.
Pythonmain.py · 39 lines
import sysdef main(): data = sys.stdin.read().split() n, B, g, w, k = (int(v) for v in data[:5]) prices = [int(v) for v in data[5:5 + n]] holding = False cost = 0 # 산 값 high = 0 # 산 날부터 지금까지 가장 높았던 값 rest = 0 # 남은 쉬는 날 수 profit = 0 out = [] for day, p in enumerate(prices, start=1): if holding: if p >= cost + g: # 규칙 1: 이익 실현 out.append(f"sell {day} {p}") profit += p - cost holding = False elif p <= high - w: # 규칙 2: 고점에서 w 이상 내려옴 out.append(f"sell {day} {p}") profit += p - cost holding = False if p < cost: # 손해를 보고 팔았을 때만 쉰다 rest = k else: # 규칙 3: 그대로 들고 간다 high = max(high, p) else: # 판 날에는 이쪽으로 오지 않는다 if rest > 0: # 규칙 4: 쉬는 날 rest -= 1 elif p <= B: # 규칙 5: 산다 out.append(f"buy {day} {p}") holding = True cost = p high = p out.append(f"{profit} {1 if holding else 0}") print("\n".join(out))main()
JavaScriptmain.js · 42 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const [n, B, g, w, k] = data;let holding = false;let cost = 0; // 산 값let high = 0; // 산 날부터 지금까지 가장 높았던 값let rest = 0; // 남은 쉬는 날 수let profit = 0;const out = [];for (let day = 1; day <= n; day++) { const p = data[4 + day]; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = Math.max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { rest--; // 규칙 4: 쉬는 날 } else if (p <= B) { // 규칙 5: 산다 out.push(`buy ${day} ${p}`); holding = true; cost = p; high = p; } }}out.push(`${profit} ${holding ? 1 : 0}`);console.log(out.join("\n"));
TypeScriptmain.ts · 43 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const [n, B, g, w, k] = data;let holding = false;let cost = 0; // 산 값let high = 0; // 산 날부터 지금까지 가장 높았던 값let rest = 0; // 남은 쉬는 날 수let profit = 0;const out: string[] = [];for (let day = 1; day <= n; day++) { const p = data[4 + day]; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = Math.max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { rest--; // 규칙 4: 쉬는 날 } else if (p <= B) { // 규칙 5: 산다 out.push(`buy ${day} ${p}`); holding = true; cost = p; high = p; } }}out.push(`${profit} ${holding ? 1 : 0}`);console.log(out.join("\n"));
JavaMain.java · 51 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;public class Main { public static void main(String[] args) throws Exception { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); int[] head = new int[5]; for (int i = 0; i < 5; i++) { in.nextToken(); head[i] = (int) in.nval; } int n = head[0], B = head[1], g = head[2], w = head[3], k = head[4]; boolean holding = false; int cost = 0; // 산 값 int high = 0; // 산 날부터 지금까지 가장 높았던 값 int rest = 0; // 남은 쉬는 날 수 int profit = 0; StringBuilder out = new StringBuilder(); for (int day = 1; day <= n; day++) { in.nextToken(); int p = (int) in.nval; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 out.append("sell ").append(day).append(' ').append(p).append('\n'); profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 out.append("sell ").append(day).append(' ').append(p).append('\n'); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = Math.max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { // 규칙 4: 쉬는 날 rest--; } else if (p <= B) { // 규칙 5: 산다 out.append("buy ").append(day).append(' ').append(p).append('\n'); holding = true; cost = p; high = p; } } } out.append(profit).append(' ').append(holding ? 1 : 0).append('\n'); System.out.print(out); }}
C#Main.cs · 58 lines
using System;using System.Text;class Program{ static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), B = int.Parse(data[1]), g = int.Parse(data[2]), w = int.Parse(data[3]), k = int.Parse(data[4]); bool holding = false; int cost = 0; // 산 값 int high = 0; // 산 날부터 지금까지 가장 높았던 값 int rest = 0; // 남은 쉬는 날 수 int profit = 0; var sb = new StringBuilder(); for (int day = 1; day <= n; day++) { int p = int.Parse(data[4 + day]); if (holding) { if (p >= cost + g) // 규칙 1: 이익 실현 { sb.Append("sell ").Append(day).Append(' ').Append(p).Append('\n'); profit += p - cost; holding = false; } else if (p <= high - w) // 규칙 2: 고점에서 w 이상 내려옴 { sb.Append("sell ").Append(day).Append(' ').Append(p).Append('\n'); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else // 규칙 3: 그대로 들고 간다 { high = Math.Max(high, p); } } else // 판 날에는 이쪽으로 오지 않는다 { if (rest > 0) // 규칙 4: 쉬는 날 { rest--; } else if (p <= B) // 규칙 5: 산다 { sb.Append("buy ").Append(day).Append(' ').Append(p).Append('\n'); holding = true; cost = p; high = p; } } } sb.Append(profit).Append(' ').Append(holding ? 1 : 0).Append('\n'); Console.Write(sb); }}
C++main.cpp · 43 lines
#include <algorithm>#include <iostream>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, B, g, w, k; std::cin >> n >> B >> g >> w >> k; bool holding = false; int cost = 0; // 산 값 int high = 0; // 산 날부터 지금까지 가장 높았던 값 int rest = 0; // 남은 쉬는 날 수 int profit = 0; for (int day = 1; day <= n; day++) { int p; std::cin >> p; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 std::cout << "sell " << day << ' ' << p << '\n'; profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 std::cout << "sell " << day << ' ' << p << '\n'; profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = std::max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { // 규칙 4: 쉬는 날 rest--; } else if (p <= B) { // 규칙 5: 산다 std::cout << "buy " << day << ' ' << p << '\n'; holding = true; cost = p; high = p; } } } std::cout << profit << ' ' << (holding ? 1 : 0) << '\n';}
Cmain.c · 41 lines
#include <stdio.h>int main(void) { int n, B, g, w, k; scanf("%d %d %d %d %d", &n, &B, &g, &w, &k); int holding = 0; int cost = 0; /* 산 값 */ int high = 0; /* 산 날부터 지금까지 가장 높았던 값 */ int rest = 0; /* 남은 쉬는 날 수 */ int profit = 0; for (int day = 1; day <= n; day++) { int p; scanf("%d", &p); if (holding) { if (p >= cost + g) { /* 규칙 1: 이익 실현 */ printf("sell %d %d\n", day, p); profit += p - cost; holding = 0; } else if (p <= high - w) { /* 규칙 2: 고점에서 w 이상 내려옴 */ printf("sell %d %d\n", day, p); profit += p - cost; holding = 0; if (p < cost) rest = k; /* 손해를 보고 팔았을 때만 쉰다 */ } else { /* 규칙 3: 그대로 들고 간다 */ if (p > high) high = p; } } else { /* 판 날에는 이쪽으로 오지 않는다 */ if (rest > 0) { /* 규칙 4: 쉬는 날 */ rest--; } else if (p <= B) { /* 규칙 5: 산다 */ printf("buy %d %d\n", day, p); holding = 1; cost = p; high = p; } } } printf("%d %d\n", profit, holding); return 0;}
Craykonmain.cray · 62 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];B = 첫줄[1];g = 첫줄[2];w = 첫줄[3];k = 첫줄[4];prices = Console.ReadNumbers();holding = false;cost = 0; // 산 값high = 0; // 산 날부터 지금까지 가장 높았던 값rest = 0; // 남은 쉬는 날 수profit = 0;for (day = 1; day <= n; day++){ p = prices[day - 1]; if (holding) { if (p >= cost + g) { Console.WriteLine("sell " + day + " " + p); profit = profit + p - cost; holding = false; } else if (p <= high - w) { Console.WriteLine("sell " + day + " " + p); profit = profit + p - cost; holding = false; if (p < cost) { rest = k; } } else { high = Mathf.Max(high, p); } } else { if (rest > 0) { rest = rest - 1; } else if (p <= B) { Console.WriteLine("buy " + day + " " + p); holding = true; cost = p; high = p; } }}if (holding){ Console.WriteLine(profit + " 1");}else{ Console.WriteLine(profit + " 0");}