e-olymp 4142. Большой XOR

03/12/2019 by Никита Репнин

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

$ a $ xor $x > x $
$ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

Входные данные

Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.

Выходные данные

Для каждого теста выведите в отдельной строке количество значений $a$, удовлетворяющих приведенным условиям.

Тесты

№	Входные данные	Выходные данные
1	2 2 10	1 5
2	3 13 3 16	2 0 15
3	5 1 7 4294967295 42 451	0 0 0 21 60

Код

#include <iostream>
using namespace std;
int main() {
    long q, x, res, two; 
    cin >> q;
    for(long i = 0; i < q; ++ i){
        cin >> x;
        res = 0;
        two = 1; // two = 2^0
        while(x > 0){
            if(x % 2 == 0) // проверяем равен ли бит нулю
                res += two;
            x >>= 1;  // двигаемся к следующему биту
            two <<= 1; // увеличиваем степень двойки
        }
        cout << res << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long q, x, res, two;

cin >> q;

for(long i = 0; i < q; ++ i){

cin >> x;

res = 0;

two = 1; // two = 2^0

while(x > 0){

if(x % 2 == 0) // проверяем равен ли бит нулю

res += two;

x >>= 1; // двигаемся к следующему биту

two <<= 1; // увеличиваем степень двойки

}

cout << res << endl;

}

return 0;

}

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

Задача на e-olymp

Код программы на ideone

Засчитанное решение

Related Images:

e-olymp 8891. Ровно одно условие из двух

01/12/2019 by Владислав Стасюк

Задача

Для заданного целого числа $n$ вывести YES, если выполняется ровно одно из следующих условий и NO в противном случае.

число $n$ четное.
число $n$ отрицательное и кратное трем.

Входные данные

Одно целое число $n$.

Выходные данные

Вывести YES или NO в зависимости от выполнения условий.

Тесты

ВВОД	ВЫВОД
22	YES
7	NO
-30	NO
-9	YES
0	YES

Код (как делать можно, но не нужно)

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    if((n % 2 == 0 and (n >= 0 or n % 3 != 0)) or (n % 3 == 0 and n < 0 and n % 2 != 0)){
        cout << "YES";
    }
    else{
        cout << "NO";
    } 
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

if((n % 2 == 0 and (n >= 0 or n % 3 != 0)) or (n % 3 == 0 and n < 0 and n % 2 != 0)){

cout << "YES";

}

else{

cout << "NO";

}

return 0;

}

Код (как делать можно и нужно)

#include <iostream>
using namespace std;
int main() {
    int n; 
    cin >> n;
    cout << ((n%2 == 0) == (n%3 == 0 and n<0)? "NO": "YES");
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << ((n%2 == 0) == (n%3 == 0 and n<0)? "NO": "YES");

}

Решение

Если оба условия выполняются или оба не выполняются, то нужно вывести «NO», а иначе — «YES».

В первом случае проверяем четность числа $n$.
Во втором случае проверяем кратность трем и является ли $n$ отрицательным.
В обеих случаях исключаем варианты, когда оба условия могли бы выполнятся, то есть исключаем отрицательные числа и кратность трем для первого, и четность числа для второго случая.

Ссылки
e-olymp
ideone

Related Images:

e-olymp 8374. Нечетное количество раз

09/12/2018 by Инна Литвиненко

Задача

Найдите число, которое встречается в последовательности нечетное количество раз.

Входные данные

Первая строка содержит натуральное число $n (n < 500000)$. Далее следуют $n$ натуральных чисел, каждое из которых меньше $10^6$.

Выходные данные

Во входной последовательности только одно число $x$ повторяется нечетное количество раз. Другие числа повторяются четное число раз. Выведите $x$.

Замечание

В условии задачи на e-olymp опечатка, но, проанализировав входные и выходные данные примеров, несложно понять суть задачи.

Тесты

№	Ввод	Вывод
1	9 3 1 2 2 17 1 3 17 3	3
2	5 12 13 14 13 12	14
3	3 20 0 20	0
4	15 5 7 1 2 3 5 7 2 7 5 1 2 3 5 2	7
5	11 10 100 1000 100 100 100 1000 10 100 1000 100	1000

