Hình chữ nhật - LCOJ: Luyện Code Online Judge

MAREC - Hình chữ nhật

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

aprocoder

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho n que diêm có độ dài ~ a_1, a_2, ..., a_n ~.

Hãy đếm xem có thể ghép được bao nhiêu hình chữ nhật khác nhau từ các que diêm trên, biết rằng mỗi hình chữ nhật được tạo thành từ 4 que diêm.

Hai hình chữ nhật được coi là khác nhau nếu chúng không có cùng chiều dài và chiều rộng.

Input

• Dòng thứ nhất gồm một số nguyên dương n (4 ≤ n ≤ 1000).

• Dòng thứ hai gồm n số nguyên dương ~ a_1, a_2, ..., a_n ~ (~ 1 ≤ a_i ≤ 1000 ~).

Output

• In ra một số nguyên là số hình chữ nhật khác nhau có thể tạo thành.

Sample

Input #1

9
2 4 5 2 2 4 5 4 3

Output #1

Input #2

8
2 2 2 2 2 2 2 2

Output #2

Problem source: Beginner Free Contest 31

Bình luận

Please read the guidelines before commenting.

Hint:

Đếm số que mỗi độ dài.
Chỉ quan tâm độ dài có ≥ 2 que.
Chọn 2 độ dài khác nhau → 1 hình chữ nhật.
Chọn 1 độ dài có ≥ 4 que → 1 hình vuông.
Đáp án = C(k,2) + số độ dài có ≥ 4 que.

code tham khảo (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n;
  cin>>n;
  map<int, int> mp;
  for(int i = 1, x; i <= n; ++i)
    cin>>x, mp[x]++;
  vector<int> v;
  for(auto &p : mp)
    if(p.second >= 2) v.push_back(p.first);
  long long ans = 1ll*v.size()*(v.size()-1)/2;
  for(auto &p : mp)
    if(p.second >= 4) ++ans;
  cout<<ans;
  return 0;
}

0

phucdeptraipro đã bình luận lúc 25, Tháng 7, 2025, 11:56

cho tui xin ý tưởng làm bài