AtCoder Beginner Contest 170 B Problem "Crane and Turtle" Explanation (Python3, C ++, Java)

AtCoder Beginner Contest 170 B I will explain the problem "Crane and Turtle".

Problem URL: https://atcoder.jp/contests/abc170/tasks/abc170_b

Problem summary

There are some animals in the garden. As information ・ Total number of animals in the garden $ X $, ・ Total number of legs $ Y $ Is given. The number of crane legs is $ 2 $ and the number of turtle legs is $ 4 $.

Determine if there is a combination of crane and turtle numbers that fits the $ X $, $ Y $ information. output: -Output existing " Yes " -Output as " No " that does not exist

Constraint

・ $ 1 \ leq X \ leq 100 $ ・ $ 1 \ leq Y \ leq 100 $ -All input values are integers

Commentary

Solution 1 (full search)

Fortunately, the constraints on $ X $ and $ Y $ are small, so you can do the following:

・ Enter $ X and Y $ -Declare the flag function $ flag $ and initialize it with 0 ・ Let the number of turtles be $ i $, take $ i $ in the interval of $ (0, X) $, and repeat the following process. ・ If $ Y-2i $ is divisible by $ 4 $ and its quotient is $ X-i $ Outputs " Yes " and ends the subsequent loop This raises the combination flag, so add 1 to $ flag $ ・ If $ flag = 0 $, there is no combination, so output " No "

An example of the answer in Python 3 is as follows. (It can be solved in the same way in C ++ and Java)

Example of solution in Python3 (Solution 1)

{B.py}


x,y = map(int,input().split())
flag = 0
for i in range(x+1):
  if (y - 2*i)%4 == 0 and (y -  2 * i)//4 == x - i:
    flag += 1
    print("Yes")
    break
if flag == 0:
  print("No")
  • For i in range (x + 1) is used because the value of i is taken in the interval of $ (0, x) $. For i in range (x), the value of i is taken in the interval of $ (0, x-1) $.

Solution 2

If the number of cranes is $ a $ and the number of turtles is $ b $, the following simultaneous equations will hold.


  \begin{cases}
    a+b = X \\
    2a+4b = Y
  \end{cases}

If you solve this


  \begin{cases}
    a = \frac{4x-Y}{2}　\\
    b = \frac{-2x+Y}{2} \\
  \end{cases}

You can get two solutions. You just have to determine if both are integer solutions and greater than 0. </ b> (Since the constraint is small, this time solution 1 But I can afford to meet the execution time limit) </ font>

Example of solution in Python3 (Solution 2)

{B2.Py}


x,y = map(int,input().split())
a = (4*x-y)/2
b = (-2*x+y)/2
if a%1 == 0 and 0 <= a and b%1 == 0 and 0 <=b:
  print("Yes")
else:
  print("No")

In general, it is often solved by Solution 1 instead of Solution 2, so here are some examples of C ++ and Java solutions solved by Solution 1.

Example solution in C ++ (Solution 1)

{B1.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  int flag = 0;
  for (int i = 0; i <= x; i++){
    if ((y-2*i)%4 == 0 && (y - 2 * i)/4 == x-i){
      flag++;
      cout << "Yes" << endl;
      break;
      }
    }
  if (flag == 0){
    cout << "No" << endl;
  }
}
Java solution example (Solution 1)

{B1.cpp}


import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int x = scan.nextInt();
    int y = scan.nextInt();
    int flag = 0;
    for (int i = 0; i <= x; i++){
      if ((y-2*i)%4 == 0 && (y - 2 * i)/4 == x-i){
        flag++;
        System.out.println("Yes");
        break;
      }
    }
    if  (flag == 0){
      System.out.println("No");
    }
  }
}

Recommended Posts