Problem The Brand New Function

Link: http://codeforces.com/problemset/problem/243/A

A. The Brand New Function

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarpus has a sequence, consisting of n non-negative integers: a₁, a₂, ..., a_n.

Let's define function f(l, r) (l, r are integer, 1 ≤ l ≤ r ≤ n) for sequence a as an operation of bitwise OR of all the sequence elements with indexes from l to r. Formally: f(l, r) = a_l | a_l + 1 | ...  | a_r.

Polycarpus took a piece of paper and wrote out the values of function f(l, r) for all l, r (l, r are integer,1 ≤ l ≤ r ≤ n). Now he wants to know, how many distinct values he's got in the end.

Help Polycarpus, count the number of distinct values of function f(l, r) for the given sequence a.

Expression x | y means applying the operation of bitwise OR to numbers x and y. This operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "|", inPascal — as "or".

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of elements of sequence a. The second line contains n space-separated integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁶) — the elements of sequence a.

Output

Print a single integer — the number of distinct values of function f(l, r) for the given sequence a.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin,cout streams or the %I64d specifier.

Sample test(s)

input

3
1 2 0

output

4

input

10
1 2 3 4 5 6 1 2 9 10

output

11

Note

In the first test case Polycarpus will have 6 numbers written on the paper: f(1, 1) = 1, f(1, 2) = 3, f(1, 3) = 3, f(2, 2) = 2, f(2, 3) = 2, f(3, 3) = 0. There are exactly 4 distinct numbers among them: 0, 1, 2, 3.

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>


using namespace std;

#define oo 1000000005
#define N 100005
#define rep(i, start, end, step) for(int i = start; i < end; i += step)
#define down(i, start, end, step) for(int i = start; i > end; i -= step)
#define lop(i,s,e) for(int i = s; i != e; i++)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(x) ((int)(x).size())
#define X first
#define Y second

typedef pair<int,int> II;
typedef pair<II,int> D;
typedef long long LL;

vector<int> V;
map<int,int> M;
set<int> S;
queue<int> Q;
stack<int> ST;

int n;
int a[N];

int main()
{
    #define Off  false
    if(Off)
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }   
    cin >> n;
    rep(i, 0, n, 1) scanf("%d",&a[i]);
    
    rep(i, 0, n, 1)
    {
        S.insert(a[i]);
        int s = 0;
        down(j, i - 1, -1, 1)
        {
            //cout << "j=" << j << endl;
            s |= a[j];
            if((a[i] & ~s) == 0) break;
            S.insert(s|a[i]);
        }
    }
    cout << S.size();
    return 0;
}

Problem Undoubtedly Lucky Numbers

Link: http://codeforces.com/problemset/problem/244/B

B. Undoubtedly Lucky Numbers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits x and y. For example, if x = 4, and y = 7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer a undoubtedly lucky, if there are such digits x and y (0 ≤ x, y ≤ 9), that the decimal representation of number a (without leading zeroes) contains only digits x and y.

Polycarpus has integer n. He wants to know how many positive integers that do not exceed n, are undoubtedly lucky. Help him, count this number.

Input

The first line contains a single integer n (1 ≤ n ≤ 10⁹) — Polycarpus's number.

Output

Print a single integer that says, how many positive integers that do not exceed n are undoubtedly lucky.

Sample test(s)

input

10

output

10

input

123

output

113

Note

In the first test sample all numbers that do not exceed 10 are undoubtedly lucky.

In the second sample numbers 102, 103, 104, 105, 106, 107, 108, 109, 120, 123 are not undoubtedly lucky.

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>


using namespace std;

#define oo 1000000005
#define N 100005
#define rep(i, start, end, step) for(int i = start; i < end; i += step)
#define down(i, start, end, step) for(int i = start; i > end; i -= step)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(x) ((int)(x).size())
#define X first
#define Y second

typedef pair<int,int> II;
typedef pair<II,int> D;
typedef long long LL;

vector<int> V;
map<int,int> M;
set<LL> S;
queue<int> Q;
stack<int> ST;

int n;

void generate(int x, int y,LL val, int numdigit)
{
    if(val > n) return;
    if(numdigit > 10) return;
    S.insert(val);
    generate(x, y, val * 10 + x, numdigit + 1);
    generate(x, y, val * 10 + y, numdigit + 1);
}

int main()
{
    #define Off  false
    if(Off)
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }
    cin >> n;
    rep(i,0,10,1)
    rep(j,i+1,10,1)
        generate(i,j,0,0);
    
    cout << S.size() - 1;   // tru so 0
                    
    return 0;
}

Problem Dividing Orange

Link: http://codeforces.com/problemset/problem/244/A

A. Dividing Orange

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Ms Swan bought an orange in a shop. The orange consisted of n·k segments, numbered with integers from 1 to n·k.

There were k children waiting for Ms Swan at home. The children have recently learned about the orange and they decided to divide it between them. For that each child took a piece of paper and wrote the number of the segment that he would like to get: the i-th (1 ≤ i ≤ k) child wrote the number a_i (1 ≤ a_i ≤ n·k). All numbers a_i accidentally turned out to be different.

Now the children wonder, how to divide the orange so as to meet these conditions:

• each child gets exactly n orange segments;
• the i-th child gets the segment with number a_i for sure;
• no segment goes to two children simultaneously.

Help the children, divide the orange and fulfill the requirements, described above.

Input

The first line contains two integers n, k (1 ≤ n, k ≤ 30). The second line contains k space-separated integers a₁, a₂, ..., a_k (1 ≤ a_i ≤ n·k), where a_i is the number of the orange segment that the i-th child would like to get.

It is guaranteed that all numbers a_i are distinct.

Output

Print exactly n·k distinct integers. The first n integers represent the indexes of the segments the first child will get, the second n integers represent the indexes of the segments the second child will get, and so on. Separate the printed numbers with whitespaces.

You can print a child's segment indexes in any order. It is guaranteed that the answer always exists. If there are multiple correct answers, print any of them.

Sample test(s)

input

2 2
4 1

output

2 4 
1 3 

input

3 1
2

output

3 2 1 

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>


using namespace std;

#define oo 1000000005
#define N 100005
#define rep(i,s,e) for(int i = s; i < e; i++)
#define lop(i,s,e) for(int i = s; i != e; i++)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(x) ((int)(x).size())
#define X first
#define Y second

typedef pair<int,int> II;
typedef pair<II,int> D;
typedef long long LL;

vector<int> V;
map<int,int> M;
set<int> S;
queue<int> Q;
stack<int> ST;

int n,k,x;
int a[31];

int main()
{
    #define Off  false
    if(Off)
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }   
    cin >> n >> k;
    rep(i,0,k)
    {
        cin >> a[i];
        S.insert(a[i]);
    }
        
    rep(i,0,k)
    {
        cout << a[i] << " ";
        int count = 1;
            rep(j, 1, n * k +1)
            {
                if(S.find(j) == S.end())
                {
                    cout << j << " ";
                    S.insert(j);    
                    count++;
                }
                if(count == n)break;
            }
        cout << endl;
    }
    return 0;
}