EVENODDS - Chẵn - Lẻ
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.1s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Là một người khó tính, Nam thường xuyên không hài lòng với tình trạng hiện tại của sự vật, đặc biệt với thứ tự của các số tự nhiên nguyên dương. Cậu quyết tâm sắp xếp lại chúng. Nhưng có quá nhiều số tự nhiên, vì vậy Nam quyết định bắt đầu với ~n~ số đầu tiên. Nam viết xuống dãy số sau đây: trước hết là tất cả các số nguyên lẻ từ ~1~ đến ~n~ (theo thứ tự tăng dần), sau đó tất cả các số nguyên chẵn từ ~1~ đến ~n~ (cũng theo thứ tự tăng dần).
Yêu cầu: Giúp Nam tìm số đứng ở vị trí thứ ~K~.
Input
~2~ số nguyên dương ~n~ và ~K~.
Ràng buộc:
- ~1 \le n, K \le 10^{100}~
Output
Số đứng ở vị trí thứ ~K~ trong dãy mà Nam đã sắp xếp
Sample
Input #1
10 3
Output #1
5
Input #2
7 7
Output #2
6
Hint
Giải thích #1:
- Ta thu được dãy: ~1, 3, 5, 7, 9, 2, 4, 6, 8, 10~ số thứ ~3~ là số ~5~.
Giải thích #2:
- Ta thu được dãy: ~1, 3, 5, 7, 2, 4, 6~ số thứ ~7~ là số ~6~
Bình luận
Ý tưởng: Bài này với cách làm của mình không AC bằng c++ được do số to quá, dùng python thì ok
Ta thấy từ 1 -> n: Nếu n % 2 == 0 thì số lượng số lẻ = số lượng số chẵn. Ngược lại thì số lượng số lẻ = số lượng số chẵn + 1. Từ đó ta suy ra vị trí chốt (mình gọi là v) là n // 2 (nếu n chẵn), hoặc n // 2 + 1 (nếu n lẻ). Từ đây ta bắt đầu tim vị trí số k.
Quy luật là 1, 3, 5, ..., [chốt v (chưa biết giá trị nhé)], 2, 4, 6, ... Nếu k <= v thì chắc chắn là lẻ, ngược lại k > v thì chắc chắn được số chẵn.
TH1: k <= v, được số lẻ, ta phân tích dãy số lẻ: 1, 3, 5, 7, ... = 1, 1 + 2, 1 + 2 + 2, 1 + 2 + 2 + 2,... = 1, 1 + 1.2, 1 + 2.2, 1 + 3.2,..., 1 + X.2. Ta thấy ngay X = vị trí - 1 của dãy trên (mà vị trí chính là k) => để tìm số vị trí thứ k: 1 + (k - 1) * 2 là ra.
TH2: k > v, được số chẵn, ta phần tích bên dãy số chẵn: 2, 4, 6, 8, ... = 2, 2 + 2, 2 + 2 + 2, 2 + 2 + 2 + 2, ... = 2, 2 + 1.2, 2 + 2.2, 2 + 3.2, ... 2 + Y.2. Ta thấy ngay Y = vị trí - 1 của dãy trên (lúc này Y != k mà Y = k - v - 1, đoạn này các bạn tự suy luận nhé) => để tìm số vị trí thứ k: 2 + (k - v - 1) * 2 là ra.
Phân tích thì dài vậy. chứ code thì if_else 10, 11 dòng thôi. Mình thấy có cách hay hơn AC đc c++, ai biết có thể comment nhé.
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG
Mình đã AC bằng ngôn ngữ C++ nhé, bạn có thể tham khảo <3
Về cơ bản thì mình dựa trên 3 hàm xử lí số lớn cơ bản là CỘNG, TRỪ và NHÂN
Sau đó thì dùng Toán xử lí 2 TH giống bạn, khác mỗi đoạn số chẵn thôi tại mình không dùng "Chốt v" giống bạn