建物の壁が、横 C 枚、縦 R 段の正方形のタイルで覆われている。 看板はタイルを 1 枚以上覆う長方形で、高さ h 段と幅 w 枚は 1 以上の整数である。 看板はタイルの段と列にぴったり合わせて貼り、壁の外にはみ出してはならず、回して貼ることはない。 広告主は面積 h × w が A 以上 B 以下の看板だけを買う。 大きさ (h, w) と貼る場所が一つでも違えば、違う場合として数える。 一行に R、C、A、B が空白で区切って与えられる。 高さ h を 1 から R まで順に見て、高さ h の看板を貼る場合の数が 0 より大きければ、一行に h とその場合の数を空白一つで区切って出力せよ。 場合の数が 0 の高さは行を書かない。 最後の行には "total" と、すべての高さの場合の数を足した値を空白一つで区切って出力せよ。 数はカンマなしで数字だけを書く。
入力
1 ≤ R ≤ 500、1 ≤ C ≤ 500、1 ≤ A ≤ B ≤ 250,000（すべて整数）
出力
場合の数がある高さごとに "h 場合の数" 一行、最後の行に "total 合計"
例 1 · stdin
2 3 2 3
stdout
1 6
2 3
total 9
例 2 · stdin
3 3 10 20
stdout
total 0
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
高さ h は 1 から R まで、幅 w は 1 から C まで二重に回し、面積が合えば貼る場所 (R - h + 1) × (C - w + 1) 通りを足します。 段数が R の壁に高さ h を貼ると、いちばん上の段は 1 段目から R - h + 1 段目までなので、R - h ではありません。 一つ目の落とし穴は繰り返しの終わりです。 Python の range(1, R + 1) は終わりの値を入れないので、range(1, R) と書くと h = R を落とします。 JS・TS・Java・C#・C・C++ は for (int h = 1; h <= R; h++)、Craykon は 繰り返す (h = 1; h <= R; h++) のように <= で終わりを入れます。 C# の Enumerable.Range(1, R) は二つ目の値が終わりではなく個数です。 二つ目に、内側の繰り返しは幅なので C まで回します。 縦と横が違う壁（500 × 1）で R と C を取り違えると間違えます。 三つ目に、「A 以上 B 以下」は両端とも入るので A <= area && area <= B です（Python は A <= area <= B とつなげて書けますが、ほかの言語ではエラーになるか（Craykon、Java・C#）、意味が変わります（JS・TS・C・C++ は前の比較の結果を B と比べます））。 四つ目の落とし穴は大きさです。 高さ一つの場合の数は int に収まりますが、500 × 500 の壁では合計が約 1.6×10^10 になるので、C・C++ は long long、Java・C# は long に足します。 JS・TS・Craykon の数は 2^53 まで正確で、Python の int はあふれません。
Pythonmain.py · 11 行
R, C, A, B = map(int, input().split())total = 0for h in range(1, R + 1): # range의 끝은 들어가지 않는다: R까지 돌려면 R + 1 count = 0 for w in range(1, C + 1): if A <= h * w <= B: count += (R - h + 1) * (C - w + 1) # 위쪽 줄 R-h+1가지 × 왼쪽 칸 C-w+1가지 if count > 0: print(h, count) total += countprint("total", total)
JavaScriptmain.js · 14 行
const [R, C, A, B] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = [];let total = 0; // 최대 약 1.6×10^10: 2^53 안이라 Number로 정확하다for (let h = 1; h <= R; h++) { let count = 0; for (let w = 1; w <= C; w++) { const area = h * w; if (A <= area && area <= B) count += (R - h + 1) * (C - w + 1); } if (count > 0) out.push(`${h} ${count}`); total += count;}out.push(`total ${total}`);console.log(out.join("\n"));
TypeScriptmain.ts · 15 行
import { readFileSync } from "node:fs";const [R, C, A, B]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: string[] = [];let total = 0; // 최대 약 1.6×10^10: 2^53 안이라 number로 정확하다for (let h = 1; h <= R; h++) { let count = 0; for (let w = 1; w <= C; w++) { const area: number = h * w; if (A <= area && area <= B) count += (R - h + 1) * (C - w + 1); } if (count > 0) out.push(`${h} ${count}`); total += count;}out.push(`total ${total}`);console.log(out.join("\n"));
JavaMain.java · 21 行
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int R = sc.nextInt(), C = sc.nextInt(), A = sc.nextInt(), B = sc.nextInt(); StringBuilder out = new StringBuilder(); long total = 0; // 최대 약 1.6×10^10: int로는 넘친다 for (int h = 1; h <= R; h++) { long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long) (R - h + 1) * (C - w + 1); } if (count > 0) out.append(h).append(' ').append(count).append('\n'); total += count; } out.append("total ").append(total).append('\n'); System.out.print(out); }}
C#Main.cs · 27 行
using System;using System.Linq;using System.Text;class Program{ static void Main() { int[] v = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int R = v[0], C = v[1], A = v[2], B = v[3]; var out_ = new StringBuilder(); long total = 0; // 최대 약 1.6×10^10: int로는 넘친다 for (int h = 1; h <= R; h++) { long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long)(R - h + 1) * (C - w + 1); } if (count > 0) out_.Append(h).Append(' ').Append(count).Append('\n'); total += count; } out_.Append("total ").Append(total).Append('\n'); Console.Write(out_); }}
C++main.cpp · 17 行
#include <iostream>int main() { int R, C, A, B; std::cin >> R >> C >> A >> B; long long total = 0; // 최대 약 1.6×10^10: int로는 넘친다 for (int h = 1; h <= R; h++) { long long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long long)(R - h + 1) * (C - w + 1); } if (count > 0) std::cout << h << ' ' << count << '\n'; total += count; } std::cout << "total " << total << '\n';}
Cmain.c · 18 行
#include <stdio.h>int main(void) { int R, C, A, B; scanf("%d %d %d %d", &R, &C, &A, &B); long long total = 0; /* 최대 약 1.6×10^10: int로는 넘친다 */ for (int h = 1; h <= R; h++) { long long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long long)(R - h + 1) * (C - w + 1); } if (count > 0) printf("%d %lld\n", h, count); total += count; } printf("total %lld\n", total); return 0;}
Craykonmain.cray · 25 行
v = コンソール.数読み();R = v[0];C = v[1];A = v[2];B = v[3];total = 0; // 최대 약 1.6×10^10: 2^53 안이라 정확하다繰り返す (h = 1; h <= R; h++){ count = 0; 繰り返す (w = 1; w <= C; w++) { area = h * w; もし (A <= area && area <= B) { // 위쪽 줄 R-h+1가지 × 왼쪽 칸 C-w+1가지 count += (R - h + 1) * (C - w + 1); } } もし (count > 0) { コンソール.書く(h + " " + count); } total += count;}コンソール.書く("total " + total);