Ước lượng kích thước dữ liệu tối đa xử lí được của Sở Giáo dục

Trung tâm dữ liệu của Sở Giáo dục quản lí hồ sơ học sinh toàn tỉnh. Máy chủ thực hiện mỗi phép tính cơ bản trong 1 micro giây (10^-6 giây), giống ví dụ ước lượng đã học ở phần Vận dụng. Với mỗi truy vấn, cho biết tên thuật toán được dùng (LinearSearch, SelectionSort hoặc BubbleSort) và thời gian xử lí tối đa cho phép t (đơn vị: giây, có thể là số thực), hãy xác định kích thước dữ liệu n lớn nhất mà thuật toán có thể xử lí xong trong thời gian đó.

Vận dụng độ phức tạp O-lớn đã xác định trong bài học: LinearSearch có độ phức tạp O(n) nên T(n) ≈ n; SelectionSort và BubbleSort đều có độ phức tạp O(n²) nên T(n) ≈ n². Gọi B = t × 10^6 là tổng số phép tính cơ bản tối đa có thể thực hiện. Với thuật toán O(n): n_max ≈ B (lấy phần nguyên). Với thuật toán O(n²): n_max ≈ √B (lấy phần nguyên).

Input: dòng đầu là số nguyên q (số truy vấn, 1 ≤ q ≤ 8); tiếp theo q dòng, mỗi dòng gồm tên thuật toán và thời gian t (giây), cách nhau bởi khoảng trắng.

Output: q dòng, mỗi dòng in ra n_max (số nguyên, lấy phần nguyên) tương ứng với từng truy vấn theo đúng thứ tự.

Ví dụ (các dòng input/output được ngăn cách bởi dấu ; để hiển thị trong bảng, thực tế mỗi phần tử nằm trên một dòng riêng):