가로로 a칸, 세로로 b줄인 모눈종이가 있다.
칸은 왼쪽부터 1번, 2번, …, a번이고, 줄은 위부터 1번, 2번, …, b번이다.
이 종이를 다음 규칙으로 남김없이 정사각형 조각으로 자른다.
남은 종이의 가로가 세로보다 길거나 같으면, 남은 종이의 왼쪽 끝에서 한 변이 남은 종이의 세로와 같은 정사각형을 잘라 낸다.
남은 종이의 가로가 세로보다 짧으면, 남은 종이의 위쪽 끝에서 한 변이 남은 종이의 가로와 같은 정사각형을 잘라 낸다.
남은 종이가 없어질 때까지 이 일을 되풀이하고, 조각에는 잘라 낸 차례대로 1번부터 번호를 붙인다.
예시 1의 가로 10, 세로 7인 종이에서는 먼저 왼쪽에서 한 변이 7인 1번 조각을 잘라 내고, 남은 가로 3, 세로 7인 종이의 위쪽에서 한 변이 3인 2번, 3번 조각을 잘라 낸다. 마지막으로 남은 가로 3, 세로 1인 종이의 왼쪽에서 한 변이 1인 4번, 5번, 6번 조각을 잘라 낸다.
첫 줄에 조각의 수와 가장 작은 조각의 한 변의 길이를 빈칸 하나로 띄워 출력하라.
이어서 질문 q개에 차례대로 한 줄씩 답하라.
질문 "c r"의 답은 처음 종이의 c번 칸, r번 줄에 있는 모눈이 들어간 조각의 번호와 그 조각의 한 변의 길이이고, 빈칸 하나로 띄워 출력한다.
입력
첫 줄에 a, b, q가 빈칸 하나로 띄워 주어진다. 다음 q줄에 c와 r이 빈칸 하나로 띄워 주어진다. 1 ≤ a, b ≤ 10^15, 1 ≤ q ≤ 5,000, 1 ≤ c ≤ a, 1 ≤ r ≤ b(모두 정수이고, 쉼표 없이 숫자만 주어진다)
출력
첫 줄에 조각의 수와 가장 작은 조각의 한 변의 길이. 이어서 질문마다 한 줄에 조각의 번호와 그 조각의 한 변의 길이
예시 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
예시 2 · stdin
1000000000000000 1 2
1 1
1000000000000000 1
stdout
1000000000000000 1
1 1
1000000000000000 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
이 자르기는 유클리드 호제법을 그림으로 그린 것이에요. 가로 w가 세로 h 이상이면 한 변이 h인 조각이 w를 h로 나눈 몫개 나오고, 남는 가로는 w % h예요. 그래서 조각의 수는 호제법에서 나오는 몫을 모두 더한 값이고, 마지막에 남는 가장 작은 조각의 한 변이 a와 b의 최대공약수예요. Python math.gcd, C++ std::gcd(<numeric>)는 최대공약수만 돌려주고 몫은 알려 주지 않아서, 여기서는 while (y != 0) 반복을 직접 써야 해요(Java·C#·C·JavaScript·TypeScript·크레이콘에는 정수용 gcd 함수가 없어 어차피 직접 써요). 질문에는 같은 반복을 돌면서 남은 종이의 왼쪽과 위쪽으로 이미 잘려 나간 길이 left, top과 지금까지 자른 조각의 수 count를 함께 들고 가요. 가로로 자르는 단계에서 c - left가 k × h 이하이면 그 단계의 조각이고, 번호는 count + (c - left - 1)을 h로 나눈 몫 + 1이에요. 세로로 자르는 단계는 r과 top으로 똑같이 해요. 몫은 Python //, Java·C#·C·C++의 정수 /로 구해요. JavaScript·TypeScript의 /는 소수까지 나누니 (w - w % h) / h나 Math.floor(w / h)로, 크레이콘도 /가 소수까지 나누니 수학.몫(w, h)로 구해요. 함정 하나: 조각을 하나씩 잘라 세면(나머지 대신 빼기) 예시 2의 가로 10^15, 세로 1인 종이에서 10^15번을 돌아요. 어느 언어로도 시간 안에 끝나지 않아서, 같은 크기의 조각 k개를 한 번에 건너뛰어야 해요. 그러면 단계는 100번을 넘지 않아요. 함정 둘: 번호를 (c - left)를 h로 나눈 몫 + 1로 구하면 조각의 마지막 칸이 다음 조각으로 넘어가요. 예시 1의 7번 칸, 7번 줄은 1번 조각인데 2가 나와요. 함정 셋: 잘려 나간 길이를 빼지 않고 처음 종이의 c, r을 그대로 쓰면 예시 1의 9번 칸, 7번 줄에서 어느 단계에도 들지 못하고 남은 종이가 없어져 0으로 나누게 돼요. 답은 5번 조각이에요. 함정 넷: 길이도, 조각의 수도 10^15까지 커져요. Java·C#·C·C++은 long/long long을 써야 해요. Java에서 조각의 수를 int로 세면 예시 2의 첫 줄이 -1530494976으로 찍혀요. Python의 정수는 크기 제한이 없고, JavaScript·TypeScript·크레이콘의 수는 2^53(약 9 × 10^15)까지 정확해서 이 범위는 그대로 맞아요.
Pythonmain.py · 46 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
첫줄 = 콘솔.수들읽기();a = 첫줄[0];b = 첫줄[1];q = 첫줄[2];// 조각의 수와 가장 작은 조각의 한 변(= a와 b의 최대공약수)x = 수학.큰수(a, b);y = 수학.작은수(a, b);모두 = 0;동안 (y != 0){ 모두 = 모두 + 수학.몫(x, y); // 긴 쪽에서 짧은 쪽 크기의 정사각형이 몫만큼 나온다 t = x % y; x = y; y = t;}콘솔.쓰기(모두 + " " + x);// c번 칸, r번 줄이 든 조각의 [번호, 한 변]찾기(c, r){ 왼쪽 = 0; // 남은 종이의 왼쪽·위쪽으로 이미 잘려 나간 길이 위쪽 = 0; w = a; // 남은 종이의 가로와 세로 h = b; 센수 = 0; // 지금까지 잘라 낸 조각의 수 동안 (참) { 만약 (w >= h) { k = 수학.몫(w, h); // 왼쪽에서 h × h 조각을 k개 잘라 낸다 만약 (c - 왼쪽 <= k * h) { 돌려주기 [센수 + 수학.몫(c - 왼쪽 - 1, h) + 1, h]; } 센수 = 센수 + k; 왼쪽 = 왼쪽 + k * h; w = w - k * h; } 아니면 { k = 수학.몫(h, w); // 위쪽에서 w × w 조각을 k개 잘라 낸다 만약 (r - 위쪽 <= k * w) { 돌려주기 [센수 + 수학.몫(r - 위쪽 - 1, w) + 1, w]; } 센수 = 센수 + k; 위쪽 = 위쪽 + k * w; h = h - k * w; } }}반복 (i = 0; i < q; i++){ 줄 = 콘솔.수들읽기(); 답 = 찾기(줄[0], 줄[1]); 콘솔.쓰기(답[0] + " " + 답[1]);}