A. Unit Array | Codeforces Solution | Codeforces Round 879 (Div. 2)
Given an array š of length š , which elements are equal to ā1 and 1 . Let's call the array š good if the following conditions are held at the same time: š1+š2+ā¦+ššā„0 ; š1ā š2ā ā¦ā šš=1 . In one operation, you can select an arbitrary element of the array šš and change its value to the opposite. In other words, if šš=ā1 , you can assign the value to šš:=1 , and if šš=1 , then assign the value to šš:=ā1 .
A. Unit Array
time limit per test: 1 second | memory limit per test: 256 megabytes
Given an array a of length n, which elements are equal to ā1 and 1. Let's call the array a good if the following conditions are held at the same time:
- a1 + a2 + ā¦ + an ā„ 0;
- a1 ā a2 ā ā¦ ā an = 1.
In one operation, you can select an arbitrary element of the array ai and change its value to the opposite. In other words, if ai = ā1, you can assign the value to ai := 1, and if ai = 1, then assign the value to ai := ā1.
Determine the minimum number of operations you need to perform to make the array a good. It can be shown that this is always possible.
Input
Each test consists of multiple test cases. The first line contains a single integer t (1 ā¤ t ā¤ 500) ā the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1 ā¤ n ā¤ 100) ā the length of the array a.
The second line of each test case contains n integers a1, a2, ā¦, an (ai = Ā±1) ā the elements of the array a.
Output
For each test case, output a single integer ā the minimum number of operations that need to be done to make the a array good.
Example
Input
7 4 -1 -1 1 -1 5 -1 -1 -1 1 1 4 -1 1 -1 1 3 -1 -1 -1 5 1 1 1 1 1 1 -1 2 -1 -1
Output
1 1 0 3 0 1 2
Note
In the first test case, we can assign the value a1 := 1. Then a1 + a2 + a3 + a4 = 1 + (ā1) + 1 + (ā1) = 0 ā„ 0 and a1 ā a2 ā a3 ā a4 = 1 ā (ā1) ā 1 ā (ā1) = 1. Thus, we performed 1 operation.
In the second test case, we can assign a1 := 1. Then a1 + a2 + a3 + a4 + a5 = 1 + (ā1) + (ā1) + 1 + 1 = 1 ā„ 0 and a1 ā a2 ā a3 ā a4 ā a5 = 1 ā (ā1) ā (ā1) ā 1 ā 1 = 1. Thus, we performed 1 operation.
In the third test case, a1 + a2 + a3 + a4 = (ā1) + 1 + (ā1) + 1 = 0 ā„ 0 and a1 ā a2 ā a3 ā a4 = (ā1) ā 1 ā (ā1) ā 1 = 1. Thus, all conditions are already satisfied and no operations are needed.
In the fourth test case, we can assign the values a1 := 1, a2 := 1, a3 := 1. Then a1 + a2 + a3 = 1 + 1 + 1 = 3 ā„ 0 and a1 ā a2 ā a3 = 1 ā 1 ā 1 = 1. Thus, we performed 3 operations.
void solve()
{
int n;
cin >> n;
int neg = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (x == -1)
neg++;
}
int pos = n - neg;
if (pos >= neg && neg % 2 == 0)
{
cout << 0 << endl;
}
else if (pos >= neg && neg % 2)
{
cout << 1 << endl;
}
else
{
int diff = neg - pos;
int change = diff % 2 + diff / 2;
neg -= change;
if (neg % 2 == 0)
{
cout << change << endl;
}
else
cout << change + 1 << endl;
}
// neg = 7 pos = 4 diff = -3
// neg = 6 pos = 5 diff = -1
// neg = 5 pos = 6 diff = 1
// neg = 8 pos = 4 diff = -4
// neg = 7 pos = 5 diff = -3
// neg = 6 pos = 6 diff = 0
//
}
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a) \
for (auto x : a) \
cout << x << " "; \
cout << endl
#define print1(a) \
for (auto x : a) \
cout << x.F << " " << x.S << endl
#define print2(a, x, y) \
for (int i = x; i < y; i++) \
cout << a[i] << " "; \
cout << endl
#define scanit(a, n) \
for (ll indexaa = 0; indexaa < n; indexaa++) \
cin >> a[indexaa];
inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1)
x *= a;
a *= a;
b >>= 1;
}
return x;
}
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
const char *comma = strchr(names + 1, ',');
cout.write(names, comma - names) << " : " << arg1 << " | ";
__f(comma + 1, args...);
}
const int N = 200005;
void solve()
{
int n;
cin >> n;
int neg = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (x == -1)
neg++;
}
int pos = n - neg;
if (pos >= neg && neg % 2 == 0)
{
cout << 0 << endl;
}
else if (pos >= neg && neg % 2)
{
cout << 1 << endl;
}
else
{
int diff = neg - pos;
int change = diff % 2 + diff / 2;
neg -= change;
if (neg % 2 == 0)
{
cout << change << endl;
}
else
cout << change + 1 << endl;
}
// neg = 7 pos = 4 diff = -3
// neg = 6 pos = 5 diff = -1
// neg = 5 pos = 6 diff = 1
// neg = 8 pos = 4 diff = -4
// neg = 7 pos = 5 diff = -3
// neg = 6 pos = 6 diff = 0
//
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
clock_t z = clock();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Raunit Verma
Technical Writer at CodingKaro
