天平(Not so Mobile)

Submit Status

Description

Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies.

The figure illustrates a simple mobile. It is just a wire, suspended by a string, with an object on each side. It can also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the lever principle we know that to balance a simple mobile the product of the weight of the objects by their distance to the fulcrum must be equal. That isW_l×D_l = W_r×D_r whereD_l is the left distance, D_r is the right distance, W_l is the left weight andW_r is the right weight.

In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure. In this case it is not so straightforward to check if the mobile is balanced so we need you to write a program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or not.

Input 

The input is composed of several lines, each containing 4 integers separated by a single space. The 4 integers represent the distances of each object to the fulcrum and their weights, in the format:W_l D_l W_r D_r

If W_l or W_r is zero then there is a sub-mobile hanging from that end and the following lines define the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of all its objects, disregarding the weight of the wires and strings. If bothW_l and W_r are zero then the following lines define two sub-mobiles: first the left then the right one.

Output 

Write `YES' if the mobile is in equilibrium, write `NO' otherwise.

Sample Input 

1

0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2
  

Sample Output 

YES
  

       采用递归方式输入。

用C++语言编写程序，代码如下：

#include<iostream>
using namespace std;
//输入一个子天平，返回子天平是否平衡，参数w修改为子天平的总重量
bool solve(int& w) {
	int W1, D1, W2, D2;
	bool b1 = true, b2 = true;
	cin >> W1 >> D1 >> W2 >> D2;
	if (!W1) b1 = solve(W1);
	if (!W2) b2 = solve(W2);
	w = W1 + W2;
	return b1 && b2 && (W1 * D1 == W2 * D2);
}

int main() {
	int T, w;
	cin >> T;
	while (T--) {
		if (solve(w))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		if (T)
			cout << endl;
	}
	return 0;
}

（在测试过程中，曾在递归方法中加入一句输出语句，在提交过程中，忘记对该语句的删除，导致程序时间超限。删除该语句之后就答案正确了）

以下有两个方法可以使得在程序的递归方法中可以传递引用：

方法1：

import java.io.BufferedInputStream;
import java.util.Scanner;

//要注意的是java中并没有所谓的引用传递，当我们传递对象时，方法接受到的对象只不过是指向相同地址值的引用摆了，当我们改变该对象的指向时，并不会影响原来的地址值。
//当我们只是改变对象本身，而没有改变对象的属性时，原对象的内容不变。（这也是为什么下面用Integer代替int改为传递对象不行的原因，Integer对象在方法中被
//重新赋值，也不会影响调用者的Integer对象）
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(new BufferedInputStream(System.in));
		int[] W = new int[1];
		int T = input.nextInt();
		for(int i = 0; i < T; i++) {
			if(i != 0)
				System.out.println();
			
			if(solve(input, W))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
	
	public static boolean solve(Scanner input, int[] W) {
		int[] W1 = new int[1]; int[] W2 = new int[1];
		int D1,D2;
		boolean b1 = true, b2 = true;
		W1[0] = input.nextInt(); D1 = input.nextInt();
		W2[0] = input.nextInt(); D2 = input.nextInt();
		if(W1[0] == 0) b1 = solve(input, W1);
		if(W2[0] == 0) b2 = solve(input, W2);
		W[0] = W1[0] + W2[0];
		//System.out.println(W[0]);
		return b1 && b2 && (W1[0] * D1 == W2[0] * D2);
	}
}

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(new BufferedInputStream(System.in));
		int T = input.nextInt();
		Weight w = new Weight();
		for(int i = 0; i < T; i++) {
			if(i != 0)
				System.out.println();
			
			if(solve(input, w))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
	
	static class Weight {
		int w;
		public Weight(int w) {
			this. w = w;
		}
		public Weight() {
			super();
		}
	}
	
	public static boolean solve(Scanner input, Weight W) {
		Weight W1 = new Weight();
		Weight W2 = new Weight();
		int D1, D2;
		boolean b1 = true, b2 = true;
		W1.w = input.nextInt(); D1 = input.nextInt();
		W2.w = input.nextInt(); D2 = input.nextInt();
		if(W1.w == 0) b1 = solve(input, W1);
		if(W2.w == 0) b2 = solve(input, W2);
		W.w = W1.w + W2.w;
		//System.out.println(W.w);
		return b1 && b2 && (W1.w * D1 == W2.w * D2);
	}
}