Westlake
BAN USER#include <iostream>
#include <vector>
using namespace std;
int findMax(vector<int>& A)
{
int lb = 0;
int rb = A.size() - 1;
while (lb < rb) {
int m = (rb - lb) / 2 + lb;
if (A[m] < A[m + 1])
lb = m + 1;
else
rb = m;
}
return lb;
}
int main()
{
vector<int> A = {1,2,3,4,5,9, 11, 88, 4, 3,1};
cout << "max = " << A[findMax(A)] << endl;
return 0;
}
LOL :) You really made this board fully of joy! I like your answer very much. Anyway I will give my way to approve the result.
The possiblity to have only 1 child is 0.5 (1 boy, and 0 girl);
The possiblity to have only 2 children is 0.5^2 (1 boy, and 1 girl);
...
The possiblity to have only i children is 0.5^i (1 boy, and i-1 girl);
So the number of boys expected is P = 0.5 + 0.5^2 + .. + 0.5^i + ...
So the number of girls expected is Q = 0.5^2 + .. + (i-1)*0.5^i + ...
It's easy to find out that
Q*2 - Q = P
P*2 - P = 1
So P = Q = 1
This implies that each pair of parents will have just 2 children in
average, one boy and one girl.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int K = 1000;
const int N = 100000;
int main () {
vector<int> v;
for (int i = 0; i < K; i++) {
int d = rand();
v.push_back(d);
}
// create a min-heap with K elements
make_heap (v.begin(),v.end(), greater<int>());
for (int i = 0; i < N; i++) {
int d = rand();
// if the new number is greater than the min value of the heap
// remove the min value from the heap, and add the new value in
// the heap
if (d > v.front()) {
pop_heap (v.begin(),v.end(), greater<int>());
v.pop_back();
v.push_back(d);
push_heap (v.begin(),v.end(), greater<int>());
}
}
sort_heap (v.begin(),v.end(), greater<int>());
for (int i : v) cout << i << " ";
cout << endl;
return 0;
}
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
/* find the largest rectangle in a histogram */
int largestRectangleInHistogram(const vector<int>& H)
{
stack<int> S;
int maxArea = 0;
for (int i = 0; i < H.size(); i++) {
while (!S.empty() && H[S.top()] >= H[i])
S.pop();
int span = S.empty() ? (i + 1) : (i - S.top());
maxArea = max(maxArea, span * H[i]);
S.push(i);
}
return maxArea;
}
int largestRectangleInMatrix(const vector<vector<int>>& M)
{
int rows = M.size();
int columns = M[0].size();
vector<int> H(columns);
for (int j = 0; j < columns; j++)
H[j] = M[0][j];
int maxArea = largestRectangleInHistogram(H);
for (int i = 1; i < rows; i++) {
for (int j = 0; j < columns; j++)
H[j] = M[i][j] ? H[j] + 1 : 0;
maxArea = max(maxArea, largestRectangleInHistogram(H));
}
return maxArea;
}
int main()
{
vector<vector<int>> M = {
{1,0,0,0,1,0,0},
{0,0,0,0,1,0,0},
{0,0,1,1,1,1,1},
{0,0,1,1,1,1,0},
{0,0,1,1,1,1,0}
};
cout << "max area = " << largestRectangleInMatrix(M) << endl;
}
/* output: max area = 12 */
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N = 9;
for (int i = 0; i < 2 * N - 1; i++) {
int k = i < N ? i : 2 * (N - 1) - i;
for (int j = 0; j < k; j++)
cout << N - j;
for (int j = 0; j < 2 * (N - k) - 1; j++)
cout << N - k;
for (int j = k - 1; j >= 0; j--)
cout << N - j;
cout << endl;
}
return 0;
}
/**** output for N = 9
99999999999999999
98888888888888889
98777777777777789
98766666666666789
98765555555556789
98765444444456789
98765433333456789
98765432223456789
98765432123456789
98765432223456789
98765433333456789
98765444444456789
98765555555556789
98766666666666789
98777777777777789
98888888888888889
99999999999999999
***/
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
/* find the next enumeration */
bool hasNext(vector<int>& limits, vector<int>& perm)
{
const int N = limits.size();
for (int i = 0; i < N; i++) {
perm[i]++;
if (perm[i] < limits[i])
return true;
for (int j = 0; j <= i; j++)
perm[j] = 0;
}
return false;
}
int main()
{
vector<vector<string>> map = { // things to enumerate
{ "Checks", "Lines" },
{ "XL", "X", "M", "S" },
{ "Red", "Blue", "Green"}};
const int N = map.size();
vector<int> perm(N, 0);
vector<int> limits(N);
for(int i = 0; i < N; i++)
limits[i] = map[i].size();
do {
for (int i = N - 1; i >= 0; i--)
cout << map[i][perm[i]] << "\t";
cout << endl;
} while (hasNext(limits, perm));
return 0;
}
/* output:
Red XL Checks
Red XL Lines
Red X Checks
Red X Lines
Red M Checks
Red M Lines
Red S Checks
Red S Lines
Blue XL Checks
Blue XL Lines
Blue X Checks
Blue X Lines
Blue M Checks
Blue M Lines
Blue S Checks
Blue S Lines
Green XL Checks
Green XL Lines
Green X Checks
Green X Lines
Green M Checks
Green M Lines
Green S Checks
Green S Lines
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<double> A = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0};
vector<double> M(A.size());
const int N = A.size();
double m = 1.0;
for (int i = 0; i < N; i++) {
M[i] = m; // m = A[0] * A[1] * .... * A[i - 1]
m *= A[i]; // update m
}
m = 1;
for (int i = N - 1; i >=0; i--) {
M[i] *= m; // m = A[i+1] * ... * A[N-1]
m *= A[i]; // update m
}
for (double d : M) cout << d << " "; cout << endl;
return 0;
}
If it's the next largest, how come the first element becomes 12. When we consider A[0], the largest element from A[0] is 12, and the second largest is 10. If you want the second largest, A[0] should become 10.
The code can be easily adapted to handle the second largest case.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int A[] = {2,12,8,6,5,1,2,10,3,2};
const int N = sizeof(A) / sizeof(A[0]);
int m = A[N - 1];
for (int i = N - 2; i >= 0; i--) {
m = max(m, A[i]); // m = max(A[i], A[i+1], .... A[N-1]
A[i] = m;
}
for_each(A, A + N, [](int n) { cout << n << " "; });
cout << endl;
}
// output: 12 12 10 10 10 10 10 10 3 2
Very nice idea. I just wanted to point out one bug (one modulo operator is missing). Here's the correction I made:
// set A'[i] = A[i] + N * A[A[i]]
for(int i = 0; i < N; i++)
A[i] += (A[A[i] % N] % N) * N;
for(int i = 0; i < N; i++)
A[i] /= N;
One problem of this approach is that when size of the array is big (N >= 2^31) there will be overflow.
My approach in another solves this problem.
int main()
{
int A[] = {2, 3, 1, 0, 5, 6, 4};
const int N = sizeof (A) / sizeof (A[0]);
for (int i = 0; i < N; i++) {
if (A[i] < 0) // already processed
continue;
if (A[i] == i) {
A[i] = -A[i] - 1; // reverse it to mark it processed
continue;
}
int t = A[i];
int j = i;
do {
int k = A[j];
A[j] = - A[k] - 1; // use negative value to to mark it processed
j = k;
} while (i != A[j]);
A[j] = -t - 1;
}
for(int i = 0; i< N; i++) {
A[i] = -A[i] - 1; // restore the value
cout << A[i] << " ";
}
cout << endl;
}
A little change to make it more efficient:
for (int k = 0; k < N; k++) {
int i = 0;
int j = k;
while (j >= 0)
cout << A[i++][j--] << " ";
cout << endl;
}
for (int k = 1; k < N; k++) {
int i = k;
int j = N - 1;
while (i < N)
cout << A[i++][j--] << " ";
cout << endl;
}
}
#include <iostream>
using namespace std;
const int N = 4;
int main()
{
int A[N][N];
int n = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
A[i][j] = n++;
cout << A[i][j] << " ";
}
cout << endl;
}
for (int k = 0; k < 2 * N; k++) {
int i = k < N ? 0 : k - N + 1;
int j = k < N ? k : N - 1;
while (i < N && j >= 0)
cout << A[i++][j--] << " ";
cout << endl;
}
return 0;
}
If there are no duplicates, then we can create array of buckets. The array size is 1M, and each element is a 12-bit integer count. Then scan the numbers, for each number N, increase the count in the (N>>12)'th bucket. At the end if the count in the bucket is less than 2^12-1, then the missing number is in this bucket. The rest is easy - scan the numbers again, discard the numbers not in the bucket, for the number is this bucket, use bitmap to indicate if the number is visited.
- Westlake February 25, 2014Here's the tested code:
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>
using namespace std;
struct Node {
long data;
Node* left;
Node* right;
Node(long d) : data(d), left(0), right(0) {}
};
void serialize (Node* root, stringstream& os)
{
if (!root) {
os << "$ ";
return;
}
os << root->data << " ";
serialize(root->left, os);
serialize(root->right, os);
}
Node* deserialize (stringstream& os)
{
string tok;
os >> tok;
if (tok == "$")
return 0;
Node* root = new Node(stoi(tok));
root->left = deserialize(os);
root->right = deserialize(os);
return root;
}
int main()
{
Node* root = new Node(4);
root->left = new Node(2);
root->left->right = new Node(3);
root->left->right->left = new Node(1);
root->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
stringstream os;
serialize(root, os);
cout << os.str() << endl;
Node* dup = deserialize(os);
stringstream os2;
serialize(dup, os2);
cout << os2.str() << endl;
return 0;
}
Look at this:
double power(double x, int y)
{
if (y == 0)
return 1.0;
if (y == 1)
return x;
if (y < 0)
return 1.0 / power(x, -y);
if (y & 0x1 == 0) {
double t = power(x, y/2);
return t * t;
}
return x * power(x, y - 1);
}
double power_iterative(double x, int y)
{
double result = 1.0;
if (y == 0)
return result;
bool neg = false;
if (y < 0) {
neg = true;
y = -y;
}
while (y) {
if (y & 0x1)
result *= x;
x *= x;
y >>= 1;
}
return neg ? 1.0 / result : result;
}
I really like your idea. Here's the C++ implementation:
int tower(int n)
{
if (n <= 0)
return 0;
switch (n) {
case 1: return 1;
case 2: return 2;
case 3: return 4;
case 4: return 8;
default: break;
}
n -= 4;
queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(4);
Q.push(8);
int f = 1 + 2 + 4 + 8;
while (--n) {
Q.push(f);
f = 2 * f - Q.front();
Q.pop();
}
return f;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
using namespace std;
int main ()
{
vector<int> A = { 1,5, 3, 4, 2, 9, 7 };
int K = 2;
sort(A.begin(), A.end());
int count = 0;
auto i = A.begin();
auto j = next(i, 1);
while(j != A.end()) {
int n = *i + K;
auto r = equal_range (j, A.end(), n);
j = r.first;
while (r.first != r.second) {
cout << "(" << *i << ", " << *r.first << ")" << endl;
count++;
r.first++;
}
++i;
}
cout << "total pairs = " << count << endl;
return 0;
}
/***********************************************************
output:
(1, 3)
(2, 4)
(3, 5)
(5, 7)
(7, 9)
total pairs = 5
***********************************************************/
bool perm_next (int *a, int n)
{
int k = n - 2;
if (k < 0) return false;
// Find the largest index k such that a[k] < a[k + 1]. If no such index
// exists, the permutation is the last permutation.
//
while (a[k] >= a[k+1]) {
k--;
if (k < 0)
return false;
}
// Find the largest index l such that a[k] < a[l]. Since k + 1 is such an
// index, l is well defined and satisfies k < l.
int l = n - 1;
while (a[k] >= a[l])
l--;
// Swap a[k] with a[l]
std::swap(a[k], a[l]);
// Reverse the sequence from a[k + 1] up to and including the final
// element a[n]
std::reverse(&a[k+1], &a[n]);
return true;
}
int main()
{
int a[N];
for (int i = 0; i < N; i++)
a[i] = i + 1;
do {
print(a, N);
} while (perm_next(a, N));
return 0;
}
We may try the following idea:
create an array of pairs (S_i, i) where
S_i = A[1] + a[2] + ... + A[i],
Sort the array of pairs so that the first element increase. In the sorted array find
(S_i, i) and (S_j, j) so that S_i = S_j -1 and j < j
Average cost should be the same as the sorting and searching algorithms.
- Westlake February 19, 2014First sort the numbers. If there are 2 numbers then the minimal move is A[1] - A[0] by settling down the final number to any value between A[1] and A[0]. If there are 3 numbers, then the minimal move is A[3] - A[1]. by settling down the final number to A[2]. For N numbers the minimal moves is
(A[N-1]-A[0]) + (A[N-2]-A[1]) ...
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void fillWithY(vector<string>& A, int i, int j)
{
if (i < 0 || i >= A.size() || j < 0 || j >= A[i].size() || A[i][j] != 'O')
return;
A[i][j] = 'Y';
fillWithY(A, i - 1, j); // absorb more 'O' on the top
fillWithY(A, i + 1, j); // absorb more 'O' on the bottom
fillWithY(A, i, j - 1); // absorb more 'O' on the left
fillWithY(A, i, j + 1); // absorb more 'O' on the right
}
int main()
{
vector<string> A;
A.push_back("XXXXX");
A.push_back("XXOOX");
A.push_back("XXOOX");
A.push_back("OXXXX");
// first try to aborb '0's at the boundary and replace them with 'Y'
for (int j = 0; j < A[0].size(); j++)
fillWithY(A, 0, j);
for (int j = 0; j < A.back().size(); j++)
fillWithY(A, A.size() - 1, j);
for (int i = 0; i < A.size(); i++) {
fillWithY(A, i, 0);
fillWithY(A, i, A[i].size() - 1);
}
// rewrite internal 'O's with 'X', and restore 'Y's
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < A[i].size(); j++)
if (A[i][j] == 'Y')
A[i][j] = 'O';
else if (A[i][j] == 'O')
A[i][j] = 'X';
}
// shown me the result
for (int i = 0; i < A.size(); i++)
cout << A[i] << endl;
}
Let's try this efficient version:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int factor(int& n, int p)
{
int ret = 0;
while (n && n % p == 0) {
ret++;
n /= p;
}
return ret;
}
bool magic_number(int n)
{
// first decompose 'n' into 2^p2 3^p3 5^p5 7^p5
int p2 = factor (n, 2);
int p3 = factor (n, 3);
int p5 = factor (n, 5);
int p7 = factor (n, 7);
// if there are factors other than 2, 3, 5, 7, there's no solution
if (n != 1)
return false;
vector<int> v;
for (int i = 0; i < p7; i++) // one factor of 7 needs one digit
v.push_back(7);
for (int i = 0; i < p5; i++) // one factor of 5 needs one digit
v.push_back(5);
for (int i = 0; i < p3 / 2; i++) // 2 factors of 3 can form one digit 9
v.push_back(9);
if (p3 % 2 && p2) { // factor 2 and 3 can form one digit 6
v.push_back(6);
p2--;
}
for (int i = 0; i < p2 / 3; i++) // 3 factors of 2 can form one digit 8
v.push_back(8);
p2 %= 3;
for (int i = 0; i < p2 / 2; i++) // 2 factors of 2 can form one digit 4
v.push_back(4);
if (p2 % 2) // 1 factor of 2 can for one digit 2
v.push_back(2);
if (v.size() > 3) // too many digits
return false;
int d = 3 - v.size(); // fill digit 1 if there are still spaces
for (int i = 0; i < d; i++)
v.push_back(1);
sort(v.begin(), v.end());
for(int i : v)
cout << i << " ";
cout << endl;
return true;
}
int main()
{
int n = 100;
magic_number(n);
return 0;
}
Minor change to return only one matching subset:
void findSubsetHelper(int* A, int N, bool *chosen, int K, int start,
bool& found)
{
int d = K - A[start];
if (d < 0)
return;
if (d == 0) {
found = true;
chosen[start] = true;
for (int i = 0; i < N; i++)
if (chosen[i])
cout << A[i] << " ";
cout << endl;
chosen[start] = false;
return;
}
// case 1: A[start] is not chosen
findSubsetHelper(A, N, chosen, K, start + 1, found);
if (found)
return;
// case 2: A[start] is chosen
chosen[start] = true;
findSubsetHelper(A, N, chosen, d, start + 1, found);
chosen[start] = false;
}
void findSubset(int* A, int N, int K)
{
bool *chosen = new bool [N];
bool found = false;
for (int i = 0; i < N; i++) chosen[i] = false;
sort (A, A + N);
findSubsetHelper(A, N, chosen, K, 0, found);
delete [] chosen;
if (!found)
cout << "not found" << endl;
}
A brutal method:
#include <algorithm>
#include <iostream>
using namespace std;
void findSubsetHelper(int* A, int N, bool *chosen, int K, int start)
{
int d = K - A[start];
if (d < 0)
return;
if (d == 0) {
chosen[start] = true;
for (int i = 0; i < N; i++)
if (chosen[i])
cout << A[i] << " ";
cout << endl;
chosen[start] = false;
return;
}
// case 1: A[start] is not chosen
findSubsetHelper(A, N, chosen, K, start + 1);
// case 1: A[start] is chosen
chosen[start] = true;
findSubsetHelper(A, N, chosen, d, start + 1);
chosen[start] = false;
}
void findSubset(int* A, int N, int K)
{
bool *chosen = new bool [N];
for (int i = 0; i < N; i++) chosen[i] = false;
sort (A, A + N);
findSubsetHelper(A, N, chosen, K, 0);
delete [] chosen;
}
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
int main()
{
int A[] = {1, 2, 100, 22 , 28};
int B[] = {1, 2, 3, 5, 7, 10};
findSubset(A, ARRAY_SIZE(A), 150);
findSubset(B, ARRAY_SIZE(B), 15);
}
Not very optimized, but it worked:
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
const int N = 10;
int A[N];
vector<int> smaller, bigger;
for (int i = 0; i < N; i++)
A[i] = rand() % 20;
int median = A[0];
for (int i = 1; i < N; i++) {
if(median < A[i]) {
bigger.push_back(A[i]);
push_heap(bigger.begin(), bigger.end(), greater<int>());
}
else {
smaller.push_back(A[i]);
push_heap(smaller.begin(), smaller.end(), less<int>());
}
int d = smaller.size() - bigger.size();
if (d > 0) {
bigger.push_back(median);
push_heap(bigger.begin(), bigger.end(), greater<int>());
median = smaller[0];
pop_heap(smaller.begin(), smaller.end(), less<int>());
smaller.pop_back();
}
else if (d < -1) {
smaller.push_back(median);
push_heap(smaller.begin(), smaller.end(), less<int>());
median = bigger[0];
pop_heap(bigger.begin(), bigger.end(), greater<int>());
bigger.pop_back();
}
cout << "median = " << median << " in ";
vector<int> t(A, A + i + 1);
sort(t.begin(), t.end());
for (int x : t) cout << x << " "; cout << endl;
}
}
Working on linux:
#include <pthread.h>
#include <stdio.h>
pthread_mutex_t lock;
pthread_cond_t cv;
int turn = 0;
void *print_num(void *arg)
{
int my_turn = arg ? 1 : 0;
for (int i = my_turn; i < 100; i += 2) {
pthread_mutex_lock(&lock);
while (my_turn != turn)
pthread_cond_wait (&cv, &lock);
turn = (turn + 1) % 2;
printf ("%d ", i);
pthread_cond_signal (&cv);
pthread_mutex_unlock(&lock);
}
printf ("\n");
pthread_exit(0);
}
int main (int argc, char *argv[])
{
pthread_mutex_init(&lock, NULL);
pthread_cond_init (&cv, NULL);
pthread_t odd, even;
pthread_create(&even, NULL, print_num, (void *)0);
pthread_create(&odd, NULL, print_num, (void *)1);
pthread_join(even, NULL);
pthread_join(odd, NULL);
pthread_mutex_destroy(&lock);
pthread_cond_destroy(&cv);
return 0;
}
For C++ fans:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isOne (int i) { return i==1; }
int main(int argc, char**argv)
{
vector<int> a = {1, 2, 9, 3, 4, 5, 6};
int k = 7;
sort(a.begin(), a.end());
int i = 0;
int j = a.size() - 1;
while (i < j) {
int d = k - a[j] - a[i];
if (d == 0) {
cout << a[i] << " - " << a[j] << endl;
i++;
j--;
}
else if (d < 0)
j--;
else
i++;
}
}
For C++ fans:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isOne (int i) { return i==1; }
int main(int argc, char**argv)
{
vector<int> a = {1,2,1,2,1,2,1,2};
partition(a.begin(), a.end(), isOne);
for (int i: a)
cout << i << endl;
}
Here's the c++ version:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool timeLess(int a, int b)
{
int d = abs(a) - abs(b);
if (d == 0)
return a < b;
return d < 0;
}
struct Meeting {
int start;
int end;
};
int main(int argc, char**argv)
{
Meeting allMeetings[] = {
{1, 3},
{2, 4},
{6, 7},
{4, 6},
{5, 6}
};
int N = sizeof(allMeetings) / sizeof(allMeetings[0]);
vector<int> times;
for (int i = 0; i < N; i++) {
times.push_back(allMeetings[i].start);
times.push_back(-allMeetings[i].end);
}
sort(times.begin(), times.end(), timeLess);
int rooms = 0;
int maxRooms = 0;
for (int i : times) {
if (i > 0) {
// hit the meeting start time
rooms++;
if (rooms > maxRooms)
maxRooms = rooms;
}
else {
// hit the meeting end time
rooms--;
}
}
cout << "max number of rooms needed is " << maxRooms << endl;
}
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
Interval (int a, int b) : start(a), end(b) {}
int start, end;
bool combine(const Interval& r) {
if (start > r.end || end < r.start)
return false; // no intersection
start = min(start, r.start);
end = max(end, r.end);
return true;
}
};
ostream& operator << (ostream& os, const Interval& i)
{
os << "(" << i.start << ", " << i.end << ")" << endl;
}
bool intervalLess (const Interval& i1, const Interval& i2)
{
int x = i1.start - i2.start;
return (x < 0) ? true : ((x == 0) ? (i1.end - i2.end < 0) : false);
}
int main()
{
vector<Interval> v;
v.push_back(Interval(7, 8));
v.push_back(Interval(8, 11));
v.push_back(Interval(6, 10));
v.push_back(Interval(2, 5));
v.push_back(Interval(1, 3));
sort(v.begin(), v.end(), intervalLess);
for (Interval& i : v) cout << i;
cout << "---------------------" << endl;
Interval curInterval = v[0];
for (int i = 1; i < v.size(); i++) {
if (curInterval.combine(v[i])) {
// v[i] is combined into the current interval
continue;
}
cout << curInterval;
curInterval = v[i];
}
cout << curInterval;
return 0;
}
int main(int argc, char** argv)
{
int d;
int zeros = 0;
int ones = 0;
while (cin >> d) {
if (d == 0)
zeros++;
else if (d == 1)
ones++;
else {
cout << "bad number";
return -1;
}
}
int fprev = 1;
int f = 2;
for (int i = 0; zeros && i < fprev; i++, zeros--) {
cout << "0 ";
}
int flag = 1;
while (zeros || ones) {
if (flag == 1) {
flag = 0;
for (int i = 0; ones && i < f; i++, ones--)
cout << "1 ";
}
else {
flag = 1;
for (int i = 0; zeros && i < f; i++, zeros--)
cout << "0 ";
}
int t = f * f - fprev * fprev;
fprev = f;
f = t;
}
}
struct Node {
Node(char d) : data(d), next(0) {}
char data;
Node* next;
};
inline void ADD(Node*& t, Node* n)
{
n->next = 0; t->next = n; t = n;
}
int main(int argc, char** argv)
{
Node* head = new Node('a');
Node* tail = head;
ADD(tail, new Node('x'));
ADD(tail, new Node('b'));
ADD(tail, new Node('y'));
ADD(tail, new Node('c'));
ADD(tail, new Node('z'));
for (Node* p = head; p->next != tail; p = p->next) {
Node* t = p->next;
p->next = t->next;
t->next = tail->next;
tail->next = t;
}
for (Node* n = head; n; n = n->next) cout << n->data; cout << endl;
cout << endl;
}
int main(int argc, char** argv)
{
int a[] = {1, 2, 1, 3, 2, 4, 4, 5, 4};
int N = sizeof(a) / sizeof(*a);
map<int, int> count;
for (int i = 0; i < N; i++) {
if (count.find(a[i])!= count.end())
count[a[i]]++;
else
count[a[i]] = 1;
}
for (map<int,int>::iterator iter = count.begin(); iter != count.end(); iter++) {
if (iter->second % 2)
cout << iter->first << " ";
}
}
int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
int N = sizeof(a) / sizeof(*a);
sort(a, a + N);
int K = 12;
for (int i = 0; i < N - 3; i++) {
for (int j = i + 1; j < N - 2; j++) {
int diff = K - a[i] - a[j];
int *t = lower_bound(a + j, a + N, diff);
if (t != a + N && *t == diff) {
cout << "(" << a[i] << ", " << a[j] << ", " << *t << ")" << endl;
}
}
int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
int N = sizeof(a) / sizeof(*a);
sort(a, a + N);
int K = 12;
int i = 0;
int *t = std::upper_bound(a, a + N, K - a[0]);
int j = t - a - 1;
while (i < j) {
for (int k = i + 1; k <= j; k++)
cout << "(" << a[i] << ", " <<a[k] << ") ";
i++;
while (a[i] + a[j] > K && i < j) {
j--;
}
}
Repjuanitasfalbo45, Android Engineer at 247quickbookshelp
Hey, Juanita Falbo, and I am working as a Yoga instructor. And nowadays I am doing a new experiment on ...
RepKimDavilla, Questions - Problem Solving Round at Cavium Networks
Kim , an associate veterinarian with 4+ years of experience. Specialist in companion animal emergency and also expert at Sudoku , playing ...
- Westlake March 16, 2014