コンサートホールに入口が A と B の二か所ある。 入口ごとに、入った観客の入場時刻(秒)が入った順に書かれている。 だから二つの記録はそれぞれ小さい時刻から順に並んでいる(同じ時刻が複数あることもある)。 二つの記録をまとめて、入場時刻の順に名簿を一つ作る。 時刻が同じなら A 入口の観客が B 入口の観客より前に来る。 同じ入口の観客どうしは元の記録の順番を守る。 名簿の先頭が 1 番である。 一行目に A 入口の観客たちの名簿番号を A の記録の順に、空白一つずつ空けて出力せよ。 二行目に B 入口の観客たちの名簿番号を B の記録の順に、同じように出力せよ。 入力の一行目に A の記録の数 n と B の記録の数 m、二行目に A の時刻 n 個、三行目に B の時刻 m 個が与えられる。
入力
1 ≤ n, m ≤ 10,000、0 ≤ 時刻 ≤ 1,000,000,000(整数)。 各行の時刻は小さくならない順に与えられる
出力
二行:A の観客たちの名簿番号、B の観客たちの名簿番号
例 1 · stdin
4 3
5 9 9 120
3 9 40
stdout
2 3 4 7
1 5 6
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では?言語別の解答を見る · 8 言語の解答
二つの記録はすでに整列しているので、それぞれに指(位置 i、j)を一本ずつ置き、早いほうを名簿に入れてその指だけを一つ進めれば n + m 回で終わります。 同じ時刻なら A が先なので、A を選ぶ条件は a[i] <= b[j] です。 < と書くと同じ時刻で B が先に入ります。 片方の記録が先に終わったら、残りをすべて後ろに付ける必要があります。 while (i < n && j < m) だけ回って止まると尻尾が抜けるので、条件を j == m || (i < n && a[i] <= b[j]) と書いて一つのループで最後まで処理します。 このとき i < n を先に聞けば、使い終わった記録の範囲外を読みません(&& は前が偽なら後ろを見ません。 順番を逆にして a[i] <= b[j] && i < n と書くと、Python・Java・C#・Craykon は範囲外エラーで止まります)。 集めて並べ替えてもよいですが、JS・TS の sort() は比較関数がないと文字列にして辞書順に並べるので、100 が 9 より前に来ます。 Java で List<Integer> の二つの値を == で比べると同じオブジェクトかを見るので、-128〜127 の外の同じ時刻が違うと判定されます。 int[] に入れるか、equals・intValue() を使います。 一行に数を空白でつないで書くとき、Python print(*pos)、JS・TS・C# join(" ")、Craykon コンソール.書く(リスト) は間にだけ空白を入れ、C・C++・Java は最初の数の前に空白が出ないよう自分で気をつけます。
Pythonmain.py · 18 行
n, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))pos_a, pos_b = [], []i = j = 0place = 1while i < n or j < m: # A를 고르는 때: B가 다 끝났거나, A의 시각이 B보다 이르거나 같을 때(같으면 A가 먼저) if j == m or (i < n and a[i] <= b[j]): pos_a.append(place) i += 1 else: pos_b.append(place) j += 1 place += 1print(*pos_a)print(*pos_b)
JavaScriptmain.js · 17 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a = lines[1].trim().split(/\s+/).map(Number);const b = lines[2].trim().split(/\s+/).map(Number);const posA = [], posB = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) { // B가 끝났거나 A가 이르거나 같으면 A가 먼저 if (j === m || (i < n && a[i] <= b[j])) { posA.push(place); i++; } else { posB.push(place); j++; }}console.log(posA.join(" ") + "\n" + posB.join(" "));
TypeScriptmain.ts · 17 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a: number[] = lines[1].trim().split(/\s+/).map(Number);const b: number[] = lines[2].trim().split(/\s+/).map(Number);const posA: number[] = [], posB: number[] = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) { if (j === m || (i < n && a[i] <= b[j])) { posA.push(place); i++; } else { posB.push(place); j++; }}console.log(posA.join(" ") + "\n" + posB.join(" "));
JavaMain.java · 33 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int[] readInts(BufferedReader br, int k) throws Exception { StringTokenizer st = new StringTokenizer(br.readLine()); int[] r = new int[k]; for (int t = 0; t < k; t++) r[t] = Integer.parseInt(st.nextToken()); return r; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()); int[] a = readInts(br, n), b = readInts(br, m); // int[]라 ==가 값을 비교한다 StringBuilder outA = new StringBuilder(), outB = new StringBuilder(); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { if (outA.length() > 0) outA.append(' '); outA.append(place); i++; } else { if (outB.length() > 0) outB.append(' '); outB.append(place); j++; } } System.out.print(outA + "\n" + outB + "\n"); }}
C#Main.cs · 31 行
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]), m = int.Parse(first[1]); int[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); int[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); var posA = new List<int>(n); var posB = new List<int>(m); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { posA.Add(place); i++; } else { posB.Add(place); j++; } } Console.WriteLine(string.Join(" ", posA)); Console.WriteLine(string.Join(" ", posB)); }}
C++main.cpp · 30 行
#include <iostream>#include <vector>void printLine(const std::vector<int>& p) { for (size_t t = 0; t < p.size(); t++) std::cout << (t ? " " : "") << p[t]; std::cout << "\n";}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> a(n), b(m); for (int& x : a) std::cin >> x; for (int& x : b) std::cin >> x; std::vector<int> posA, posB; int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { posA.push_back(place); i++; } else { posB.push_back(place); j++; } } printLine(posA); printLine(posB);}
Cmain.c · 28 行
#include <stdio.h>static int a[10000], b[10000];static int pos_a[10000], pos_b[10000];static void print_line(const int *p, int k) { for (int t = 0; t < k; t++) printf(t ? " %d" : "%d", p[t]); printf("\n");}int main(void) { int n, m; scanf("%d %d", &n, &m); for (int t = 0; t < n; t++) scanf("%d", &a[t]); for (int t = 0; t < m; t++) scanf("%d", &b[t]); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { /* B가 끝났거나 A가 이르거나 같으면 A가 먼저 */ if (j == m || (i < n && a[i] <= b[j])) { pos_a[i++] = place; } else { pos_b[j++] = place; } } print_line(pos_a, n); print_line(pos_b, m); return 0;}
Craykonmain.cray · 27 行
first = コンソール.数読み();n = first[0];m = first[1];a = コンソール.数読み();b = コンソール.数読み();posA = [];posB = [];i = 0;j = 0;繰り返す (place = 1; place <= n + m; place++){ // B가 끝났거나, A가 남아 있고 A의 시각이 이르거나 같으면 A가 먼저 // &&는 앞이 거짓이면 뒤를 보지 않으니 i < n을 먼저 묻는다 takeA = j == m || i < n && a[i] <= b[j]; もし (takeA) { posA.追加(place); i++; } でなければ { posB.追加(place); j++; }}コンソール.書く(posA);コンソール.書く(posB);