fraction

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1700 (p) Thời gian: 2.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Xét bài toán với \(n\) phân số \(\frac{a_1}{b_1}, \frac{a_2}{b_2}, ..., \frac{a_n}{b_n}\) (\(a_i, b_i\) nguyên dương), hãy tìm dãy chỉ số \(1 < i_1 < i_2 < ... < i_k \le n\) sao cho \(\frac{a_1}{b_1} < \frac{a_2}{b_2} < ... < \frac{a_k}{b_k}\)\(k\) lớn nhất.

Bài toán trên được mở rộng như sau: Hãy tìm cách đảo lại một phân số nếu muốn (phân số \(\frac{a_i}{b_i}\) đảo lại thành \(\frac{b_i}{a_i}\)), sau đó tìm dãy chỉ số thỏa mãn đề bài mà \(k\) lớn nhất có thể.

Yêu cầu: Cho \(n\) phân số và số nguyên \(w\) trong đó \(w = 0\) nghĩa là không được phép đảo bất kì phân số nào (bài toán ban đầu) hoặc \(w = 1\) nếu được đảo không quá 1 phân số (bài toán mở rộng), hãy đưa ra giá trị \(k\) lớn nhất có thể.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

  • Dòng đầu ghi hai số nguyên \(n, w\)
  • Dòng thứ \(i (i=1, 2, ..., n)\) trong \(n\) dòng tiếp theo chứa \(2\) số nguyên dương \(a_i, b_i\) có giá trị không vượt quá \(10^9\) lần lượt là tử số và mẫu số của phân số \(i\)

Output

  • Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(k\) lớn nhất tìm được.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(n \le 10; w = 0\);

  • Subtask \(2\) (\(25\%\) số điểm): \(n \le 10;w = 1\);

  • Subtask \(3\) (\(25\%\) số điểm): \(n \le 1000; w = 0\);

  • Subtask \(4\) (\(25\%\) số điểm): \(n \le 1000;w = 0\);

Có 20% số lượng test ứng với 20% số điểm có m < 10; k < n;

Example

Test 1

Input
4 0
5 1
1 3
3 2
1 2
Output
2

Test 1

Input
4 1
5 1
1 3
3 2
1 2
Output
3

Bình luận


  • 1
    haantv 12:50 a.m. 3 Tháng 8, 2020

    A/C nào giúp em bài này với ạ