n people run a shop together, and person i has a stake of w_i.
Let W be the sum of all stakes.
Every month the shop splits that month's profit or loss of A won in proportion to the stakes.
A negative A is a month with a loss, and then every share is 0 or less, which means that person has to pay that much.
The first line has n and the number of months q, the second line has w_1 to w_n, and the next q lines have A for each month, one per line.
The share of person i is first set to the largest integer not exceeding A × w_i ÷ W.
For example, 3.5 gives 3, −3.5 gives −4, and an exact division gives that value itself.
The part cut off for person i is then A × w_i − share × W, which is an integer from 0 to W − 1.
The sum of the shares set this way is r won less than A (0 ≤ r < n).
The remaining r won are given 1 won each to r people, starting from the person with the largest cut-off part.
If cut-off parts are equal, the person with the smaller number receives first.
For each month, print the final shares of persons 1 to n on one line, separated by single spaces.
The printed shares always add up to A.
Input
1 ≤ n ≤ 1,000, 1 ≤ q ≤ 20, 1 ≤ w_i ≤ 1,000,000, −1,000,000,000 ≤ A ≤ 1,000,000,000. All are integers and a negative one starts with -
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
Which way integer division goes for negative numbers decides the answer. For −7 ÷ 2, Python -7 // 2 gives −4 (floor), while C, C++, Java and C# -7 / 2 give −3 (truncation toward 0). JS and TS have no separate integer division: Math.floor(-7 / 2) is −4 and Math.trunc(-7 / 2) is −3. In Craykon Mathf.Floor(-7 / 2) is −4 and Mathf.Quot(-7, 2) is −3. When you need the floor, Java has Math.floorDiv(a, b), and C, C++ and C# build it with q = a / b; if (a % b < 0) q--;. Trap one: truncating toward 0 makes the sum of shares larger than A in a loss month. For −100 in the first example, −33 for each of three people is −99, so the leftover is −1 and there is nobody to give it to. With the floor it is −34 each, −102, and 2 won are left. Trap two: the remainder differs too. Python -35 % 10 is 5, but -35 % 10 in C, C++, Java, C#, JS, TS and Craykon is −5. Taking the cut-off part with % mixes 0 and negative values, so for −6 in the second example person 1, whose cut-off part is 0, is picked as the largest. Use Java Math.floorMod, or compute A × w − share × W. Trap three: A × w reaches 10^15 and overflows int in C, C++, Java and C# (last month of the second example). Use long long or long; C# and Java give a wrong value with no error when it overflows. Numbers in JS, TS and Craykon are exact up to 2^53 (about 9 × 10^15), so they work as they are, and in this range Math.floor(a / b) is exact too. Trap four: in Python int(A * w / W) is not the floor but truncation toward 0 (int(-3.5) is −3). Use //. Trap five: with equal cut-off parts the smaller number goes first. For 100 in the first example the 1 won goes to person 1. Python sorted, JS/TS sort, Java Arrays.sort on an array of objects, C# OrderByDescending, C++ stable_sort and Craykon Sort are stable, so comparing only the cut-off parts keeps the input order, but C qsort, C++ std::sort and C# Array.Sort are not guaranteed to be stable, so you must compare the numbers as well.
Pythonmain.py · 27 lines
import sysdef split(amount, weights, total): """amount를 weights 비율로 나눈 몫 목록. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.""" shares = [amount * w // total for w in weights] # //는 음수에서도 내림(-7 // 2 == -4) cut = [amount * w - s * total for w, s in zip(weights, shares)] # 0 이상 total 미만 left = amount - sum(shares) order = sorted(range(len(weights)), key=lambda i: (-cut[i], i)) for i in order[:left]: shares[i] += 1 return sharesdef main(): data = sys.stdin.read().split() n, q = int(data[0]), int(data[1]) weights = [int(x) for x in data[2:2 + n]] total = sum(weights) out = [] for t in range(q): amount = int(data[2 + n + t]) out.append(" ".join(map(str, split(amount, weights, total)))) print("\n".join(out))main()
JavaScriptmain.js · 21 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((x) => x !== "").map(Number);// amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.function split(amount, weights, total) { // Math.floor는 음수에서도 내림이다(Math.trunc는 0 쪽으로 버림). 곱은 10^15 이하라 정확하다 const shares = weights.map((w) => Math.floor((amount * w) / total)); const cut = weights.map((w, i) => amount * w - shares[i] * total); // 0 이상 total 미만 let left = amount; for (const s of shares) left -= s; const order = weights.map((_, i) => i).sort((a, b) => cut[b] - cut[a] || a - b); for (let k = 0; k < left; k++) shares[order[k]] += 1; return shares;}const n = data[0];const q = data[1];const weights = data.slice(2, 2 + n);const total = weights.reduce((a, b) => a + b, 0);const out = [];for (let t = 0; t < q; t++) out.push(split(data[2 + n + t], weights, total).join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 23 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((x: string) => x !== "").map(Number);// amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.function split(amount: number, weights: number[], total: number): number[] { // Math.floor는 음수에서도 내림이다(Math.trunc는 0 쪽으로 버림). 곱은 10^15 이하라 정확하다 const shares: number[] = weights.map((w: number) => Math.floor((amount * w) / total)); const cut: number[] = weights.map((w: number, i: number) => amount * w - shares[i] * total); // 0 이상 total 미만 let left = amount; for (const s of shares) left -= s; const order: number[] = weights.map((_: number, i: number) => i).sort((a: number, b: number) => cut[b] - cut[a] || a - b); for (let k = 0; k < left; k++) shares[order[k]] += 1; return shares;}const n: number = data[0];const q: number = data[1];const weights: number[] = data.slice(2, 2 + n);const total: number = weights.reduce((a: number, b: number) => a + b, 0);const out: string[] = [];for (let t = 0; t < q; t++) out.push(split(data[2 + n + t], weights, total).join(" "));console.log(out.join("\n"));
JavaMain.java · 46 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { // amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다. static long[] split(long amount, int[] weights, long total) { int n = weights.length; long[] shares = new long[n]; long[] cut = new long[n]; long left = amount; for (int i = 0; i < n; i++) { shares[i] = Math.floorDiv(amount * weights[i], total); // /는 0 쪽으로 버리고 floorDiv는 내림 cut[i] = Math.floorMod(amount * weights[i], total); // %는 음수가 나올 수 있고 floorMod는 0 이상 left -= shares[i]; } Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> cut[a] != cut[b] ? Long.compare(cut[b], cut[a]) : Integer.compare(a, b)); for (int k = 0; k < left; k++) shares[order[k]]++; return shares; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken()); int[] weights = new int[n]; long total = 0; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { weights[i] = Integer.parseInt(st.nextToken()); total += weights[i]; } StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { long amount = Long.parseLong(in.readLine().trim()); long[] shares = split(amount, weights, total); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(shares[i]); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 48 lines
using System;using System.Linq;using System.Text;class Program{ // C#의 /는 0 쪽으로 버리므로, 나머지가 음수이면 1을 빼서 내림으로 만든다 static long FloorDiv(long a, long b) { long quot = a / b; if (a % b < 0) quot--; return quot; } // amount를 weights 비율로 나눈 몫 배열. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다. static long[] Split(long amount, int[] weights, long total) { int n = weights.Length; var shares = new long[n]; var cut = new long[n]; long left = amount; for (int i = 0; i < n; i++) { shares[i] = FloorDiv(amount * weights[i], total); cut[i] = amount * weights[i] - shares[i] * total; // 0 이상 total 미만 left -= shares[i]; } // OrderByDescending은 안정 정렬이라 버린 부분이 같으면 번호가 작은 사람이 앞에 남는다 int[] order = Enumerable.Range(0, n).OrderByDescending(i => cut[i]).ToArray(); for (int k = 0; k < left; k++) shares[order[k]]++; return shares; } static void Main() { string[] head = Console.ReadLine().Trim().Split(' '); int n = int.Parse(head[0]), q = int.Parse(head[1]); int[] weights = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); long total = weights.Sum(w => (long)w); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { long amount = long.Parse(Console.ReadLine().Trim()); sb.Append(string.Join(" ", Split(amount, weights, total))).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 49 lines
#include <algorithm>#include <iostream>#include <numeric>#include <vector>using namespace std;// C++의 /는 0 쪽으로 버리므로, 나머지가 음수이면 1을 빼서 내림으로 만든다long long floorDiv(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}// amount를 weights 비율로 나눈 몫 목록. 내림으로 나누고 남은 돈은 버린 부분이 큰 사람부터 1씩 준다.vector<long long> split(long long amount, const vector<int>& weights, long long total) { int n = (int)weights.size(); vector<long long> shares(n), cut(n); long long left = amount; for (int i = 0; i < n; i++) { shares[i] = floorDiv(amount * weights[i], total); cut[i] = amount * weights[i] - shares[i] * total; // 0 이상 total 미만 left -= shares[i]; } vector<int> order(n); iota(order.begin(), order.end(), 0); // stable_sort라서 버린 부분이 같으면 번호가 작은 사람이 앞에 남는다 stable_sort(order.begin(), order.end(), [&](int a, int b) { return cut[a] > cut[b]; }); for (int k = 0; k < left; k++) shares[order[k]]++; return shares;}int main() { int n, q; cin >> n >> q; vector<int> weights(n); long long total = 0; for (int& w : weights) { cin >> w; total += w; } for (int t = 0; t < q; t++) { long long amount; cin >> amount; vector<long long> shares = split(amount, weights, total); for (int i = 0; i < n; i++) cout << (i ? " " : "") << shares[i]; cout << "\n"; } return 0;}
Cmain.c · 48 lines
#include <stdio.h>#include <stdlib.h>#define MAXN 1000static long long cut[MAXN];/* C의 /는 0 쪽으로 버리므로, 나머지가 음수이면 1을 빼서 내림으로 만든다 */static long long floor_div(long long a, long long b) { long long quot = a / b; if (a % b < 0) quot--; return quot;}/* 버린 부분이 큰 사람이 앞, 같으면 번호가 작은 사람이 앞(qsort는 안정 정렬이 보장되지 않아 번호까지 비교한다) */static int by_cut(const void *x, const void *y) { int a = *(const int *)x, b = *(const int *)y; if (cut[a] != cut[b]) return cut[a] > cut[b] ? -1 : 1; return a - b;}int main(void) { static int weights[MAXN], order[MAXN]; static long long shares[MAXN]; int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; long long total = 0; for (int i = 0; i < n; i++) { if (scanf("%d", &weights[i]) != 1) return 0; total += weights[i]; } for (int t = 0; t < q; t++) { long long amount; if (scanf("%lld", &amount) != 1) return 0; long long left = amount; for (int i = 0; i < n; i++) { shares[i] = floor_div(amount * weights[i], total); cut[i] = amount * weights[i] - shares[i] * total; /* 0 이상 total 미만 */ left -= shares[i]; order[i] = i; } qsort(order, (size_t)n, sizeof order[0], by_cut); for (int k = 0; k < left; k++) shares[order[k]]++; for (int i = 0; i < n; i++) printf(i ? " %lld" : "%lld", shares[i]); printf("\n"); } return 0;}
Craykonmain.cray · 39 lines
head = Console.ReadNumbers();n = head[0];q = head[1];weights = Console.ReadNumbers();total = 0;foreach (w in weights){ total = total + w;}cut = NewList(n, 0);// 버린 부분이 큰 사람이 앞. 정렬은 안정 정렬이라 같으면 번호가 작은 사람이 앞에 남는다byCut(a, b){ return cut[b] - cut[a];}for (t = 0; t < q; t++){ amount = Console.ReadLine().Trim().ToNumber(); shares = []; order = []; left = amount; for (i = 0; i < n; i++) { // 수학.내림은 음수에서도 내림이다(수학.몫은 0 쪽으로 버림). 곱은 10^15 이하라 정확하다 share = Mathf.Floor(amount * weights[i] / total); cut[i] = amount * weights[i] - share * total; // 0 이상 total 미만 left = left - share; shares.Add(share); order.Add(i); } order.Sort(byCut); for (k = 0; k < left; k++) { shares[order[k]] = shares[order[k]] + 1; } Console.WriteLine(shares.Join(" "));}