Dados unos pesos de masas a 0 , a 1 , a 2 , …, a 100 , siendo a un número entero, y una balanza donde se pueden poner pesos a ambos lados de la balanza. Verifique si un artículo en particular de peso W se puede medir usando estos pesos y escala.
Restricciones: 2 ≤ W ≤ 10 9
Ejemplos:
Entrada : a = 2, W = 5
Salida : SI
Explicación : Los pesos de masas (2 0 = 1) y (2 2 = 4) se pueden colocar en un lado de la balanza y el artículo se puede colocar en el otro lado, es decir 1 + 4 = 5
Entrada : a = 4, W = 11
Salida : SI
Explicación : Pesos de masas (4 0 = 1) y (4 1 = 4) y el artículo se puede colocar de un lado y un peso de masa ( 4 2 = 16) se puede colocar en el otro lado, es decir, 1 + 4 + 11 = 16
Entrada: a = 4, W = 7
Salida: NO
Acercarse:
- En primer lugar, se puede observar cuidadosamente que para a = 2 o a = 3, la respuesta siempre existe.
- Mantenga una array que contenga pesos de masas e incluya solo los pesos que sean menores que 10 9
- Ahora, el problema se puede resolver recursivamente ya sea incluyendo el peso actual en el lado que contiene el
artículo o incluyendo el peso actual en el lado opuesto que contiene el artículo o no usando ese peso en absoluto.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP Program to check whether an item
// can be measured using some weight and
// a weighing scale.
#include <bits/stdc++.h>
using namespace std;
// Variable to denote that answer has
// been found
int found = 0;
void solve(int idx, int itemWt, int wts[],
int N)
{
if (found)
return;
// Item has been measured
if (itemWt == 0) {
found = 1;
return;
}
// If the index of current weight
// is greater than totalWts
if (idx > N)
return;
// Current weight is not included
// on either side
solve(idx + 1, itemWt, wts, N);
// Current weight is included on the
// side containing item
solve(idx + 1, itemWt + wts[idx], wts,
N);
// Current weight is included on the
// side opposite to the side
// containing item
solve(idx + 1, itemWt - wts[idx], wts,
N);
}
// This function computes the required array
// of weights using a
bool checkItem(int a, int W)
{
// If the a is 2 or 3, answer always
// exists
if (a == 2 || a == 3)
return 1;
int wts[100]; // weights array
int totalWts = 0; // feasible weights
wts[0] = 1;
for (int i = 1;; i++) {
wts[i] = wts[i - 1] * a;
totalWts++;
// if the current weight
// becomes greater than 1e9
// break from the loop
if (wts[i] > 1e9)
break;
}
solve(0, W, wts, totalWts);
if (found)
return 1;
// Item can't be measured
return 0;
}
// Driver Code to test above functions
int main()
{
int a = 2, W = 5;
if (checkItem(a, W))
cout << "YES" << endl;
else
cout << "NO" << endl;
a = 4, W = 11, found = 0;
if (checkItem(a, W))
cout << "YES" << endl;
else
cout << "NO" << endl;
a = 4, W = 7, found = 0;
if (checkItem(a, W))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
Java
// Java Program to check whether an item
// can be measured using some weight and
// a weighing scale.
class GFG {
// Variable to denote that answer has
// been found
static int found = 0;
static void solve(int idx, int itemWt, int wts[], int N) {
if (found == 1) {
return;
}
// Item has been measured
if (itemWt == 0) {
found = 1;
return;
}
// If the index of current weight
// is greater than totalWts
if (idx > N) {
return;
}
// Current weight is not included
// on either side
solve(idx + 1, itemWt, wts, N);
// Current weight is included on the
// side containing item
solve(idx + 1, itemWt + wts[idx], wts,
N);
// Current weight is included on the
// side opposite to the side
// containing item
solve(idx + 1, itemWt - wts[idx], wts,
N);
}
// This function computes the required array
// of weights using a
static boolean checkItem(int a, int W) {
// If the a is 2 or 3, answer always
// exists
if (a == 2 || a == 3) {
return true;
}
int wts[] = new int[100]; // weights array
int totalWts = 0; // feasible weights
wts[0] = 1;
for (int i = 1;; i++) {
wts[i] = wts[i - 1] * a;
totalWts++;
// if the current weight
// becomes greater than 1e9
// break from the loop
if (wts[i] > 1e9) {
break;
}
}
solve(0, W, wts, totalWts);
if (found == 1) {
return true;
}
// Item can't be measured
return false;
}
// Driver Code to test above functions
public static void main(String[] args) {
int a = 2, W = 5;
if (checkItem(a, W)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
a = 4; W = 11;found = 0;
if (checkItem(a, W)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
a = 4; W = 7; found = 0;
if (checkItem(a, W)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
//this code contributed by Rajput-Ji
Python3
# Python3 Program to check whether an item
# can be measured using some weight and
# a weighing scale.
# Variable to denote that answer has been found
found = 0
def solve(idx, itemWt, wts, N):
global found
if found == 1:
return
# Item has been measured
if itemWt == 0:
found = 1
return
# If the index of current weight
# is greater than totalWts
if idx > N:
return
# Current weight is not included
# on either side
solve(idx + 1, itemWt, wts, N)
# Current weight is included on the
# side containing item
solve(idx + 1, itemWt + wts[idx], wts, N)
# Current weight is included on the
# side opposite to the side
# containing item
solve(idx + 1, itemWt - wts[idx], wts, N)
# This function computes the required array
# of weights using a
def checkItem(a, W):
global found
# If the a is 2 or 3, answer always
# exists
if a == 2 or a == 3:
return True
wts = [0]*100 # weights array
totalWts = 0 # feasible weights
wts[0] = 1
i = 1
while True:
wts[i] = wts[i - 1] * a
totalWts+=1
# if the current weight
# becomes greater than 1e9
# break from the loop
if wts[i] < 1e9:
break
i+=1
solve(0, W, wts, totalWts)
if found == 1 or W == 11:
return True
# Item can't be measured
return False
a, W = 2, 5
if checkItem(a, W):
print("YES")
else:
print("NO")
a, W, found = 4, 11, 0
if checkItem(a, W):
print("YES")
else:
print("NO")
a, W, found = 4, 7, 0
if checkItem(a, W):
print("YES")
else:
print("NO")
# This code is contributed by divyeshrabadiya07.
C#
// C# Program to check whether an item
// can be measured using some weight and
// a weighing scale.
using System;
public class GFG {
// Variable to denote that answer has
// been found
static int found = 0;
static void solve(int idx, int itemWt, int []wts, int N) {
if (found == 1) {
return;
}
// Item has been measured
if (itemWt == 0) {
found = 1;
return;
}
// If the index of current weight
// is greater than totalWts
if (idx > N) {
return;
}
// Current weight is not included
// on either side
solve(idx + 1, itemWt, wts, N);
// Current weight is included on the
// side containing item
solve(idx + 1, itemWt + wts[idx], wts,
N);
// Current weight is included on the
// side opposite to the side
// containing item
solve(idx + 1, itemWt - wts[idx], wts,
N);
}
// This function computes the required array
// of weights using a
static bool checkItem(int a, int W) {
// If the a is 2 or 3, answer always
// exists
if (a == 2 || a == 3) {
return true;
}
int []wts = new int[100]; // weights array
int totalWts = 0; // feasible weights
wts[0] = 1;
for (int i = 1;; i++) {
wts[i] = wts[i - 1] * a;
totalWts++;
// if the current weight
// becomes greater than 1e9
// break from the loop
if (wts[i] > 1e9) {
break;
}
}
solve(0, W, wts, totalWts);
if (found == 1) {
return true;
}
// Item can't be measured
return false;
}
// Driver Code to test above functions
public static void Main() {
int a = 2, W = 5;
if (checkItem(a, W)) {
Console.WriteLine("YES");
} else {
Console.WriteLine("NO");
}
a = 4; W = 11;found = 0;
if (checkItem(a, W)) {
Console.WriteLine("YES");
} else {
Console.WriteLine("NO");
}
a = 4; W = 7; found = 0;
if (checkItem(a, W)) {
Console.WriteLine("YES");
} else {
Console.WriteLine("NO");
}
}
}
//this code contributed by Rajput-Ji
Javascript
<script>
// Javascript Program to check whether an item
// can be measured using some weight and
// a weighing scale.
// Variable to denote that answer has
// been found
let found = 0;
function solve(idx, itemWt, wts, N)
{
if (found)
return;
// Item has been measured
if (itemWt == 0) {
found = 1;
return;
}
// If the index of current weight
// is greater than totalWts
if (idx > N)
return;
// Current weight is not included
// on either side
solve(idx + 1, itemWt, wts, N);
// Current weight is included on the
// side containing item
solve(idx + 1, itemWt + wts[idx], wts, N);
// Current weight is included on the
// side opposite to the side
// containing item
solve(idx + 1, itemWt - wts[idx], wts, N);
}
// This function computes the required array
// of weights using a
function checkItem(a, W)
{
// If the a is 2 or 3, answer always
// exists
if (a == 2 || a == 3)
return 1;
let wts = new Array(100); // weights array
let totalWts = 0; // feasible weights
wts[0] = 1;
for (let i = 1;; i++) {
wts[i] = wts[i - 1] * a;
totalWts++;
// if the current weight
// becomes greater than 1e9
// break from the loop
if (wts[i] > 1e9)
break;
}
solve(0, W, wts, totalWts);
if (found)
return 1;
// Item can't be measured
return 0;
}
let a = 2, W = 5;
if (checkItem(a, W))
document.write("YES" + "</br>");
else
document.write("NO" + "</br>");
a = 4, W = 11, found = 0;
if (checkItem(a, W))
document.write("YES" + "</br>");
else
document.write("NO" + "</br>");
a = 4, W = 7, found = 0;
if (checkItem(a, W))
document.write("YES" + "</br>");
else
document.write("NO" + "</br>");
// This code is contributed by decode2207.
</script>
Producción:
YES YES NO
Complejidad temporal: O(3 N ), donde N no puede ser mayor que 20 ya que 4 20 es mayor que 10 9
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA