Nội dung buổi offline 03, ngày 11/12/2016

Nội dung buổi offline 11/12/2016

Phần 1: Chữa bài cũ.

ATM đi thi: http://eggclub.org/2016/12/08/bai-tap-tuan-5-atm-thi-lap-trinh/

Hướng giải quyết:

  • Ý tưởng chung của các bạn là sắp xếp khả năng lập trình của hai đội từ lớn đến bé, sau đó ghép cặp người có khả năng lập trình a[i] của đội mình với người có khả năng lập trình b[j] của đội bạn sao cho b[j-1] > a[i] > b[j] . Cách này có nhược điểm là khó xét trường hợp của những người có khả năng lập trình bằng nhau, dẫn đến với một số bộ dữ liệu thì nhận được thông báo là “không thể thắng”, nhưng thực tế thì có thể ghép cặp để đội mình giành chiến thắng.
  • Bạn Vũ Minh Quân đề xuất ý tưởng là xét 2 dãy số đó theo hai chiều, từ trái sang phải và từ phải sang trái, nếu chỉ cần thấy một trong hay chiều có cách ghép để thắng thì cho kết quả là thắng, còn nếu cả hai chiều đề không tìm được cách để thắng thì thông báo “không thể thắng”. Bạn Quân đã chứng minh tính đúng đắn của thuật toán như sau :

Chứng minh thuật toán tìm cách giúp team ATM chiến thắng:
1. Gỉa sử 1 trận thắng +3 điểm, 1 trận hòa +0 điểm, 1 trận thua -3 điểm. (điều kiện thắng sẽ là tổng điểm của team ATM > 0).
2. Như vậy yêu cầu bài toán đặt ra là ghép cặp sao cho điểm của team ATM lớn nhất (Vì sao phải lớn nhất, do điểm lớn nhất của team ATM mà <= 0 thì chắc chắn team ATM không thể chiến thắng).
3. Ta nhận thấy team ATM có tổng điểm lớn nhất khi có số trận thắng lớn nhất, do đó ta sẽ đi tìm số trận thắng lớn nhất. Nếu số trận thắng lớn nhất > n/2, ta kết luận luôn team ATM có thể chiến thắng.
4. Nếu không thỏa, bằng thủ thuật ta sẽ tìm trên phần còn lại của 2 dãy, tìm số trận hòa, lúc này điều kiện thắng sẽ là 2 * win + draw > n (Chứng minh win + lose + draw = n => lose = n – win – draw, thắng khi win > lose <=> win > n – win – draw.
5. Lúc này tưởng chừng chúng ta đã có tổng điểm lớn nhất với số trận thắng tối đa và số trận hòa. Nhưng liệu có phép đổi cặp nào cho ta kết qủa lớn hơn không? Hoàn toàn có: Nếu ta thay 1 win + 1 lose thành 1 win + 1 draw .
6. Sao không phải là 1 win + 1 draw thành 2 win, cái này không thể được do chúng ta lúc đầu đã tìm số trận thắng tối đa rồi nên không thể tăng số trận thắng lên được do đó chỉ có cách tăng điểm bằng cách thay 1 lose thành 1 draw.
7. Xét các trường hợp draw + lose => draw + draw, lose + lose => lose + draw hoặc draw + draw. Các trường này không xảy được, ví dụ lose + lose => lose + draw, nếu có trường hợp này thì draw ta đã tính ở câu trên rồi. Cuối cùng chỉ có win + lose => win + draw là có thể xảy ra.

Vậy làm cách nào để đổi được. Ta xét mô hình sau:

  • Trong thuật toán đã dùng ở bài trên khi tìm số trận thắng lớn nhất ta nhận được cặp đấu a – c, b – a (1 win + 1 lose), mà với mô hình trên chúng ta hoàn toàn có thể ghép cặp lại a – a, b – c (1 draw + 1 win). Do đó cách mình đề xuất là chúng ta sẽ duyệt ngược lại từ cuối lên bằng thuật toán tương tự như trên.
  • Nếu cuối cùng sau khi duyệt từ cuối lên mà team ATM vẫn không tăng điểm nghĩa là không tồn tại mô hình này. Do đó ta kết luận team ATM không thể chiến thắng.

P/s: Cách đảo xâu chưa chắc chắn lắm nên mình đề xuất cách này:
Sau khi biết được các cặp thắng, hòa và thua. Ta đưa những thành viên chiến thắng bên mình vào mảng 1, những thành viên chiến thắng của đội bạn vào mảng 2. Bây giờ ta duyệt 2 mảng này để tìm mô hình ở trên (Win + Lose => Win +Draw). Ví dụ test case sau:

Ta có :

  • mảng 1: 70 (ghép cặp với 1) (team ATM)
  • mảng 2: 70 (ghép cặp với 3) (team đối thủ)
  • Ta tìm được 70 = 70, nghĩa là ta có
    Bây giờ xét nếu 3 > 1, nghĩa là lúc này ta có:
    Lúc này ta tăng đổi lại cặp đấu và tăng điểm của team ATM lên nếu > 0 rồi thì dừng lại, nếu chưa thì xét cho đến hết mảng. Đến đây mà tổng điểm <= 0 thì thông báo team ATM không thể chiến thắng.
  • Code của bạn Quân: http://codepad.org/QjMEUK143

Phần 2: Bài mới.

ATM đi bán hàng : http://eggclub.org/2016/12/14/bai-tap-7-atm-di-ban-hang/

Hướng giải quyết:

  • Part 1: Cách giải quyết đơn giản nhất là chúng ta kiểm tra mảng ngày (a[i]), những khách nào mua hàng cùng ngày thì sẽ cộng tổng số lượng b[i] của các khách đó, ngày nào không có khách mua thì sẽ in ra 0.
  • Part 2:
    • Ý 1: Lưu tổng số hàng của các ngày vào một mảng, ví dụ ngày thứ i thì tổng lượng mua là 1ngay[i], sau đó gán biến Max = 1ngay[0] rồi so sánh với các phần tử còn lại trong mảng, tìm ra ngày có lượng mua nhiều nhất.
    • Ý 2: Kiểm tra lượng mua của từng ngày, nếu lượng mua của ngày i có giá trị bằng 0, tức là không có khách hàng mua thì xuất ra kết quả “ngày i không có người mua hàng”.
  • Part 3: Cách đơn giản nhất là chúng ta tính tổng lượng mua từ ngày i đến ngày j :
Có 1 cách nữa nhanh hơn đó là tạo một mảng S[i], sau đó gán  S[i]=1ngay[i-1] + 1ngay[i], rồi tính tổng lượng mua từ ngày i đến ngày j bằng cách lấy S[j]-S[i-1].

  • Part 4: Anh Cường Trần đề xuất ý tưởng là tạo hai biến start và end. Ban đầu, gán start = -1, end = -1, sau đó xét mảng 1ngay[i], nếu từ ngày i đến ngày j không có khách nào mua hàng thì gán start = i, end = j, in ra file, sau đó lại gán start = -1, end = -1 và tiếp tục xét các phần tử còn lại của mảng.
The following two tabs change content below.