[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Đếm tam giác
Cho 3 dãy số dương A, B, C cùng có N phần tử. Hãy đếm xem có bao nhiêu bộ3 sốA, B[j] và C[k] mà 3 số này là 3 cạnh của 1 tam giác.
Dữ liệu vào: từ file TRIANGLE.INP với cấu trúc:
- Dòng đầu chứa số nguyên dương N (N≤1000)
- Dòng thứ hai chứa các số A1, A2, ..., AN.
- Dòng thứ ba chứa các số B1, B2, ..., BN.
- Dòng thứ tư chứa các số C1, C2, ..., CN.
Các số Ai, Bi, Ci đều không vượt quá 109 và được ghi cách nhau bởi dấu cách.
Kết quả: file văn bản TRIANGLE.OUT gồm một sốS duy nhất là sốlượng bộba sốtìm
được.
Test
[TBODY]
[/TBODY]
Thật sự mình cũng làm rồi mà không biết sai ở đâu:
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
long long n,i,j,first,final,l,r,m,ans=0;
long long a[100000],b[100000],c[100000];
long long cnp(long long x)
{
l=1; r=n;
while (r>=l)
{
m=(l+r)/2;
if (c[m]>x) r=m-1;
else l=m+1;
}
return l;
}
long long tknp(long long y)
{
l=1; r=n;
while (r>=l)
{
m=(l+r)/2;
if (c[m]>y) r=m-1;
else l=m+1;
}
return l;
}
int main()
{
scanf("%lld",&n);
for (i=1;i<=n;i++) scanf("%lld",&a);
for (i=1;i<=n;i++) scanf("%lld",&b);
for (i=1;i<=n;i++) scanf("%lld",&c);
sort(a+1,a+n+1);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (abs(a-b[j])<c[n])
if (a+b[j]>c[1])
{
first=cnp(abs(a-b[j]));
final=tknp(a+b[j]);
}
if (final>=first) ans=ans+final-first+1;
printf("%lld %lld\n",first,final);
}
printf("%lld",ans);
}
Cho 3 dãy số dương A, B, C cùng có N phần tử. Hãy đếm xem có bao nhiêu bộ3 sốA, B[j] và C[k] mà 3 số này là 3 cạnh của 1 tam giác.
Dữ liệu vào: từ file TRIANGLE.INP với cấu trúc:
- Dòng đầu chứa số nguyên dương N (N≤1000)
- Dòng thứ hai chứa các số A1, A2, ..., AN.
- Dòng thứ ba chứa các số B1, B2, ..., BN.
- Dòng thứ tư chứa các số C1, C2, ..., CN.
Các số Ai, Bi, Ci đều không vượt quá 109 và được ghi cách nhau bởi dấu cách.
Kết quả: file văn bản TRIANGLE.OUT gồm một sốS duy nhất là sốlượng bộba sốtìm
được.
Test
| Input | Output |
| 2 2 3 3 1 4 7 | 2 |
| 3 2 3 1 4 4 9 8 5 2 | 8 |
Thật sự mình cũng làm rồi mà không biết sai ở đâu:
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
long long n,i,j,first,final,l,r,m,ans=0;
long long a[100000],b[100000],c[100000];
long long cnp(long long x)
{
l=1; r=n;
while (r>=l)
{
m=(l+r)/2;
if (c[m]>x) r=m-1;
else l=m+1;
}
return l;
}
long long tknp(long long y)
{
l=1; r=n;
while (r>=l)
{
m=(l+r)/2;
if (c[m]>y) r=m-1;
else l=m+1;
}
return l;
}
int main()
{
scanf("%lld",&n);
for (i=1;i<=n;i++) scanf("%lld",&a);
for (i=1;i<=n;i++) scanf("%lld",&b);
for (i=1;i<=n;i++) scanf("%lld",&c);
sort(a+1,a+n+1);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (abs(a-b[j])<c[n])
if (a+b[j]>c[1])
{
first=cnp(abs(a-b[j]));
final=tknp(a+b[j]);
}
if (final>=first) ans=ans+final-first+1;
printf("%lld %lld\n",first,final);
}
printf("%lld",ans);
}
