Open utterances-bot opened 2 years ago
Cho em hỏi cách làm câu này ntn với ạ, nghĩ vẫn chưa ra đc ạ
hoán vị từ 1 đến n sao cho pi = a(i+1) - ai
Có ai làm được rồi cho mình xin ý tưởng từng bước hoặc pseudo code với ạ Mình cảm ơn nhiều ạ
với ví dụ trên thì 3 số hoán vị mình gọi là x y z thì 3 thằng x y z này chỉ có 1 dạng là cả 3 là duy nhất chỉ khác là x+k y+k z+k với k bất kỳ thôi thì mới có thể tạo ra cái pi đó được (theo mình thì thế) bây giờ bạn cứ cho x là bất kỳ đi mình lấy ví dụ là 1 thì chủng số là 1 -1 0 thì tạo ra 3 đứa đó ( cái này nên tự tìm hiểu, không được thì mình lại nói tiếp ) giờ thấy thằng -1 bé nhất có nghĩa nó phải thành số 1 ( tại bộ hoán vị là từ 1 -> n) thì k ở đây là 2 1+2 -1+2 0+2 3 1 2 sort mảng này nếu cấp số cộng k phải 1 thì -1 nếu là 1 thì xuất mảng đó
Để làm được bài này thì nên xem lại khái niệm hoán vị. Sau khi đã xem lại khái niệm hoán vị thì các bạn hẵng đọc tiếp nhé. Bài này khó ở chỗ ngôn từ của cái đề không clear lắm trong test case input#1: 3 là độ dài ai cũng biết rồi -2 là hiệu của số a[2] - a[1] (mảng a bắt đầu từ 1 cho dễ hiểu nhé) 1 là hiệu của số a[3] - a[2]
giả sử a[1] = x, a[2] = y, a[3] = z cho x = 1 => y = 1+( -2) = -1 => z = (-1)+ 1 = 0 ta được dãy a[1] = 1 a[2] = -1 a[3] = 0 mà hoán vị của n = n! (1=>n) nên cộng cả 3 số với (1 - min) min = a[2] = -1 ta được dãy số là output.
Khôi phục dãy số - Luyện Code Online
https://oj.luyencode.net/problem/PTIT003