A or B
Problem Statement :
Consider four numbers: , , , and . You must change at most bits in and to form the numbers and satisfying the equation . Here, the | symbol denotes the bitwise OR operation. Given sets of the numbers defined above, find and print the respective values of and on new lines; if no such value exists, print instead. If there are multiple solutions, make as small as possible; if there are still multiple solutions, make as small as possible. Input Format The first line contains an integer, , denoting the number of queries. The subsequent lines describe each respective query as follows: The first line contains a single integer denoting the value of . Each of the next lines contains a Hexadecimal (base 16) number describing the respective values of , , and . Output Format Print two lines of output for each query: The first line should contain a Hexadecimal (base 16) number denoting the value of A'. The second line must contain a Hexadecimal (base 16) number denoting the value of B'. If no valid answer exists, you must instead print one line of output with the integer 1. Note: The letters in Hexadecimal numbers must be in uppercase.
Solution :
Solution in C :
In C :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int n;
char s[500000];
int a[500000],b[500000],c[500000];
void trans1(char s[],int a[]) {
int i,l=strlen(s);
for(i=0;i<l;i++) if (s[i]>='A') a[l-i-1]=s[i]-'A'+10; else a[l-i-1]=s[i]-'0';
}
void trans2(int a[],int l,char s[]) {
int i;
while(l>1 && a[l-1]==0) l--;
for(i=0;i<l;i++) if (a[i]>=10) s[l-1-i]=a[i]-10+'A'; else s[l-1-i]=a[i]+'0';
s[l]='\0';
}
int main() {
int i,N,l1,l2,l3,l,j,aa,bb,cc,dd,ee;
for(scanf("%d",&N);N--;) {
scanf("%d",&n);
scanf("%s",s);
trans1(s,a);
l1=strlen(s);
scanf("%s",s);
trans1(s,b);
l2=strlen(s);
scanf("%s",s);
trans1(s,c);
l3=strlen(s);
l=l1;
if (l2>l) l=l2;
if (l3>l) l=l3;
for(i=0;i<l && n>=0;i++) for(j=0;j<4 && n>=0;j++) {
aa=(a[i]>>j)&1;
bb=(b[i]>>j)&1;
cc=(c[i]>>j)&1;
if (!cc) {
if (aa) a[i]&=15^(1<<j),n--;
if (bb) b[i]&=15^(1<<j),n--;
} else if (!aa && !bb) {
b[i]|=1<<j,n--;
}
}
for(i=l-1;i>=0 && n>0;i--) for(j=3;j>=0 && n>0;j--) {
aa=(a[i]>>j)&1;
bb=(b[i]>>j)&1;
cc=(c[i]>>j)&1;
if (aa && bb) a[i]&=15^(1<<j),n--;
else if (aa && !bb && n>1) a[i]&=15^(1<<j),b[i]|=1<<j,n-=2;
}
if (n<0) {
puts("-1");
continue;
}
trans2(a,l,s);
printf("%s\n",s);
trans2(b,l,s);
printf("%s\n",s);
}
return 0;
}
Solution in C++ :
In C ++ :
#include <bits/stdc++.h>
using namespace std;
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void PR(vi &v) { trav(x, v) cout << x << ' '; cout << endl; }
void unhex(char& c) {
if (0 <= c && c < 10) c = (char)('0' + c);
else c = (char)('A' + (c - 10));
}
void rehex(char& c) {
if ('0' <= c && c <= '9') c = (char)(c - '0');
else c = (char)(c - 'A' + 10);
}
string trim0(string& s) {
trav(x, s) unhex(x);
rep(i,0,sz(s)) {
if (s[i] != '0') return s.substr(i);
}
return "0";
}
bool solve() {
int K, N;
string a, b, c;
cin >> K;
cin >> a >> b >> c;
N = max(max(sz(a), sz(b)), sz(c));
a = string(N-sz(a), '0') + a;
b = string(N-sz(b), '0') + b;
c = string(N-sz(c), '0') + c;
trav(x, a) rehex(x);
trav(x, b) rehex(x);
trav(x, c) rehex(x);
int bits[4] = {8,4,2,1};
rep(i,0,N) trav(bi, bits) {
if (!(c[i]&bi)) {
if (a[i]&bi) {
a[i] &= ~bi;
--K;
}
if (b[i]&bi) {
b[i] &= ~bi;
--K;
}
}
else {
if (!((a[i]&bi) || (b[i]&bi))) {
b[i] |= bi;
--K;
}
}
}
if (K < 0) return false;
rep(i,0,N) trav(bi, bits) {
if (c[i]&bi) {
if ((a[i]&bi) && (b[i]&bi) && K >= 1) {
a[i] &= ~bi;
K--;
}
else if ((a[i]&bi) && K >= 2) {
a[i] &= ~bi;
b[i] |= bi;
K -= 2;
}
}
}
cout << trim0(a) << endl;
cout << trim0(b) << endl;
return true;
}
int main() {
cin.sync_with_stdio(false);
cin.exceptions(cin.failbit);
int N;
cin >> N;
rep(i,0,N) {
if (!solve()) cout << -1 << endl;
}
}
Solution in Java :
In Java :
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class B
{
String line;
StringTokenizer inputParser;
BufferedReader is;
FileInputStream fstream;
DataInputStream in;
String FInput="";
void openInput(String file)
{
if(file==null)is = new BufferedReader(new InputStreamReader(System.in));//stdin
else
{
try{
fstream = new FileInputStream(file);
in = new DataInputStream(fstream);
is = new BufferedReader(new InputStreamReader(in));
}catch(Exception e)
{
System.err.println(e);
}
}
}
void readNextLine()
{
try {
line = is.readLine();
inputParser = new StringTokenizer(line, " ,\t");
//System.err.println("Input: " + line);
} catch (IOException e) {
System.err.println("Unexpected IO ERROR: " + e);
}
catch (NullPointerException e)
{
line=null;
}
}
long NextLong()
{
String n = inputParser.nextToken();
long val = Long.parseLong(n);
return val;
}
int NextInt()
{
String n = inputParser.nextToken();
int val = Integer.parseInt(n);
//System.out.println("I read this number: " + val);
return val;
}
double NextDouble()
{
String n = inputParser.nextToken();
double val = Double.parseDouble(n);
//System.out.println("I read this number: " + val);
return val;
}
String NextString()
{
String n = inputParser.nextToken();
return n;
}
void closeInput()
{
try {
is.close();
} catch (IOException e) {
System.err.println("Unexpected IO ERROR: " + e);
}
}
public static void main(String [] argv)
{
//String filePath="circles.in";
String filePath=null;
if(argv.length>0)filePath=argv[0];
new B(filePath);
}
public B(String inputFile)
{
openInput(inputFile);
readNextLine();
int T=NextInt();
StringBuilder sb = new StringBuilder();
for(int t=1; t<=T; t++)
{
readNextLine();
int K = NextInt();
readNextLine();
//String A = line;
//BigInteger a = new BigInteger(A, 16);
boolean [] a = hexStringToBooleanArray(line);
readNextLine();
//String B = line;
//BigInteger b = new BigInteger(B, 16);
boolean [] b = hexStringToBooleanArray(line);
readNextLine();
//String C = line;
//BigInteger c = new BigInteger(C, 16);
boolean [] c = hexStringToBooleanArray(line);
int len = a.length;
len = Math.max(len, b.length);
len = Math.max(len, c.length);
boolean [] ra = new boolean[len];
and(ra, a,c);
boolean [] rb = new boolean[len];
and(rb, b,c);
boolean [] cxra = new boolean[len];
xor(cxra, c, ra);
or(rb, rb, cxra);
boolean [] xa = new boolean[len];
int da = xor(xa, ra, a);
boolean [] xb = new boolean[len];
int db = xor(xb, rb, b);
if(da+db>K){
sb.append("-1\n");
}
else{
int dd = K - da - db;
if(dd>0)
{
boolean [] X = new boolean[len];
for(int i=0; i<ra.length&&dd>0; i++){
if(ra[i])
{
if(dd==1&&!rb[i])continue;
dd--;
X[i]=true;
if(!rb[i])dd--;
}
}
xor(ra, ra, X);
or(rb, rb, X);
}
sb.append(toStr(ra)+"\n");
sb.append(toStr(rb)+"\n");
}
/*
BigInteger ra = a.and(c);
BigInteger rb = b.and(c).or(c.xor(ra));
int da = a.xor(ra).bitCount();
int db = b.xor(rb).bitCount();
if(da+db>K)sb.append("-1\n");
else
{
int dd = K - da - db;
if(dd>0)
{
/*String x = ra.toString(2);
BigInteger X = BigInteger.ZERO;
for(int i=0; i<x.length()&&dd>0; i++){
if(x.charAt(i)=='1')
{
if(dd==1&&!rb.testBit(x.length()-i-1))continue;
dd--;
X = X.setBit(x.length()-i-1);
if(!rb.testBit(x.length()-i-1))dd--;
}
}
ra = ra.xor(X);
rb = rb.or(X);*
}
sb.append(ra.toString(16).toUpperCase()+"\n");
sb.append(rb.toString(16).toUpperCase()+"\n");
}*/
}
System.out.print(sb);
closeInput();
}
private String toStr(boolean[] rb) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<rb.length; i++)
if(rb[i])sb.append(1);
else sb.append(0);
BigInteger b = new BigInteger(sb.toString(), 2);
return b.toString(16).toUpperCase();
}
private void or(boolean[] xa, boolean[] ra, boolean[] a) {
int len = xa.length;
len = Math.min(len, ra.length);
len = Math.min(len, a.length);
for(int i=0; i<len; i++){
xa[xa.length-i-1] = a[a.length - i - 1]|ra[ra.length - i - 1];
}
}
private int xor(boolean[] xa, boolean[] ra, boolean[] a) {
int len = xa.length;
len = Math.min(len, ra.length);
len = Math.min(len, a.length);
int ret = 0;
for(int i=0; i<len; i++){
xa[xa.length-i-1] = a[a.length - i - 1]^ra[ra.length - i - 1];
if(xa[xa.length-i-1])ret++;
}
return ret;
}
private void and(boolean[] ra, boolean[] a, boolean[] b) {
int len = a.length;
len = Math.min(len, b.length);
len = Math.min(len, ra.length);
for(int i=0; i<len; i++){
ra[ra.length-i-1] = a[a.length - i - 1]&b[b.length - i - 1];
}
}
public boolean [] hexStringToBooleanArray(String s) {
int len = s.length();
boolean [] ret = new boolean[len*4];
for(int i=0; i<len; i++){
int x = Character.digit(s.charAt(i), 16);
if((x&1)>0)ret[i*4+3] = true;
if((x&2)>0)ret[i*4+2] = true;
if((x&4)>0)ret[i*4+1] = true;
if((x&8)>0)ret[i*4] = true;
}
return ret;
}
public byte[] hexStringToByteArray(String s) {
int len = s.length();
byte[] data = new byte[len / 2];
for (int i = 0; i < len; i += 2) {
data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
+ Character.digit(s.charAt(i+1), 16));
}
return data;
}
}
Solution in Python :
In Python3 :
Q = int(input())
for _ in range(Q):
k = int(input())
A = bin(int(input(), 16))[2:]
B = bin(int(input(), 16))[2:]
C = bin(int(input(), 16))[2:]
l = max(len(A), len(B), len(C))
A = list('0' * (l - len(A)) + A)
B = list('0' * (l - len(B)) + B)
C = list('0' * (l - len(C)) + C)
for i in range(l):
if A[i] == B[i] == '0' and C[i] == '1':
B[i] = '1'
k -= 1
if A[i] > C[i] or B[i] > C[i]:
if A[i] == '1':
A[i] = '0'
k -= 1
if B[i] == '1':
B[i] = '0'
k -= 1
if k < 0:
print(-1)
continue
for i in range(l):
if A[i] == '1' and B[i] == '1' and k > 0:
A[i] = '0'
k -= 1
if A[i] == '1' and B[i] == '0' and k > 1:
A[i] = '0'
B[i] = '1'
k -= 2
print("%X" % int(''.join(A), 2))
print("%X" % int(''.join(B), 2))
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →