A building wall is covered with square tiles, C tiles wide and R rows tall.
A billboard is a rectangle covering one or more whole tiles, with a height of h rows and a width of w tiles, both integers of 1 or more.
A billboard is aligned exactly with the tile rows and columns, must not go outside the wall, and is not rotated.
The advertisers only buy billboards whose area h × w is at least A and at most B.
Two cases are different if the size (h, w) or the position differs in any way.
One line gives R, C, A, B separated by spaces.
Go through the heights h from 1 to R in order, and if the number of ways to put up a billboard of height h is greater than 0, print h and that number on one line, separated by one space.
Do not print a line for a height with 0 ways.
On the last line, print "total" and the sum of the numbers of ways over all heights, separated by one space.
Write numbers as plain digits, with no commas.
Input
1 ≤ R ≤ 500, 1 ≤ C ≤ 500, 1 ≤ A ≤ B ≤ 250,000 (all integers)
Output
One line "h ways" for each height that has ways, and a last line "total sum"
Example 1 · stdin
2 3 2 3
stdout
1 6
2 3
total 9
Example 2 · stdin
3 3 10 20
stdout
total 0
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
Loop twice: height h from 1 to R and width w from 1 to C, and when the area fits add the (R - h + 1) × (C - w + 1) positions. On a wall with R rows, a billboard of height h can have its top row at row 1 through row R - h + 1, so it is not R - h. The first trap is where the loop ends. Python range(1, R + 1) leaves out the end value, so writing range(1, R) misses h = R. JS, TS, Java, C#, C and C++ write for (int h = 1; h <= R; h++) and Craykon for (h = 1; h <= R; h++), including the end with <=. In C#, the second argument of Enumerable.Range(1, R) is a count, not an end. Second, the inner loop is the width, so it goes up to C. On a wall whose width and height differ (500 × 1), swapping R and C gives a wrong answer. Third, "at least A and at most B" includes both ends, so it is A <= area && area <= B (Python can chain it as A <= area <= B, but elsewhere it is an error (Craykon, Java, C#) or means something else (JS, TS, C and C++ compare the result of the first comparison with B)). The fourth trap is size. The number of ways for one height fits in an int, but on a 500 × 500 wall the sum is about 1.6×10^10, so add it into C/C++ long long or Java/C# long. Numbers in JS, TS and Craykon are exact up to 2^53, and Python's int never overflows.
Pythonmain.py · 11 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
v = Console.ReadNumbers();R = v[0];C = v[1];A = v[2];B = v[3];total = 0; // 최대 약 1.6×10^10: 2^53 안이라 정확하다for (h = 1; h <= R; h++){ count = 0; for (w = 1; w <= C; w++) { area = h * w; if (A <= area && area <= B) { // 위쪽 줄 R-h+1가지 × 왼쪽 칸 C-w+1가지 count += (R - h + 1) * (C - w + 1); } } if (count > 0) { Console.WriteLine(h + " " + count); } total += count;}Console.WriteLine("total " + total);