Bộ 3 cấp số nhân
Submit solution
Points:
3
Time limit:
1.0s
Memory limit:
250M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Bạn có một dãy số nguyên và nhiệm vụ của bạn là đếm số bộ 3 \((i, j, k)\) sao cho các phần tử ứng với 3 vị trí \((i, j, k)\) tạo thành một cấp số nhân với công bội là r và \((i < j < k)\)
Ví dụ: mảng A = [1, 4, 16, 64] và r = 4 thì chúng ta sẽ có 2 bộ 3 là [1, 4, 16] và [4, 16, 64] ứng với chỉ số là (0, 1, 2) và (1, 2, 3)
Input:
- Dòng đầu tiên gồm 2 số nguyên N và r tương ứng là độ dài của mảng và công bội \((1 \le N \le 10^5 , 1 \le r \le 10^9)\)
- Dòng tiếp theo gồm N số nguyên \(A_i\) với \((1 \le A_i \le 10^9)\)
Output:
In ra một số nguyên duy nhất là số bộ 3 cấp số nhân trong mảng thỏa mãn điều kiện đầu bài
Example:
Input:
4 2
1 2 2 4Output:
2Explanation:
Có 2 bộ 3 cấp số nhân ứng với chỉ số (0, 1, 3) và (0, 2, 3)
Example 2:
Input:
6 3
1 3 9 9 27 81Output:
6Explanation:
Có 6 bộ 3 cấp số nhân ứng với chỉ số (0, 1, 2), (0, 1, 3), (1, 2, 4), (1, 3, 4), (2, 4, 5), (3, 4, 5)
Comments
AD cho em hỏi bài này nên dung thuật toán nào để tối ưu nhất ạ: code em chưa tối ưu chạy: Test case #1: AC Test case #2: AC Test case #3: AC Test case #4: RTE Test case #5: RTE Test case #6: RTE Test case #7: AC Test case #8: RTE
ad cho em hỏi cái test 1 sao lại cái 0 1 2 lại là cấp số nhân ạ
Đó là cái chỉ số a[0],a[1],a[2] chứ không phải là giá trị
Ý em là 1 2 2 vs công bội là 2 ý ạ
Cảm ơn Nam, thầy sẽ sửa lại đề ngay