원탁에 손님 n명이 둘러앉아 있다.
자리에는 시계 방향으로 1번, 2번, …, n번이 붙어 있고, n번 자리의 시계 방향 옆은 1번 자리이다.
i번 자리 손님의 음식을 내는 데는 t_i초가 걸린다.
종업원은 s번 자리에서 시작해 한쪽 방향으로 돌면서 이어 앉은 k명에게 차례로 음식을 낸다.
손님이 기다린 시간은 자기보다 먼저 받은 손님들의 음식을 내는 데 걸린 시간을 모두 더한 값이다. 자기 음식을 내는 시간은 넣지 않는다.
질문 q개가 주어진다.
질문 "s k"마다 시계 방향으로 돌 때 k명이 기다린 시간의 합과, 반시계 방향으로 돌 때 k명이 기다린 시간의 합을 빈칸 하나로 띄워 한 줄에 출력하라.
예시 1의 첫 질문 "1 3"에서 시계 방향으로 돌면 1번, 2번, 3번 자리 손님이 차례로 0초, 3초, 4초를 기다려 합이 7이다. 반시계 방향으로 돌면 1번, 5번, 4번 자리 손님이 차례로 0초, 3초, 8초를 기다려 합이 11이다.
입력
첫 줄에 n과 q가 빈칸 하나로 띄워 주어진다. 둘째 줄에 t_1, …, t_n이 빈칸 하나로 띄워 주어진다. 다음 q줄에 s와 k가 빈칸 하나로 띄워 주어진다. 1 ≤ n ≤ 9,000, 1 ≤ q ≤ 7,000, 1 ≤ t_i ≤ 10^8, 1 ≤ s ≤ n, 1 ≤ k ≤ n(모두 정수)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
j번째(0부터 셈)로 받는 손님의 음식 시간은 그 뒤에 받는 k-1-j명이 모두 기다려요. 그래서 답은 t × (k-1-j)를 모두 더한 값이고, 곱하는 수가 자리를 하나 옮길 때마다 1씩 줄어요. 이런 합은 누적 합 두 개로 구해요. P[i]는 앞에서부터 i개의 t를 더한 값, Q[i]는 자리 번호 × t를 더한 값이에요(자리 번호는 0부터). 자리 a부터 b-1까지를 번호가 커지는 쪽으로 돌고 a의 곱하는 수가 c라면 합은 c × (P[b] - P[a]) - ((Q[b] - Q[a]) - a × (P[b] - P[a]))예요. 번호가 작아지는 쪽으로 돌 때는 Q를 반대로 써요. 원탁이라 n번 자리를 넘어가면 두 토막으로 나눠요. 둘째 토막의 첫 손님이 곱하는 수는 첫 토막의 사람 수만큼 줄어든 값이에요. 작은 계산 둘을 Python은 함수 안의 함수로, C++은 람다로, Java·C#은 static 메서드로, C·JavaScript·TypeScript·크레이콘은 그냥 함수로 묶었어요. 누적 합 목록은 Python [0] * (n + 1), JavaScript new Array(n + 1).fill(0), 크레이콘 새목록(n + 1, 0)처럼 0으로 채워 만들어요. 함정 하나: 질문마다 k명을 한 명씩 돌며 더하면 가장 큰 입력에서 약 1억 2천만 번을 더해요. 이렇게 짠 Python 풀이는 시간 안에 끝나지 않았고, 크레이콘도 너무 오래 걸린다며 멈췄어요. 솔직히 말하면 같은 방식의 C 풀이는 이 컴퓨터에서 0.3초 안에 끝났어요. 누적 합이 꼭 필요한 것은 느린 언어에서예요. 함정 둘: 둘째 토막에서 곱하는 수를 다시 k-1부터 시작하면 안 돼요. 예시 1의 둘째 질문 "4 4"는 시계 방향 합이 16인데 24가 나오고, 첫 질문의 반시계 방향 합은 11인데 17이 나와요. 함정 셋: 자기 음식을 내는 시간까지 넣으면(곱하는 수를 k부터 시작하면) 예시 1의 첫 질문이 7 11이 아니라 15 20이 되고, 한 명뿐인 셋째 질문도 0 0이 아니라 1 1이 돼요. 함정 넷: 반시계 방향으로 도는 k명은 어떤 자리에서 시계 방향으로 도는 k명과 같은 사람들이지만, 차례가 거꾸로라서 합이 달라요. 예시 1의 첫 질문에서 반시계 방향(1번, 5번, 4번)을 4번에서 시작하는 시계 방향(4번, 5번, 1번)으로 바꿔 구하면 11이 아니라 7이 나와요. 함정 다섯: 답이 약 4 × 10^15까지 커져요. Java·C#·C·C++은 누적 합과 답을 long/long long에 담아야 해요. Java에서 모두 int에 담으면 예시 2의 첫 질문이 2800000000이 아니라 -1494967296으로 나와요. Python의 정수는 크기 제한이 없어요. JavaScript·TypeScript·크레이콘의 수는 2^53(약 9.007 × 10^15)까지만 정확한데, 이 문제는 중간에 나오는 곱도 약 8.1 × 10^15를 넘지 않아서 그대로 맞아요.
Pythonmain.py · 42 줄
import sysdef main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) t = [int(x) for x in data[2:2 + n]] # P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 P = [0] * (n + 1) Q = [0] * (n + 1) for i in range(n): P[i + 1] = P[i] + t[i] Q[i + 1] = Q[i] + i * t[i] def forward(a, b, c): """자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다.""" dp = P[b] - P[a] return c * dp - ((Q[b] - Q[a]) - a * dp) def backward(a, b, c): """자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다.""" dp = P[b] - P[a] return c * dp - ((b - 1) * dp - (Q[b] - Q[a])) out = [] pos = 2 + n for _ in range(q): s, k = int(data[pos]) - 1, int(data[pos + 1]) pos += 2 if s + k <= n: cw = forward(s, s + k, k - 1) else: cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)) if k <= s + 1: ccw = backward(s - k + 1, s + 1, k - 1) else: ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)) out.append("%d %d" % (cw, ccw)) print("\n".join(out))main()
JavaScriptmain.js · 36 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];// P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합const P = new Array(n + 1).fill(0);const Q = new Array(n + 1).fill(0);for (let i = 0; i < n; i++) { P[i + 1] = P[i] + data[2 + i]; Q[i + 1] = Q[i] + i * data[2 + i];}// 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다function forward(a, b, c) { const dp = P[b] - P[a]; return c * dp - (Q[b] - Q[a] - a * dp);}// 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다function backward(a, b, c) { const dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}const out = [];for (let i = 0; i < q; i++) { const s = data[2 + n + 2 * i] - 1; const k = data[3 + n + 2 * i]; let cw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); let ccw; if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); out.push(cw + " " + ccw);}console.log(out.join("\n"));
TypeScriptmain.ts · 37 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];// P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합const P: number[] = new Array<number>(n + 1).fill(0);const Q: number[] = new Array<number>(n + 1).fill(0);for (let i = 0; i < n; i++) { P[i + 1] = P[i] + data[2 + i]; Q[i + 1] = Q[i] + i * data[2 + i];}// 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다function forward(a: number, b: number, c: number): number { const dp = P[b] - P[a]; return c * dp - (Q[b] - Q[a] - a * dp);}// 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다function backward(a: number, b: number, c: number): number { const dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}const out: string[] = [];for (let i = 0; i < q; i++) { const s = data[2 + n + 2 * i] - 1; const k = data[3 + n + 2 * i]; let cw: number; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); let ccw: number; if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); out.push(cw + " " + ccw);}console.log(out.join("\n"));
JavaMain.java · 46 줄
import java.io.*;import java.util.*;public class Main { static long[] P, Q; // P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 // 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 static long forward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp); } // 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 static long backward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a])); } 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()); int q = Integer.parseInt(st.nextToken()); P = new long[n + 1]; Q = new long[n + 1]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { long t = Long.parseLong(st.nextToken()); P[i + 1] = P[i] + t; Q[i + 1] = Q[i] + i * t; } StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); int s = Integer.parseInt(st.nextToken()) - 1; int k = Integer.parseInt(st.nextToken()); long cw, ccw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); out.append(cw).append(' ').append(ccw).append('\n'); } System.out.print(out); }}
C#Main.cs · 48 줄
using System;using System.Text;class Program{ static long[] P, Q; // P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 // 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 static long Forward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp); } // 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 static long Backward(int a, int b, int c) { long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a])); } static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), q = int.Parse(p[1]); long[] t = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); P = new long[n + 1]; Q = new long[n + 1]; for (int i = 0; i < n; i++) { P[i + 1] = P[i] + t[i]; Q[i + 1] = Q[i] + i * t[i]; } var sb = new StringBuilder(); for (int i = 0; i < q; i++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int s = int.Parse(p[0]) - 1, k = int.Parse(p[1]); long cw, ccw; if (s + k <= n) cw = Forward(s, s + k, k - 1); else cw = Forward(s, n, k - 1) + Forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = Backward(s - k + 1, s + 1, k - 1); else ccw = Backward(0, s + 1, k - 1) + Backward(n - (k - s - 1), n, k - 1 - (s + 1)); sb.Append(cw).Append(' ').Append(ccw).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 40 줄
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; // P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 vector<long long> P(n + 1, 0), Q(n + 1, 0); for (int i = 0; i < n; i++) { long long t; cin >> t; P[i + 1] = P[i] + t; Q[i + 1] = Q[i] + i * t; } // 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 auto forward = [&](int a, int b, int c) -> long long { long long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp); }; // 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 auto backward = [&](int a, int b, int c) -> long long { long long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a])); }; while (q--) { int s, k; cin >> s >> k; s--; long long cw, ccw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); cout << cw << ' ' << ccw << '\n'; } return 0;}
Cmain.c · 39 줄
#include <stdio.h>/* P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합 */static long long P[9001], Q[9001];/* 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다 */static long long forward(int a, int b, int c) { long long dp = P[b] - P[a]; return c * dp - ((Q[b] - Q[a]) - a * dp);}/* 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다 */static long long backward(int a, int b, int c) { long long dp = P[b] - P[a]; return c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}int main(void) { int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) { long long t; if (scanf("%lld", &t) != 1) return 0; P[i + 1] = P[i] + t; Q[i + 1] = Q[i] + i * t; } for (int i = 0; i < q; i++) { int s, k; if (scanf("%d %d", &s, &k) != 2) return 0; s--; long long cw, ccw; if (s + k <= n) cw = forward(s, s + k, k - 1); else cw = forward(s, n, k - 1) + forward(0, s + k - n, k - 1 - (n - s)); if (k <= s + 1) ccw = backward(s - k + 1, s + 1, k - 1); else ccw = backward(0, s + 1, k - 1) + backward(n - (k - s - 1), n, k - 1 - (s + 1)); printf("%lld %lld\n", cw, ccw); } return 0;}
Craykonmain.cray · 52 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];q = 첫줄[1];t = 콘솔.수들읽기();// P[i] = t[0..i-1]의 합, Q[i] = j * t[j] (j < i)의 합P = 새목록(n + 1, 0);Q = 새목록(n + 1, 0);반복 (i = 0; i < n; i++){ P[i + 1] = P[i] + t[i]; Q[i + 1] = Q[i] + i * t[i];}// 자리 a..b-1을 번호가 커지는 쪽으로 돌 때: a가 c번, 그다음이 c-1번, … 기다리게 한다앞으로(a, b, c){ dp = P[b] - P[a]; 돌려주기 c * dp - (Q[b] - Q[a] - a * dp);}// 자리 b-1..a를 번호가 작아지는 쪽으로 돌 때: b-1이 c번, 그다음이 c-1번, … 기다리게 한다뒤로(a, b, c){ dp = P[b] - P[a]; 돌려주기 c * dp - ((b - 1) * dp - (Q[b] - Q[a]));}반복 (i = 0; i < q; i++){ 줄 = 콘솔.수들읽기(); s = 줄[0] - 1; k = 줄[1]; 시계 = 0; 반시계 = 0; 만약 (s + k <= n) { 시계 = 앞으로(s, s + k, k - 1); } 아니면 { 시계 = 앞으로(s, n, k - 1) + 앞으로(0, s + k - n, k - 1 - (n - s)); } 만약 (k <= s + 1) { 반시계 = 뒤로(s - k + 1, s + 1, k - 1); } 아니면 { 반시계 = 뒤로(0, s + 1, k - 1) + 뒤로(n - (k - s - 1), n, k - 1 - (s + 1)); } 콘솔.쓰기(시계 + " " + 반시계);}