[JAVA] ABC --030- A & B & C

AtCoder ABC 030 A&B&C AtCoder - 030

A problem

--Since it is troublesome to handle the decimal point, change to multiplication -{$ b \ div a <d \ div c } or { b \ div a> d \ div c } -Changed to { b \ times c <d \ times a } or { b \ times c> d \ times a $}

	private void solveA() {
		int a = nextInt();
		int b = nextInt();
		int c = nextInt();
		int d = nextInt();
		if (b * c > a * d) {
			out.println("TAKAHASHI");
		} else if (b * c < a * d) {
			out.println("AOKI");
		} else {
			out.println("DRAW");
		}
	}

B problem

――The angle calculation of the minute hand of the clock is Mendoi --With this calculation method, 23:59 is accurate, but at 23:10, it exceeds 180, so subtract from 360.

	private void solveB() {
		int n = nextInt();
		int m = nextInt();

		double smallHand = n % 12 * 30 + m * 0.5;//n % 12 * (360 / 12) + m * (360 / 12 /  60)
		double longHand = m % 60 * 6;//m % 60 * (360 / 60)

		double res = Double.max(smallHand, longHand) - Double.min(smallHand, longHand);
		/*
		 * 23:10 is greater than 180
		 */
		if (res > 180) {
			out.println(360 - res);
		} else {
			out.println(res);
		}
	}

Problem C: Binary search

--Use binary search --Hereafter, loop until the end of the search (BinarySearch index acquisition exceeds each final Index) --A Get the minimum time you can leave the airport with Binary Search --If you can search, record that you moved to the current time + X --Get the minimum time you can leave Airport B with Binary Search --If you can search, record the current time + Y and move --The number of times the moved count / 2 made a round trip ――However, if it is an even number, it can be considered that you could make a round trip, but if it is an odd number, -1 and then / --To eliminate the case of moving only to X-> Y

	private void solveC2() {
		int n = nextInt();
		int m = nextInt();
		long x = nextInt();
		long y = nextInt();
		long[] aA = LongStream.range(0, n).map(i -> nextLong()).toArray();
		long[] bA = LongStream.range(0, m).map(i -> nextLong()).toArray();

		/*
		 * true = airport A
		 * false = airport B
		 */
		boolean isAirportA = true;
		long currentTime = 0;
		long moveCnt = 0;
		while (true) {
			/*
			 *Airport A or B departure
			 */
			if (isAirportA) {
				/*
				 *Find a flight at Airport A that can depart from the current time
				 */
				int aI = Arrays.binarySearch(aA, currentTime);
				aI = aI >= 0 ? aI : ~aI;
				//As a result of the binary search, if you reach the last index position, it is already over
				if (aI >= n) {
					break;
				}
				/*
				 *Departure time from the next B airport
				 */
				currentTime = aA[aI] + x;
				/*
				 *Next is B Airport
				 */
				isAirportA = false;
				moveCnt++;
			} else {
				/*
				 *The content is just replacing all the values of A airport with B
				 */
				int bI = Arrays.binarySearch(bA, currentTime);
				bI = bI >= 0 ? bI : ~bI;
				if (bI >= m) {
					break;
				}
				currentTime = bA[bI] + y;
				isAirportA = true;
				moveCnt++;
			}
		}
		/*
		 *When the number of movements is odd, X->I just went to Y
		 *I haven't been able to make a round trip.
		 *Therefore, the movement of that time is pear
		 */
		if ((moveCnt & 1) == 1) {
			moveCnt -= 1;
		}
		/*
		 *The number of times that half of the number of people on the plane could make a round trip
		 */
		out.println(moveCnt / 2);

	}

Problem C: Another solution (determined only by for, not using binary search)

-$ O (2N) $? Computational complexity

――I was able to immediately come up with a binary search and implement it, but it was dirty, so if I was looking for another method, I felt that I could implement it here as well, so I tried it. ――Rather than searching all $ A [i] and B [i] $ each time, if you keep the index in the middle, why not just turn both arrays once? The idea

--Find the departure time of A Airport --Get {$ departure time + X } at A airport --Find the departure time of B Airport --Get { departure time + Y } at B airport & (get the next search start index and stop the time search) --Find the departure time of A Airport --Get { departure time + X $} at A airport --- The following loop

	/*
	 *Full search?
	 */
	private void solveC() {
		int n = nextInt();
		int m = nextInt();
		long x = nextInt();
		long y = nextInt();
		long[] aA = LongStream.range(0, n).map(i -> nextLong()).toArray();
		long[] bA = LongStream.range(0, m).map(i -> nextLong()).toArray();

		int bI = 0;
		long currentTime = 0;
		long moveCnt = 0;
		for (int i = 0; i < n; i++) {
			//Departure times smaller than the current time cannot be used
			if (currentTime > aA[i]) {
				continue;
			}
			//A Can depart from Airport
			currentTime = aA[i] + x;
			//B Start searching for airport time
			for (int j = bI; j < m; j++) {
				//Departure times smaller than the current time cannot be used
				if (currentTime > bA[j]) {
					continue;
				}
				/*
				 *This time can be used, so
				 *・ Set the departure time of the next A airport
				 *・ Set the index for starting the time search at the next B airport
				 */
				currentTime = bA[j] + y;
				bI = j + 1;
				//I was able to leave Airport B, so I was able to make a round trip
				moveCnt++;
				break;
			}
		}
		out.println(moveCnt);
	}