Editorial for Bedao Mini Contest 13 - FRACPATH


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask ~1~:

Ta sinh cây có độ sâu tối đa là ~17~. Sau đó truy vết đường đi trên cây một cách đơn giản.

Subtask ~2~:

Nếu ta có hai phân số ~\frac{a}{b}~ < ~\frac{c}{d}~, ta luôn chứng minh được rằng ~\frac{a}{b} < \frac{a + c}{b + d} < \frac{c}{d}~. Ta sẽ biết được nên đi theo cây con gốc phải nếu ~\frac{a + c}{b + d} < \frac{x}{y}~. Và đi theo cây con gốc trái trong trường hợp ngược lại. Cài đặt thuật toán này tương tự chặt nhị phân. Việc so sánh hai phân số có thể dùng tích chéo.

Subtask ~3~:

Việc khó duy nhất lúc này là so sánh hai phân số. Nếu dùng double hoặc tích chéo long long sẽ xảy ra hiện tượng chạy vô hạn do sai số. Ngoài cách sử dụng bignum hoặc python ra, chúng ta có thể đệ quy để so sánh hai phân số trong thời gian chạy rất nhanh.

Giả sử ta cần so sánh hai phân số ~\frac{a}{b}~ và ~\frac{c}{d}~. Ta quy về hỗn số có phần nguyên lớn nhất: ~\frac{a}{b} = e_1\frac{r_1}{b}~ với ~a = b \times e_1 + r_1~. Tương tự ~\frac{c}{d} = e_2\frac{r_2}{d}~ với ~c = d \times e_2 + r_2~. Khi đó nếu ~e_1 > e_2~ thì ~\frac{a}{b} > \frac{c}{d}~. Nếu ~e_1 < e_2~ thì ~\frac{a}{b} < \frac{c}{d}~. Nếu ~e_1 = e_2~, ta so sánh tiếp ~\frac{b}{r_1}~ và ~\frac{d}{r_2}~ bằng đệ quy. Cứ làm như vậy đến khi ~r_1 = 0~ hoặc ~r_2 = 0~ hoặc tìm ra đáp án.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.