I have been trying this open.kattis.com problem but I don't know why the 13/14 test keeps giving me the wrong answer. I have already tried different solutions but keep giving me the same test case, I don't know if a declare some variables in the wrong way.
#include <iostream>
using namespace std;
int main(){
int arr[9];
int find = 0 , x, y;
bool found = false;
for(int i = 0; i < 9; i ){
cin >> arr[i];
find = arr[i];
}
find -= 100;
for(int first = 0; first < 8; first ){
for(int second = first; second < 9; second ){
if(arr[second] arr[first] == find){
x = first;
y = second;
found = true;
break;
}
}
if(found)
break;
}
for(int i = 0; i < 9; i )
if(i == x || i == y)
continue;
else
cout << arr[i] << endl;
}
CodePudding user response：
Consider the following test case:
8 3 1 5 30 15 12 22 10
Note that: 3 3 == 1 5
In the posted code, the nested loop checking the dwarves looks like this
for ( int first = 0; first < 8; first ) {
for( int second = first; second < 9; second ) {
// ^^^^^^^^^^^^^^
// ...
}
}
Meaning that it's considering the same dwarf twice, while it should be looking for two distinct ones:
for ( int first = 0; first < 8; first ) {
for( int second = first 1; second < 9; second ) {
// ^^^^^^^^^^^^^^^^^^ Just pick the next one
// ...
}
}
CodePudding user response：
First we need to analyze the task and then draft a solution.
The given problem is related to combinatorics. We should select k elements from n overall elements and check, if they fulfill a condition (sum == 100).
This is called "n choose k". Therory can be found here.
For getting such combinations there is a standard approach in C . We use a so called Selector. The Selector selects k elements from the overall input data. And then we calculate all permutations of the Selector and use it in a loop, to select source data and add it up (if selected).
Some picture will help to understand better.
Assume 4 choose 2
Base Data: 1,2,3,4
^ ^ ^ ^
| | | |
Selector: 0,0,1,1 --> 3,4
0,1,1,0 --> 2,3
0,1,0,1 --> 2,4
1,0,0,1 --> 1,4
1,0,1,0 --> 1,3
1,1,0,0 --> 1,2
So, we can build a selector array and then select elements accordingly.
For the example at hand, we can use precalculated values, since 9 choose 7 is 36, so a small number.
So. selectors converted int number would be:
1 001111111 -- > 127
2 010111111 -- > 191
3 011011111 -- > 223
4 011101111 -- > 239
5 011110111 -- > 247
6 011111011 -- > 251
7 011111101 -- > 253
8 011111110 -- > 254
9 100111111 -- > 319
10 101011111 -- > 351
11 101101111 -- > 367
12 101110111 -- > 375
13 101111011 -- > 379
14 101111101 -- > 381
15 101111110 -- > 382
16 110011111 -- > 415
17 110101111 -- > 431
18 110110111 -- > 439
19 110111011 -- > 443
20 110111101 -- > 445
21 110111110 -- > 446
22 111001111 -- > 463
23 111010111 -- > 471
24 111011011 -- > 475
25 111011101 -- > 477
26 111011110 -- > 478
27 111100111 -- > 487
28 111101011 -- > 491
29 111101101 -- > 493
30 111101110 -- > 494
31 111110011 -- > 499
32 111110101 -- > 501
33 111110110 -- > 502
34 111111001 -- > 505
35 111111010 -- > 506
36 111111100 -- > 508
We can then use bit masking operations, to check, if a bit is set and then select the corresponding data.
One of many many possible solutions would be:
#include <iostream>
int main() {
// Get user data
unsigned int data[9] = {7,8,10,13,15,19,20,23,25};
for (unsigned int k = 0; k < 9; k) std::cin >> data[k];
// Precomputed selectors
unsigned int selector[36] = { 127,191,223,239,247,251,253,254,319,351,367,375,379,381,382,415,431,439,443,445,446,463,471,475,477,478,487,491,493,494,499,501,502,505,506,508 };
// Go through all possible combinations of 9 choose 7
for (unsigned k = 0; k < 36; k) {
// For masking out bits in the selector
unsigned int mask = 1;
// Accumulating, if selected
unsigned int sum = 0;
// Check, if selected
for (unsigned int b = 0; b < 9; b) {
if (selector[k] & mask)
sum = data[b];
mask <<= 1;
}
// Ceck if sum fulfils requirement
if (sum == 100) {
mask = 1;
// Output selected result
for (unsigned int b = 0; b < 9; b) {
if (selector[k] & mask)
std::cout << data[b] << '\n';
}
}
}
}
And the idiomatic correct approach using C algorithms could look like the below:
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <iterator>
#include <numeric>
constexpr unsigned int TargetSum = 100u;
constexpr size_t NumberOverall = 9u;
constexpr size_t SelectedNumbers = 7u;
int main() {
// Get source data from std::cin
std::array<int, NumberOverall> data{ 7,8,10,13,15,19,20,23,25 };
//for (int& i : data) std::cin >> i;
// Define the selector with the same size as the input data vector
std::vector<bool> selector(NumberOverall);
// Set subSetSize elements in the selector element to true
std::fill(selector.begin(), std::next(selector.begin(), SelectedNumbers), true);
do {
// Calculate the sum of selectedelement
if (std::accumulate(data.begin(), data.end(), 0, [&, k = 0u](int sum, int i) mutable {if (selector[k ]) sum = i; return sum; }) == TargetSum) {
// Show result
std::copy_if(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, "\n"), [&, k = 0u] (const int i) mutable{return selector[k ];});
}
// Create the next permutation
} while (std::prev_permutation(selector.begin(), selector.end()));
}