English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/brtree

Cây bánh mì là một loài cây chuyên sản xuất bánh mì. Ở năm đầu tiên, một cây bánh mì chỉ có một nút với một chiếc bánh mì có trọng lượng 0 ở nút đó, gọi là nút 0. Cứ mỗi năm sau đó, trọng lượng của bánh mì trên mỗi nút của cây sẽ tăng thêm 1, và một cành với một nút 0 sẽ mọc thêm vào cuối mỗi nút. Tuy nhiên, có một giới hạn về số cành trên mỗi nút. Tức là, khi số lượng cành của một nút đạt đến giới hạn thì sẽ không có thêm cành nào mọc thêm ở nút đó nữa, nhưng trọng lượng của chiếc bánh mì của nó thì vẫn tăng lên. Thêm vào đó, một cây bánh mì sẽ không thay đổi nữa khi mà tổng trọng lượng của những chiếc bánh mì trên nó lớn hơn 1234567890.

Input

Có nhiều bộ test, mỗi bộ test gồm 2 số nguyên N và K trên 1 dòng. N và K đều là các số nguyên dương 32-bit. N bằng 0 đánh dấu kết thúc input và không cần xử lí.

Output

Với mỗi bộ test, viết ra tổng trọng lượng của những chiếc bánh mì trên cây vào năm thứ N, khi biết giới hạn số cành là K.

Example

Input:
10000 0
101 1
10 2
1221 128
0 0

Output:
9999
5050
221
2147483647

---

hide comments

	noedelorme: 2021-07-20 02:11:51 [Fixed] I have really fast solution which seems to work on every test I can imagine. But I still have a WA. Is there any way to access the input file (or maybe only the test case that doesn't work)? Last edit: 2021-07-20 19:49:57
	noedelorme: 2021-07-19 22:52:36 @legsleg True, my bad :-)
	legsleg: 2021-07-19 10:07:48 The worst-case input regarding running-time is actually (most probably) something else. Last edit: 2021-07-19 10:11:07
	jacomo: 2021-07-17 13:10:25 @noedelorme: It's done in under 0.1s Last edit: 2021-07-17 13:10:42
	noedelorme: 2021-07-17 08:39:22 You can try with the worst case, which is the following (because 2147483647 is the maximal positive signed 32-bit integer) : 2147483647 2147483647 0 0
	jacomo: 2021-07-13 09:16:24 Getting always a TLE , but don't know why. Is it possible to get an example for the testcase inputs?