AtCoder Beginner Contest 170 B Problème Explication "Crane and Turtle" (Python3, C ++, Java)

AtCoder Beginner Contest 170 B Je vais expliquer le problème "Crane and Turtle".

URL du problème: https://atcoder.jp/contests/abc170/tasks/abc170_b

Résumé du problème

Il y a des animaux dans le jardin. Comme information ・ Nombre total d'animaux dans le jardin $ X $, ・ Nombre total d'étapes $ Y $ Est donnée. Le nombre de pattes de grue est de 2 $ et le nombre de pattes de tortue est de 4 $.

Déterminez s'il existe une combinaison de numéros de grue et de tortue qui correspond aux informations $ X $, $ Y $. production: -Output existant "" Oui "` -Output comme "" Non "qui n'existe pas

Contrainte

・ $ 1 \ leq X \ leq 100 $ ・ $ 1 \ leq Y \ leq 100 $ ・ Toutes les valeurs d'entrée sont des entiers

Commentaire

Solution 1 (recherche complète)

Heureusement, les contraintes sur $ X $ et $ Y $ sont petites, vous pouvez donc faire ce qui suit:

・ Entrez $ X, Y $ -Déclarer la fonction drapeau $ flag $ et l'initialiser avec 0 ・ Soit le nombre de tortues $ i $, prends $ i $ dans la section de $ (0, X) $, et répète le processus suivant. Si $ Y-2i $ est divisible par $ 4 $ et son quotient est $ X-i $ Sort «Oui» et termine la boucle suivante Cela soulève le drapeau de combinaison, alors ajoutez 1 à $ flag $ ・ Si $ flag = 0 $, il n'y a pas de combinaison, donc afficher " Non "

Un exemple de réponse dans Python 3 est le suivant. (C ++ et Java peuvent être résolus par la même solution)

Exemple de solution en 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) est défini car la valeur de i est prise dans l'intervalle de $ (0, x) $. Pour i dans la plage (x), la valeur de i est prise dans l'intervalle de $ (0, x-1) $.

Solution 2

Si le nombre de grues est $ a $ et le nombre de tortues est $ b $, les équations simultanées suivantes seront valables.


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

Si vous résolvez ceci


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

Vous pouvez obtenir deux solutions. Il vous suffit de déterminer si les deux sont des solutions entières et supérieures à 0. </ b> (La contrainte étant petite, cette fois la solution 1 Mais je peux me permettre de respecter le délai d'exécution) </ font>

Exemple de solution en 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")

En général, il est souvent résolu par la solution 1 au lieu de la solution 2, voici donc quelques exemples de solutions C ++ et Java résolues par la solution 1.

Exemple de solution en 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;
  }
}
Exemple de solution en Java (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