Код 1

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    long long n, *x;
    cin >> n;
    x = new long long[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    sort(x, x + n);
    long long k, y;
    k = 1;
    y = x[0];
    for (int i = 1; i < n; i++) {
        if (x[i] == y)
            k++;
        else {
            if (k % 2 != 0) {
                cout << y;
                return 0;
            }
            else {
                k = 1;
                y = x[i];
            }
        }
    }
    cout << x[n - 1];
    delete []x;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long n, *x;

cin >> n;

x = new long long[n];

for (int i = 0; i < n; i++)

cin >> x[i];

sort(x, x + n);

long long k, y;

k = 1;

y = x[0];

for (int i = 1; i < n; i++) {

if (x[i] == y)

k++;

else {

if (k % 2 != 0) {

cout << y;

return 0;

}

else {

k = 1;

y = x[i];

}

cout << x[n - 1];

delete []x;

return 0;

}

Код 2

#include <iostream>
using namespace std;
 
int main() {
    long long n, *x;
    cin >> n;
    x = new long long[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    long res = 0;
    for (int i = 0; i < n; i++)
		res ^= x[i];
    cout << res;
    delete []x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, *x;

cin >> n;

x = new long long[n];

for (int i = 0; i < n; i++)

cin >> x[i];

long res = 0;

for (int i = 0; i < n; i++)

res ^= x[i];

cout << res;

delete []x;

return 0;

}

Код 3 (без массива)

#include <iostream>
using namespace std;

int main() {
	long long n, res = 0, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		res ^= x;
	}
	cout << res;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, res = 0, x;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> x;

res ^= x;

}

cout << res;

return 0;

}

Решение

Для начала создадим динамический одномерный массив и считаем с потока ввода все его элементы. Конечно, можно было создать статический массив на 500000 элементов, но, скорее всего, памяти выделилось бы намного больше, чем было бы использовано.

Первый способ

Отсортируем наш массив по возрастанию. Как будем сортировать особо значения не имеет, главное, чтоб одинаковые элементы стояли подряд.

Затем, заведём две переменные: счётчик и число. Последней присваиваем значение первого элемента массива. Сравниваем следующий элемент с тем, что лежит в переменной. Если они равны, увеличиваем счетчик. В счетчик с самого начала положим единицу, так как предполагаем, что в массиве есть хоть один элемент.

Как только проверяемый нами элемент массива не будет равен значению переменной, проверяем счетчик на четность. Если нечетный, выводим значение переменной и завершаем работу программы. Если четный, присваиваем переменной новое значение, а счетчику снова единицу. Так будем подсчитывать пока не найдём число, повторяющееся нечетное количество раз. Если не найдем, это значит, что искомое число последнее, так как оно обязательно есть по условию, а наша программа сработает для всех элементов, кроме последнего (последний элемент мы не можем сравнить со следующим, а значит не можем проверить счетчик).

Второй способ

Применим исключающее «или» ко всем элементам массива. Предварительно создадим переменную равную нулю, в которой будем это проделывать.

Так как xor двух одинаковых чисел равен нулю, то для любого количества пар одинаковых чисел он будет равен нулю. А вот xor нуля и любого числа равен самому числу.

Таким образом, исключив все пары одинаковых чисел, наша переменная примет значение повторяющегося нечетное количество раз числа.

Третий способ

Идейно такой же как предыдущий. Отличается только тем, что мы не записываем числа в массив, а исключающее «или» работает сразу после того как число было прочитано.

Ссылки

Задача 8374 на e-olymp

Код 1 на Ideone

Код 2 на Ideone

Код 3 на Ideone

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: xor

e-olymp 4142. Большой XOR

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Related Images:

e-olymp 8891. Ровно одно условие из двух

Задача

Входные данные

Выходные данные

Тесты

Код (как делать можно, но не нужно)

Код (как делать можно и нужно)

Решение

Related Images:

e-olymp 8374. Нечетное количество раз

Задача

Входные данные

Выходные данные

Замечание

Тесты

Код 1

Код 2

Код 3 (без массива)

Решение

Первый способ

Второй способ

Третий способ

Ссылки

Related Images: