Những bài code trâu ba vòng for thì nên xử lý như thế nào?

[ducviet00]

Ví dụ như bài này:

Được học về định lí Py-ta-go đảo, Tèo biết rằng “Nếu một tam giác có bình phương của một cạnh bằng tổng các bình phương của hai cạnh kia thì tam giác đó là tam giác vuông”. Tèo viết lên giấy N số nguyên dương đôi một khác nhau a1, a2,…, aN. Tèo muốn chọn một bộ ba số (ai, aj, ak) với ai < aj < ak và i ≠ j ≠ k sao cho ba số này là độ dài ba cạnh của một tam giác vuông.
Ví dụ: Với N = 6 và dãy 1, 2, 3, 5, 7, 4. Tèo có 1 cách chọn bộ số thoả mãn là độ dài ba cạnh của một tam giác vuông (3, 4, 5) vì 3^2 + 4^2 = 5^2.
Yêu cầu: Hỏi Tèo có bao nhiêu cách chọn một bộ số như trên.
Dữ liệu: Vào từ tệp văn bản “TRIANGLE.INP” gồm:
• Dòng 1: Ghi số nguyên dương N (3 ≤ N ≤ 1000).
• Dòng 2: Ghi N số nguyên dương a1, a2,…, aN đôi một khác nhau (ai ≤ 105).
Kết quả: Ghi ra tệp văn bản “TRIANGLE.OUT” số nguyên duy nhất là kết quả tìm được.

Hoặc bài này.

Cho N, dãy a[1], a[2],…, a[n] và một số nguyên S. Hãy liệt kê các dãy con có K phần tử 1 ≤ x1 < x2 < … < xk ≤ n sao cho: a[x1] + a[x2] +…+ a[xk] = S.
SUMK.INP SUMK.OUT
7 3 20
8 6 7 10 5 4 6 1 2 7
1 3 5
2 4 6
4 6 7
Dữ liệu: Vào từ tệp văn bản ‘SUMK.INP’ gồm:
• Dòng 1: Số nguyên dương N, K, S.
• Dòng 2: Ghi N số nguyên ai.
Với K ≤ N ≤ 100, S ≤ 1000, |ai| < 1000.
Kết quả: Ghi ra tệp văn bản ‘SUMK.OUT’ gồm nhiều dòng, mỗi dòng là chỉ số các phần tử được chọn. Nếu không có cách chọn ghi ra -1.
Giải thích: Dòng 1 chọn các phần tử (1, 2, 7) có tổng: 8+6+6 = 20;…

Em nghĩ là dùng thêm 1 mảng. Sau đó ví dụ nhập vào 1, 5, 7 thì gán giá trị b[1],b[5],b[7] là 1 còn các phần tử khác là 0. for 2 vòng rồi check xem phần tử thứ 3 có trong mảng hay không.
Hay đây phải dùng quy hoạch động ạ? Em chưa học quy hoạch động

[Duong_Act (Lão Hạc)]

Thì 3 vòng for mà giã thôi có làm sao đâu ?

[ducviet00]

3 vòng k sợ bị lâu ạ?

[Duong_Act (Lão Hạc)]

Bị lâu không cứ test là biết liền.
Đấy mới là cách chính xác chứ không phải nhiều hay ít for.

[tntxtnt]

bài đầu bạn có thể tạo bộ 3 Pytago bằng công thức Euclid ở đây: https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple

chỉ cần chạy 2 số m,n nguyên tố cùng nhau, m > n, m - n ko chia hết cho 2, m² + n² < max(A_i) = 10⁵ là tính ra được tất cả bộ ba Pytago:
a = m² - n²
b = 2mn
c = m² + n²
rồi bạn chỉ cần kiểm tra bộ ba (a,b,c) có ở trong dãy số cho trước là được (sắp xếp dãy A cho trước rồi tìm a,b,c theo tìm kiếm nhị phân cho lẹ)

[HongCuong98 (Nguyễn Hồng Cường)]

Đùa chư lớp mình có đứa giải bài toán ma trận bằng 12 vòng lặp for,đứa ít hơn thì 6 cái -.-

[ducviet00]

Tại em sợ nó không chạy hết test nên mới hỏi xem có thuật toán nào không thôi
Em cảm ơn ạ

[LongvnXD]

2 vòng như này ổn ko ad chứ mình thấy nghi nghi=)

#include<bits/stdc++.h>
using ll = long long;
using namespace std;

struct dl {
vector v;
bool check()
{
return v.empty();
}
void update(ll x)
{
v.push_back(x);
}
void xuat(ll a,ll b)
{
for(auto x:v)
{
cout << x << " " << a << " " << b << “\n”;
}
}
};

ll n, check=0;
double a[1000006];
map<double,dl> v;
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(ll i=1; i<=n; i++) cin >> a[i];
v[a[1]].update(1);
for(ll i=2; i<n; i++)
{
for(ll j=i+1; j<=n; j++)
{
double k1 = sqrt(a[i]*a[i]+a[j]*a[j]);
double k2 = sqrt(a[i]*a[i]-a[j]*a[j]);
double k3 = sqrt(a[j]*a[j]-a[i]*a[i]);
if(!v[k1].check())
v[k1].xuat(i,j), check=1
if(!v[k2].check())
v[k2].xuat(i,j), check=1;
if(!v[k3].check())
v[k3].xuat(i,j), check=1;
}
v[a[i]].update(i);
}
if(check==0)
cout << -1;
return 0;
}