fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //////////////////////////////////////////////////////////////
  5. // 📌 BÀI 1: Tập con có tổng < K
  6. //////////////////////////////////////////////////////////////
  7. void bai1() {
  8.     int N, K; cin >> N >> K;
  9.     vector<int> A(N);
  10.     for (int &x : A) cin >> x;
  11.  
  12.     vector<pair<int, vector<int>>> res;
  13.     for (int mask = 1; mask < (1 << N); ++mask) {
  14.         int sum = 0;
  15.         vector<int> idx;
  16.         for (int i = 0; i < N; ++i)
  17.             if (mask >> i & 1) sum += A[i], idx.push_back(i + 1);
  18.         if (sum < K) res.push_back({sum, idx});
  19.     }
  20.  
  21.     if (res.empty()) {
  22.         cout << -1 << '\n';
  23.         return;
  24.     }
  25.  
  26.     sort(res.begin(), res.end());
  27.     for (auto &[s, v] : res) {
  28.         for (int i : v) cout << i << ' ';
  29.         cout << "\nSum = " << s << '\n';
  30.     }
  31. }
  32.  
  33. //////////////////////////////////////////////////////////////
  34. // 📌 BÀI 2: Hoán vị có độ chênh lệch > 0
  35. //////////////////////////////////////////////////////////////
  36. void bai2() {
  37.     int N; cin >> N;
  38.     vector<int> a(N);
  39.     iota(a.begin(), a.end(), 1);
  40.     do {
  41.         int diff = 0;
  42.         for (int i = 0; i < N - 1; ++i)
  43.             diff += a[i] - a[i + 1];
  44.         if (diff != 0) {
  45.             for (int x : a) cout << x << ' ';
  46.             cout << '\n';
  47.         }
  48.     } while (next_permutation(a.begin(), a.end()));
  49. }
  50.  
  51. //////////////////////////////////////////////////////////////
  52. // 📌 BÀI 3: Tìm độ dài chuỗi con nhỏ nhất chứa đủ ký tự khác nhau
  53. //////////////////////////////////////////////////////////////
  54. int solveBai3(string s) {
  55.     set<char> all(s.begin(), s.end());
  56.     map<char, int> count;
  57.     int need = all.size(), have = 0;
  58.     int res = s.size(), left = 0;
  59.  
  60.     for (int right = 0; right < s.size(); ++right) {
  61.         if (++count[s[right]] == 1) have++;
  62.         while (have == need) {
  63.             res = min(res, right - left + 1);
  64.             if (--count[s[left++]] == 0) have--;
  65.         }
  66.     }
  67.     return res;
  68. }
  69.  
  70. void bai3() {
  71.     int T; cin >> T;
  72.     cin.ignore();
  73.     while (T--) {
  74.         string s;
  75.         getline(cin, s);
  76.         cout << solveBai3(s) << '\n';
  77.     }
  78. }
  79.  
  80. //////////////////////////////////////////////////////////////
  81. // 📌 BÀI 4: Đếm số lượng ký tự 'B' trong k vị trí đầu tiên của F[n]
  82. //////////////////////////////////////////////////////////////
  83. const int MAXN = 46;
  84. long long len[MAXN];
  85.  
  86. int countB(int n, long long k) {
  87.     if (n == 0) return 0;
  88.     if (n == 1) return (k >= 1);
  89.     if (k <= len[n - 1])
  90.         return countB(n - 1, k);
  91.     else
  92.         return countB(n - 1, len[n - 1]) + countB(n - 2, k - len[n - 1]);
  93. }
  94.  
  95. void bai4() {
  96.     len[0] = 1; len[1] = 1;
  97.     for (int i = 2; i < MAXN; ++i)
  98.         len[i] = len[i - 1] + len[i - 2];
  99.  
  100.     int T; cin >> T;
  101.     while (T--) {
  102.         int n;
  103.         long long k;
  104.         cin >> n >> k;
  105.         cout << countB(n, k) << '\n';
  106.     }
  107. }
  108.  
  109. //////////////////////////////////////////////////////////////
  110. // 🔘 MENU CHỌN BÀI
  111. //////////////////////////////////////////////////////////////
  112. int main() {
  113.     cout << "Nhap so bai muon chay:\n";
  114.     cout << "1. Tap con co tong < K\n";
  115.     cout << "2. Hoan vi co do chenh lech > 0\n";
  116.     cout << "3. Chuoi con nho nhat chua du ky tu\n";
  117.     cout << "4. Dem so ky tu 'B' trong k vi tri dau F[n]\n";
  118.     cout << "Nhap lua chon (1-4): ";
  119.  
  120.     int choice;
  121.     cin >> choice;
  122.  
  123.     switch (choice) {
  124.         case 1: bai1(); break;
  125.         case 2: bai2(); break;
  126.         case 3: bai3(); break;
  127.         case 4: bai4(); break;
  128.         default: cout << "Lua chon khong hop le!\n";
  129.     }
  130.  
  131.     return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nhap so bai muon chay:
1. Tap con co tong < K
2. Hoan vi co do chenh lech > 0
3. Chuoi con nho nhat chua du ky tu
4. Dem so ky tu 'B' trong k vi tri dau F[n]
Nhap lua chon (1-4): Lua chon khong hop le!
https://ideone.com/jDq3Zk
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!