You are given three integers $$$A$$$,$$$B$$$, and $$$C$$$, and your task is to apply bitwise XOR a number x on the $$$A$$$,$$$B$$$ and $$$C$$$ such that they transform into non-decreasing order? Also A, B, C, x lie in the range from 1 to 1e9.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
35:09:27
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
35:09:27
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 06:25:34 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by fighterphoenix (previous revision, new revision, compare).
A^B will denote A XOR B operation. Consider the most significant bit in (B^C). If B > C, this bit must be set in x. If B < C, this bit must be unset in x. Do the same for A and B. If some bit in x must be set and unset at the same time, answer is -1, otherwise we can choose OR of bits that must be set.
There is a follow up for the question also, that if there exists multiple solutions find the minimum value of x.
Understood your logic and will be implementing it, Thanks for the help friend!
In my approach, only those bits that must be set, are present in x, therefore x is minimal.
Thanks bro , your logic worked and that is a very good approach!
Given A, B, C .. and you have to determine whether there is a number X such that if you set A:=A^X or B:=B^X or C:=C^X then you will have A<=B<=C ???? I couldn't understand what do you mean exactly ..
Yes, we have to set A:=A^X and B:=B^X and C:=C^X, then we need A<=B<=C, we have to find the value of x if it exists and if yes then print it else print -1.
is it a codeforces problem???.. If so then can you send me the link? because I have a solution.. but am not sure about it..
Actually it is a problem from GFG(www.geeksforgeeks.org) and unfortunately the problem is made to be private like only for those who have bought that course, but no worries, you can share your thoughts here, and we can discuss :)
Ah ok .. my solution is that maybe you can split the problem into three subproblems: the first problem is that you have to find what is the smallest Y such that A^Y <= B^Y..
The second is to find the smallest Z such that A^Z <= C^Z.. And the third is to find the smallest K such that B^K <= C^K..
And the final X will be equal to (Y|Z|K) and then you check if it's valid or not.. I am not sure if it works or not .. but this may help you
I will sure try this ,thanks for the effort friend!
It works, but we can take just x = (Y|K) and don't calculate Z at all, because if A^(Y|K) <= B^(Y|K) and B^(Y|K) <= C^(Y|K), A^(Y|K) <= C^(Y|K) holds.
That's correct.. Actually I added Z just to make sure that A will be smaller than C because I couldn't find a proof for that..
thanks for the proof :)