There is a sheet of grid paper a columns wide and b rows tall.
Columns are numbered 1, 2, …, a from the left and rows are numbered 1, 2, …, b from the top.
The sheet is cut into square pieces with nothing left over by the following rule.
If the width of the remaining paper is greater than or equal to its height, cut off from its left end a square whose side equals the height of the remaining paper.
If the width of the remaining paper is less than its height, cut off from its top end a square whose side equals the width of the remaining paper.
Repeat this until no paper remains, and number the pieces from 1 in the order they are cut off.
For the sheet of width 10 and height 7 in example 1, piece 1 with side 7 is cut from the left first, then pieces 2 and 3 with side 3 are cut from the top of the remaining paper of width 3 and height 7. Finally pieces 4, 5 and 6 with side 1 are cut from the left of the remaining paper of width 3 and height 1.
On the first line print the number of pieces and the side length of the smallest piece, separated by one space.
Then answer q questions in order, one line each.
The answer to a question "c r" is the number of the piece that contains the grid cell in column c, row r of the original sheet, and the side length of that piece, separated by one space.
Input
The first line gives a, b and q separated by single spaces. Each of the next q lines gives c and r separated by one space. 1 ≤ a, b ≤ 10^15, 1 ≤ q ≤ 5,000, 1 ≤ c ≤ a, 1 ≤ r ≤ b (all integers, given as plain digits without commas)
Output
On the first line, the number of pieces and the side length of the smallest piece. Then for each question one line with the piece number and the side length of that piece
Example 1 · stdin
10 7 6
1 1
7 7
8 1
10 6
9 7
10 7
stdout
6 1
1 7
1 7
2 3
3 3
5 1
6 1
Example 2 · stdin
1000000000000000 1 2
1 1
1000000000000000 1
stdout
1000000000000000 1
1 1
1000000000000000 1
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
This cutting is the Euclidean algorithm drawn as a picture. When the width w is at least the height h, you get the quotient of w divided by h pieces of side h, and the width left is w % h. So the number of pieces is the sum of all quotients that appear in the algorithm, and the side of the smallest piece left at the end is the greatest common divisor of a and b. Python math.gcd and C++ std::gcd (<numeric>) return only the gcd and do not tell you the quotients, so here you have to write the while (y != 0) loop yourself (Java, C#, C, JavaScript, TypeScript and Craykon have no gcd function for plain integers, so you write it anyway). For a question, run the same loop while carrying the lengths already cut away to the left and to the top of the remaining paper, left and top, and the number of pieces cut so far, count. In a step that cuts along the width, if c - left is at most k × h the cell is in that step, and the number is count + the quotient of (c - left - 1) divided by h + 1. A step that cuts along the height does the same with r and top. The quotient is // in Python and integer / in Java, C#, C and C++. / in JavaScript and TypeScript divides into decimals, so use (w - w % h) / h or Math.floor(w / h); / in Craykon also divides into decimals, so use Mathf.Quot(w, h). Trap one: counting pieces one at a time (subtracting instead of taking the remainder) loops 10^15 times for the sheet of width 10^15 and height 1 in example 2. No language finishes that in time, so you must skip k pieces of the same size at once. Then there are never more than 100 steps. Trap two: computing the number as the quotient of (c - left) divided by h + 1 pushes the last column of a piece into the next piece. Column 7, row 7 in example 1 is in piece 1, but you get 2. Trap three: if you use c and r of the original sheet without subtracting the lengths cut away, column 9, row 7 in example 1 fits in no step, the remaining paper runs out, and you divide by zero. The answer is piece 5. Trap four: both the lengths and the number of pieces grow up to 10^15. Java, C#, C and C++ need long/long long. Counting the pieces in a Java int prints -1530494976 on the first line of example 2. Python integers have no size limit, and numbers in JavaScript, TypeScript and Craykon are exact up to 2^53 (about 9 × 10^15), so this range is fine as it is.
Pythonmain.py · 46 lines
import sysdef count_and_smallest(a, b): """조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수).""" count = 0 while b != 0: count += a // b # 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 a, b = b, a % b return count, adef find(a, b, c, r): """c번 칸, r번 줄이 든 조각의 번호와 한 변.""" left = top = 0 # 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 w, h = a, b # 남은 종이의 가로와 세로 count = 0 # 지금까지 잘라 낸 조각의 수 while True: if w >= h: # 왼쪽에서 h × h 조각을 k개 잘라 낸다 k = w // h if c - left <= k * h: return count + (c - left - 1) // h + 1, h count += k left += k * h w -= k * h else: # 위쪽에서 w × w 조각을 k개 잘라 낸다 k = h // w if r - top <= k * w: return count + (r - top - 1) // w + 1, w count += k top += k * w h -= k * wdef main(): data = sys.stdin.read().split() a, b, q = int(data[0]), int(data[1]), int(data[2]) total, smallest = count_and_smallest(max(a, b), min(a, b)) out = [f"{total} {smallest}"] for i in range(q): number, side = find(a, b, int(data[3 + 2 * i]), int(data[4 + 2 * i])) out.append(f"{number} {side}") print("\n".join(out))main()
JavaScriptmain.js · 45 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 몫. 값이 2^53 안의 정수라 나머지를 먼저 빼면 나눗셈이 딱 떨어진다const div = (x, y) => (x - (x % y)) / y;// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)function countAndSmallest(a, b) { let count = 0; while (b !== 0) { count += div(a, b); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 [a, b] = [b, a % b]; } return [count, a];}// c번 칸, r번 줄이 든 조각의 [번호, 한 변]function find(a, b, c, r) { let left = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 let top = 0; let w = a; // 남은 종이의 가로와 세로 let h = b; let count = 0; // 지금까지 잘라 낸 조각의 수 for (;;) { if (w >= h) { const k = div(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 if (c - left <= k * h) return [count + div(c - left - 1, h) + 1, h]; count += k; left += k * h; w -= k * h; } else { const k = div(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 if (r - top <= k * w) return [count + div(r - top - 1, w) + 1, w]; count += k; top += k * w; h -= k * w; } }}const [a, b, q] = data;const out = [countAndSmallest(Math.max(a, b), Math.min(a, b)).join(" ")];for (let i = 0; i < q; i++) { out.push(find(a, b, data[3 + 2 * i], data[4 + 2 * i]).join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 46 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 몫. 값이 2^53 안의 정수라 나머지를 먼저 빼면 나눗셈이 딱 떨어진다const div = (x: number, y: number): number => (x - (x % y)) / y;// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)function countAndSmallest(a: number, b: number): [number, number] { let count = 0; while (b !== 0) { count += div(a, b); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 [a, b] = [b, a % b]; } return [count, a];}// c번 칸, r번 줄이 든 조각의 [번호, 한 변]function find(a: number, b: number, c: number, r: number): [number, number] { let left = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 let top = 0; let w = a; // 남은 종이의 가로와 세로 let h = b; let count = 0; // 지금까지 잘라 낸 조각의 수 for (;;) { if (w >= h) { const k = div(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 if (c - left <= k * h) return [count + div(c - left - 1, h) + 1, h]; count += k; left += k * h; w -= k * h; } else { const k = div(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 if (r - top <= k * w) return [count + div(r - top - 1, w) + 1, w]; count += k; top += k * w; h -= k * w; } }}const [a, b, q] = data;const out: string[] = [countAndSmallest(Math.max(a, b), Math.min(a, b)).join(" ")];for (let i = 0; i < q; i++) { out.push(find(a, b, data[3 + 2 * i], data[4 + 2 * i]).join(" "));}console.log(out.join("\n"));
JavaMain.java · 54 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); int q = Integer.parseInt(st.nextToken()); StringBuilder out = new StringBuilder(); // 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수) long x = Math.max(a, b), y = Math.min(a, b), total = 0; while (y != 0) { total += x / y; // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 long t = x % y; x = y; y = t; } out.append(total).append(' ').append(x).append('\n'); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); long c = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); long left = 0, top = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 long w = a, h = b; // 남은 종이의 가로와 세로 long count = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) { // 왼쪽에서 h × h 조각을 k개 잘라 낸다 long k = w / h; if (c - left <= k * h) { out.append(count + (c - left - 1) / h + 1).append(' ').append(h).append('\n'); break; } count += k; left += k * h; w -= k * h; } else { // 위쪽에서 w × w 조각을 k개 잘라 낸다 long k = h / w; if (r - top <= k * w) { out.append(count + (r - top - 1) / w + 1).append(' ').append(w).append('\n'); break; } count += k; top += k * w; h -= k * w; } } } System.out.print(out); }}
C#Main.cs · 59 lines
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long a = long.Parse(p[0]), b = long.Parse(p[1]); int q = int.Parse(p[2]); var sb = new StringBuilder(); // 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수) long x = Math.Max(a, b), y = Math.Min(a, b), total = 0; while (y != 0) { total += x / y; // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 (x, y) = (y, x % y); } sb.Append(total).Append(' ').Append(x).Append('\n'); for (int i = 0; i < q; i++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long c = long.Parse(p[0]), r = long.Parse(p[1]); long left = 0, top = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 long w = a, h = b; // 남은 종이의 가로와 세로 long count = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) // 왼쪽에서 h × h 조각을 k개 잘라 낸다 { long k = w / h; if (c - left <= k * h) { sb.Append(count + (c - left - 1) / h + 1).Append(' ').Append(h).Append('\n'); break; } count += k; left += k * h; w -= k * h; } else // 위쪽에서 w × w 조각을 k개 잘라 낸다 { long k = h / w; if (r - top <= k * w) { sb.Append(count + (r - top - 1) / w + 1).Append(' ').Append(w).Append('\n'); break; } count += k; top += k * w; h -= k * w; } } } Console.Write(sb); }}
C++main.cpp · 53 lines
#include <algorithm>#include <iostream>#include <numeric>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long a, b; int q; cin >> a >> b >> q; // 조각의 수: 유클리드 호제법의 몫을 모두 더한 값 long long x = max(a, b), y = min(a, b), total = 0; while (y != 0) { total += x / y; // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 long long t = x % y; x = y; y = t; } // 가장 작은 조각의 한 변은 최대공약수다(x와 같다) cout << total << ' ' << gcd(a, b) << '\n'; while (q--) { long long c, r; cin >> c >> r; long long left = 0, top = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 long long w = a, h = b; // 남은 종이의 가로와 세로 long long count = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) { // 왼쪽에서 h × h 조각을 k개 잘라 낸다 long long k = w / h; if (c - left <= k * h) { cout << count + (c - left - 1) / h + 1 << ' ' << h << '\n'; break; } count += k; left += k * h; w -= k * h; } else { // 위쪽에서 w × w 조각을 k개 잘라 낸다 long long k = h / w; if (r - top <= k * w) { cout << count + (r - top - 1) / w + 1 << ' ' << w << '\n'; break; } count += k; top += k * w; h -= k * w; } } } return 0;}
Cmain.c · 47 lines
#include <stdio.h>int main(void) { long long a, b; int q; if (scanf("%lld %lld %d", &a, &b, &q) != 3) return 0; /* 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수) */ long long x = a > b ? a : b, y = a > b ? b : a, total = 0; while (y != 0) { total += x / y; /* 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 */ long long t = x % y; x = y; y = t; } printf("%lld %lld\n", total, x); for (int i = 0; i < q; i++) { long long c, r; if (scanf("%lld %lld", &c, &r) != 2) return 0; long long left = 0, top = 0; /* 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 */ long long w = a, h = b; /* 남은 종이의 가로와 세로 */ long long count = 0; /* 지금까지 잘라 낸 조각의 수 */ for (;;) { if (w >= h) { /* 왼쪽에서 h × h 조각을 k개 잘라 낸다 */ long long k = w / h; if (c - left <= k * h) { printf("%lld %lld\n", count + (c - left - 1) / h + 1, h); break; } count += k; left += k * h; w -= k * h; } else { /* 위쪽에서 w × w 조각을 k개 잘라 낸다 */ long long k = h / w; if (r - top <= k * w) { printf("%lld %lld\n", count + (r - top - 1) / w + 1, w); break; } count += k; top += k * w; h -= k * w; } } } return 0;}
Craykonmain.cray · 59 lines
첫줄 = Console.ReadNumbers();a = 첫줄[0];b = 첫줄[1];q = 첫줄[2];// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)x = Mathf.Max(a, b);y = Mathf.Min(a, b);모두 = 0;while (y != 0){ 모두 = 모두 + Mathf.Quot(x, y); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 t = x % y; x = y; y = t;}Console.WriteLine(모두 + " " + x);// c번 칸, r번 줄이 든 조각의 [번호, 한 변]찾기(c, r){ 왼쪽 = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 위쪽 = 0; w = a; // 남은 종이의 가로와 세로 h = b; 센수 = 0; // 지금까지 잘라 낸 조각의 수 while (true) { if (w >= h) { k = Mathf.Quot(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 if (c - 왼쪽 <= k * h) { return [센수 + Mathf.Quot(c - 왼쪽 - 1, h) + 1, h]; } 센수 = 센수 + k; 왼쪽 = 왼쪽 + k * h; w = w - k * h; } else { k = Mathf.Quot(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 if (r - 위쪽 <= k * w) { return [센수 + Mathf.Quot(r - 위쪽 - 1, w) + 1, w]; } 센수 = 센수 + k; 위쪽 = 위쪽 + k * w; h = h - k * w; } }}for (i = 0; i < q; i++){ 줄 = Console.ReadNumbers(); 답 = 찾기(줄[0], 줄[1]); Console.WriteLine(답[0] + " " + 답[1]);}