Overview
Brute force methods involve systematically enumerating all possible solutions to find valid answers. This approach is particularly useful in competitive programming contexts like the Blue Bridge Cup, where problems often require checking combinations or permutations within defined constraints.
Problem Solutions
Problem 1: Hundred Coins for Hundred Chickens
Description:
An ancient Chinese mathematical problem involving buying exactly 100 chickens with 100 coins. Given:
- Rooster costs 5 coins
- Hen costs 3 coins
- Three chicks cost 1 coin
Find how many of each type can be bought.
Solution Approach:
Use nested loops to iterate through all possible numbers of roosters and hens, then calculate remaining chicks to satisfy both total count and cost constraints.
#include <iostream>
using namespace std;
int main() {
int roosters, hens, chicks;
for (roosters = 0; roosters <= 20; roosters++) {
for (hens = 0; hens <= 33; hens++) {
chicks = 100 - roosters - hens;
if (chicks >= 0 && (5 * roosters + 3 * hens + chicks / 3) == 100 && chicks % 3 == 0) {
cout << "Roosters: " << roosters << ", Hens: " << hens << ", Chicks: " << chicks << endl;
}
}
}
return 0;
}
Problem 2: Currency Exchange
Description:
Determine how many ways 100 yuan can be exchanged using 10-yuan, 5-yuan, and 1-yuan bills, ensuring at least one of each denomination.
Solution Approach:
Apply three nested loops to enumerate all valid combinations satisfying the total value constraint.
#include <iostream>
using namespace std;
int main() {
int count = 0;
for (int tens = 1; tens < 10; tens++) {
for (int fives = 1; fives < 20; fives++) {
for (int ones = 1; ones < 100; ones++) {
if (10 * tens + 5 * fives + ones == 100) {
cout << "Tens: " << tens << ", Fives: " << fives << ", Ones: " << ones << endl;
count++;
}
}
}
}
cout << "Total combinations: " << count << endl;
return 0;
}
Problem 3: House Numbering Digits
Description:
Count how many times digit '2' appears in house numbers from 1 to 2020.
Solution Approach:
Iterate through each number and extract individual digits to count occurrences of '2'.
#include <iostream>
using namespace std;
int main() {
int count = 0;
for (int i = 1; i <= 2020; i++) {
int num = i;
while (num != 0) {
if (num % 10 == 2) {
count++;
}
num /= 10;
}
}
cout << "Digit 2 appears " << count << " times." << endl;
return 0;
}
Problem 4: Multiplication Modulo
Description:
Find an integer x between 1 and 1000000007 such that (x * 2021) % 1000000007 equals 999999999.
Solution Approach:
Direct enumeration over the range to find matching value.
#include <iostream>
using namespace std;
int main() {
unsigned long long target = 999999999;
unsigned long long mod = 1000000007;
unsigned long long multiplier = 2021;
for (unsigned long long i = 1; i <= mod; i++) {
if ((i * multiplier) % mod == target) {
cout << i << endl;
break;
}
}
return 0;
}
Problem 5: Card Number Formation
Description:
Given 2021 cards of each digit 0-9, determine the highest positive integer that can be formed starting from 1.
Solution Approach:
Track available cards and attempt to form consecutive integers until insufficient cards remain.
#include <iostream>
using namespace std;
int main() {
int cards[10] = {2021, 2021, 2021, 2021, 2021, 2021, 2021, 2021, 2021, 2021};
int current = 1;
while (true) {
int temp = current;
bool valid = true;
while (temp > 0) {
int digit = temp % 10;
cards[digit]--;
if (cards[digit] < 0) {
valid = false;
break;
}
temp /= 10;
}
if (!valid) {
cout << current - 1 << endl;
break;
}
current++;
}
return 0;
}
Problem 6: Cargo Placement
Description:
For a given number n, count the number of ways to express it as a product of three factors L × W × H.
Solution Approach:
Find all divisors of n and use triple nested loops to count valid combinations.
#include <iostream>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
int main() {
ull n = 2021041820210418ULL;
ull divisors[3000];
ull count = 0;
// Find all divisors
for (ull i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
divisors[count++] = i;
if (i * i != n) {
divisors[count++] = n / i;
}
}
}
// Count valid triplets
ull result = 0;
for (ull i = 0; i < count; i++) {
for (ull j = 0; j < count; j++) {
for (ull k = 0; k < count; k++) {
if (divisors[i] * divisors[j] * divisors[k] == n) {
result++;
}
}
}
}
cout << result << endl;
return 0;
}
Problem 7: Shortest Path
Description:
Calculate the shortest path from node 1 to node 2021 in a graph where nodes are connected based on their difference.
Solution Approach:
Use dynamic programming with BFS-like approach to track minimum distances.
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int distance[2022] = {0};
for (int i = 1; i <= 2021; i++) {
for (int j = i + 1; j <= i + 21 && j <= 2021; j++) {
int lcm = (i * j) / gcd(i, j);
if (distance[j] == 0) {
distance[j] = distance[i] + lcm;
} else {
distance[j] = min(distance[j], distance[i] + lcm);
}
}
}
cout << distance[2021] << endl;
return 0;
}
Problem 8: Perfect Numbers
Description:
Identify all perfect numbers between 2 and 10000.
Solution Approach:
Check each number for its proper divisors sum equaling itself.
#include <iostream>
using namespace std;
bool isPerfect(int num) {
int sum = 0;
for (int i = 1; i < num; i++) {
if (num % i == 0) {
sum += i;
}
}
return sum == num;
}
int main() {
for (int i = 2; i <= 10000; i++) {
if (isPerfect(i)) {
cout << i << " is a perfect number" << endl;
}
}
return 0;
}
Problem 9: Sum of Products
Description:
Compute the sum of products of all pairs from a list of integers.
Solution Approach:
Use nested loops to compute pairwise products and accumulate the sum.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long sum = 0;
int arr[100];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
sum += (long long)arr[i] * arr[j];
}
}
cout << sum << endl;
return 0;
}