Tháp Đỏ-Xanh

Đề bài

Mô tả

Bạn có r khối màu đỏ và g khối màu xanh để xây một tòa tháp đỏ-xanh theo các quy tắc sau:

  • Tháp gồm một số tầng.
  • Nếu tháp có n tầng thì tầng thứ nhất gồm n khối, tầng thứ hai gồm n1 khối, ..., tầng cuối cùng gồm đúng 1 khối. Nói cách khác, mỗi tầng có ít hơn tầng ngay trên nó (tính từ dưới lên) đúng một khối.
  • Mỗi tầng chỉ được dùng các khối cùng một màu.

Gọi h là số tầng lớn nhất có thể của một tòa tháp xây được từ r khối đỏ và g khối xanh thỏa các quy tắc trên. Nhiệm vụ của bạn là đếm số tòa tháp khác nhau có đúng h tầng có thể xây được.

Hai tòa tháp được coi là khác nhau nếu tồn tại một tầng mà ở tháp này gồm các khối đỏ còn ở tháp kia gồm các khối xanh.

Hãy in ra số tòa tháp khác nhau có đúng h tầng theo modulo 109+7.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên rg — số khối đỏ và số khối xanh.

Dữ liệu ra

In ra một số nguyên duy nhất — số tòa tháp khác nhau có đúng h tầng, theo modulo 109+7.

Ràng buộc

  • 0r,g2·105
  • r+g1

Ví dụ

Input Output Giải thích
4 6 2 Số tầng tối đa là h=4 (cần 1+2+3+4=10 khối, vừa đủ r+g=10). Tầng cỡ 4 phải là xanh (chỉ có 4 đỏ). Phần còn lại cần tô màu cho các tầng 1,2,3 sao cho dùng đúng 4 đỏ: hoặc tầng cỡ 4... thực chất có đúng 2 cách hợp lệ.
9 7 6 Số tầng tối đa h=5 (cần 15 khối, có 16). Có 6 cách phân màu hợp lệ.
1 1 2 h=1: tháp một tầng cỡ 1, có thể là đỏ hoặc xanh, tổng cộng 2 cách.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0