VM 13 Bài 17 - Bé và Domino

View as PDF

Submit solution


Points: 1.36 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM13 - Nguyễn Thành Trung, Phạm Quang Vũ
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bé năm nay ~15~ tuổi, học hết lớp ~9~, ở cái tuổi mà Bé đã bắt đầu có những tò mò về chuyện giải toán. Hàng ngày, Bé luôn mơ ước được ngắm nhìn những bài toán hóc búa, quyến rũ. Biết Bé đam mê giải toán, cô giáo vui lắm. Hôm nay cô cho Bé một bài toán:

Cho một bảng ô vuông kích thước ~M \times N~ (~M~ và ~N~ chẵn). Trên bảng có ~2~ ô cấm (~x~, ~y~) và (~u~, ~v~). Yêu cầu: đặt các quân domino lên bảng, sao cho mỗi ô trên bảng có đúng ~1~ viên domino đặt lên, và không có quân domino đặt lên ô cấm. Quân domino có dạng hình chữ nhật ~1 \times 2~ hoặc ~2 \times 1~.

Dĩ nhiên, việc tìm ~1~ cách đặt với Bé là quá dễ, vì vậy, cô yêu cầu Bé phải tìm được ~10~ cách đặt khác nhau thì mới được điểm ~10~ (mỗi cách ~1~ điểm). Bạn có thể giúp bé được bao nhiêu điểm? Hai cách đặt được gọi là khác nhau nếu tồn tại hai quân domino (mỗi quân thuộc một cách) có đúng ~1~ ô chung. Ví dụ quân domino đặt ở vị trí (~1~, ~1~) - (~1~, ~2~) và quân domino đặt ở vị trí (~1~, ~2~) - (~2~, ~2~) là hai quân domino có đúng ~1~ ô chung (~1~, ~2~).

Input

  • Dòng ~1~ chứa ~2~ số nguyên ~M~ và ~N~.
  • Dòng ~2~ chứa ~2~ số nguyên ~x~ và ~y~.
  • Dòng ~3~ chứa ~2~ số nguyên ~u~ và ~v~.

Output

  • Dòng ~1~ in ra ~K~ là số cách bạn tìm được. (~0 \leq K \leq 10~)
  • ~K~ nhóm dòng sau, mỗi nhóm chứa ~\frac{M \times N}{2} - 1~ dòng, dòng thứ ~i~ in ra ~4~ số ~x_1~, ~y_1~, ~x_2~ và ~y_2~ tương ứng với ~2~ ô bạn đặt quân domino thứ ~i~ là (~x_1~, ~y_1~) và (~x_2~, ~y_2~).

Giới hạn

  • ~10 \leq M~, ~N \leq 100~
  • ~1 \leq x~, ~u \leq M~
  • ~1 \leq y~, ~v \leq N~
  • ~2~ ô cấm là ~2~ ô khác nhau.
  • Dữ liệu đảm bảo tồn tại ít nhất ~10~ cách đặt.

  • Bài của bạn sẽ được chấm trên thang điểm 100. Bộ test chính thức gồm 20 test, mỗi test tương ứng với 5 điểm, với một cách đặt đúng trong mỗi test bạn sẽ được 0.5 điểm. Điểm mà bạn nhận được sẽ tương ứng với tổng số điểm bạn đạt được ở mỗi test.

  • Nếu bạn xuất ra một cách không hợp lệ (đặt domino lên ô cấm, đặt 2 quân domino lên cùng 1 ô, ...) hoặc trong output của bạn có 2 cách đặt giống nhau, bạn sẽ không được điểm cho toàn bộ test đó.

Sample Input

2 4
1 3
2 1

Sample Output

1
1 1 1 2
1 4 2 4
2 2 2 3

Note

Lưu ý, test ví dụ chỉ giúp các bạn hình dung về định dạng của input và output, tất cả các test trong bộ test chính thức đều thỏa điều kiện đã nêu trong đề bài.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.