Link Sub: http://www.spoj.com/PTIT/problems/VLPT12G/
Người Gửi: Dương Lee
- Problem:
Trò chơi Bi A thông thường có một bi cái (màu trắng) và 15 bi được đánh số. Người ta có thể xếp các quả bóng Bi-a theo hai cách. Cách 1: xếp thành hình vuông (gồm tất cả các bi). Cách 2: xếp thành hình tam giác, bi cái đặt ra ngoài.
Trường hợp tổng quát, ta có một viên bi cái và x viên bi đánh số. Vậy x có thể là những số nào??
Bài toán đặt ra là cho trước hai số nguyên a, b, hãy tính xem trong đoạn [a,b] có bao nhiêu số x như vậy.
Input
Mỗi bộ test ghi trên một dòng hai số a,b (0<a<b<109). Bộ test cuối cùng chứa hai số 0.
Output
Với mỗi bộ test, ghi ra một dòng có dạng Case n:k
Trong đó n là thứ tự bộ test, k là số các số nguyên x tìm thấy (a<x+1<b) sao cho x quả bi a có thể xếp thành vào một hình tam giác, x+1 quả bi có thể xếp thành hình vuông.
Example:
Với mỗi bộ test, ghi ra một dòng có dạng Case n:k
Trong đó n là thứ tự bộ test, k là số các số nguyên x tìm thấy (a<x+1<b) sao cho x quả bi a có thể xếp thành vào một hình tam giác, x+1 quả bi có thể xếp thành hình vuông.
Input
15 17
14 16
1 20
0 0
Output:
Case 1: 1
Case 2: 0
Case 3: 2
- Solution:
Bài này thực sự họ cho time limit 10s nhưng không mình không tài nào tận dụng dụng được. Đành phải ngậm ngùi làm chương trình phụ: * Side program: - Vì khoảng 1 -> 10^9 nên các bạn tìm trước trong khoảng đó có bao nhiêu số thỏa mãn (là cái phần mình chú thích trong code). p/s: Cách đặt tam giác thì nó có dạng bi-a là: 1+2+3+... = (i*(i+1))/2 = x. Cái này bạn giải phương trình tìm i là được. còn đặt vuông thì chỉ cần kiểm tra chính phương. * Main program: - Sau khi tính sẵn giá trị bên trên rồi (được 12 số gì đó ^^) thì chỉ việc chạy theo đề bài và đếm xem có bao nhiêu số k trong khoảng a,b là được. -> O(12) 0.00s