The first line gives integers n and w, the second line the number of questions q, and the third line q piece numbers. Write the numbers 1 to n one after another with no spaces to make a long digit ribbon (for n = 12 it is "123456789101112"). Cut the ribbon from the front into pieces of w characters, and call them piece 1, piece 2, … from the front. The last piece may be shorter than w. Print the asked pieces in the order asked, one per line.
Input
1 ≤ n ≤ 1,000,000, 1 ≤ w ≤ 100, 1 ≤ q ≤ 100, each piece number is between 1 and the number of pieces (the same number may be asked more than once)
Output
one line per question: that piece
Example 1 · stdin
12 5
3
3 1 2
stdout
01112
12345
67891
Example 2 · stdin
10 4
1
3
stdout
910
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
For n = 1,000,000 the ribbon is about 5.9 million characters, so how you concatenate matters a lot. Java String and C# string are immutable, so every s += x builds a new string that copies all the characters so far. Inside a loop that is O(n²) and times out, so collect with StringBuilder's append/Append. Python strings are immutable too. CPython has an optimization that makes += fast, but the language does not promise it, so the standard way is to collect pieces and join them once with "".join(...). JS/TS engines (V8) handle += internally by linking pieces, so it is fast; collecting into an array and calling join("") works too. C++ std::string's += appends in place and is fast, but s = s + x makes a copy each time. C has no string type. strcat searches for the end of the string from the start every time, which is also O(n²). Remember the end position from the count sprintf returns and write right there. Piece numbers start at 1, so piece k starts at character (k - 1) * w (counting from 0). Craykon appends a number to text with ribbon += i (it runs on JS, so this is fast) and cuts a piece with ribbon.Substring(start, count).
Pythonmain.py · 8 lines
n, w = map(int, input().split())q = int(input())ks = list(map(int, input().split()))# 조각을 목록에 모았다가 join 한 번으로 잇는다ribbon = "".join(str(i) for i in range(1, n + 1))for k in ks: start = (k - 1) * w print(ribbon[start:start + w])
JavaScriptmain.js · 7 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, w] = lines[0].trim().split(/\s+/).map(Number);const ks = lines[2].trim().split(/\s+/).map(Number);const parts = [];for (let i = 1; i <= n; i++) parts.push(i);const ribbon = parts.join("");console.log(ks.map((k) => ribbon.slice((k - 1) * w, k * w)).join("\n"));
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int w = sc.nextInt(); int q = sc.nextInt(); // String += 는 매번 새 문자열을 만든다 — StringBuilder 하나에 이어 붙인다 StringBuilder ribbon = new StringBuilder(); for (int i = 1; i <= n; i++) ribbon.append(i); StringBuilder out = new StringBuilder(); for (int j = 0; j < q; j++) { int start = (sc.nextInt() - 1) * w; out.append(ribbon, start, Math.min(start + w, ribbon.length())).append('\n'); } System.out.print(out); }}
C#Main.cs · 21 lines
using System;using System.Text;class Program{ static void Main() { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), w = int.Parse(t[1]); Console.ReadLine(); // string += 는 매번 새 문자열을 만든다 — StringBuilder 하나에 이어 붙인다 var ribbon = new StringBuilder(); for (int i = 1; i <= n; i++) ribbon.Append(i); string s = ribbon.ToString(); foreach (string k in Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)) { int start = (int.Parse(k) - 1) * w; Console.WriteLine(s.Substring(start, Math.Min(w, s.Length - start))); } }}
C++main.cpp · 14 lines
#include <iostream>#include <string>int main() { int n, w, q, k; std::cin >> n >> w >> q; // std::string의 += 는 뒤에 덧붙인다(용량을 넉넉히 늘려 가서 빠르다) std::string ribbon; for (int i = 1; i <= n; i++) ribbon += std::to_string(i); for (int j = 0; j < q; j++) { std::cin >> k; std::cout << ribbon.substr(static_cast<std::size_t>(k - 1) * w, w) << '\n'; }}
Cmain.c · 18 lines
#include <stdio.h>static char ribbon[6000000];int main(void) { int n, w, q, k; scanf("%d %d %d", &n, &w, &q); // 끝 자리(len)를 기억하며 그 뒤에 바로 쓴다 — strcat은 매번 처음부터 끝을 찾는다 int len = 0; for (int i = 1; i <= n; i++) len += sprintf(ribbon + len, "%d", i); for (int j = 0; j < q; j++) { scanf("%d", &k); int start = (k - 1) * w; int count = len - start < w ? len - start : w; printf("%.*s\n", count, ribbon + start); } return 0;}
Craykonmain.cray · 15 lines
t = Console.ReadNumbers();n = t[0];w = t[1];q = Console.ReadLine().ToNumber();ks = Console.ReadNumbers();ribbon = "";for (i = 1; i <= n; i++){ ribbon += i;}foreach (k in ks){ start = (k - 1) * w; Console.WriteLine(ribbon.Substring(start, Mathf.Min(w, ribbon.Length - start)));}