​

This is the 18th day of my participation in Gwen Challenge.

Hello ah, I am gray little ape, a super will write bug program ape!

Welcome to pay attention to my column “daily Blue bridge”, the main role of this column is to share with you in recent years blue Bridge Cup provincial competition and the final and other real questions, analysis of the existing algorithm ideas, data structure and other content, to help you learn more knowledge and technology!

Title: The Number you can’t Buy

Xiao Ming opened a candy store. He had a unique idea: Put the fruit sugar packets into 4 a pack and 7 a bag of the two, can’t split open a candy packaging, children to buy sugar, he can use these two kinds of packaging to combination, some candy, of course, is not the number of combinations, such as 10 to buy candy, you can use the computer test, in this kind of packing cases, the biggest can’t buy the number of 17, Any number greater than 17 can be combined with 4 and 7,

Given the number of two packages, find the maximum number that cannot be combined.

Input:

Two positive integers representing the number of sugar grains in each package (no more than 1000)

Required output:

A positive integer representing the maximum amount of sugar that can’t be bought,

We don’t have to worry about the case where there is no solution

Such as:

User input:

4, 7

The program should output:

17

Such as:

User input:

3 5

The program should output:

7

Resource convention: Peak memory consumption < 64M

CPU usage < 1000ms

Please output strictly in accordance with the requirements, do not gild the lily print similar to: “Please input…” Superfluous content.

All the code is placed in the same source file, and when the test passes, the source is copied and submitted.

Note: Main needs to return 0

Note: Use only the ANSI C/ANSI C++ standards and do not call special functions that depend on the compilation environment or operating system

Note: all dependent functions must be explicitly in the source file. #include cannot be set to ignore common headers through project Settings

When committing, be careful to select the desired compiler type

Answer:

Subject of the solving process of mathematics knowledge, at the same time can also be understood as a equation of binary calculation, in this problem, we can assume that the number of two kinds of packing candy known is a and b, a candy to buy x package, candy to buy b y package, buy altogether C candy, then conform to the requirements of the combination should satisfy the type:

a*x+b*y=C

Here we have two solutions, for two positive integers with no common divisor: the first is to use the formula directly: the largest number that cannot be combined = a*b-a-b

Second: use enumeration way, list all the numbers that can be composed, but there is an upper limit, that is, the number that can be composed should be less than a* B, then according to these numbers that can be composed, find out the largest number that can not be composed, the specific implementation can see the program.

Answer source:

Method one:

Package 2013 Provincial competition import java.util.HashSet; import java.util.Scanner; import java.util.Set; Public class Year2013_t9 {ax+by=C public static void main(String[] args) {Scanner Scanner = new Scanner(System.in); int a = scanner.nextInt(); int b = scanner.nextInt(); System.out.println(answer_one(a, b)); } public static int answer_One (int a,int b) {return a*b-a-b; // Use the formula directly to find the largest number that cannot be formed}}Copy the code

Method 2:

Package 2013 Provincial competition import java.util.HashSet; import java.util.Scanner; import java.util.Set; Public class Year2013_t9 {ax+by=C public static void main(String[] args) {Scanner Scanner = new Scanner(System.in); int a = scanner.nextInt(); int b = scanner.nextInt(); System.out.println(answer_two(a, b)); } public static int answer_two(int a,int b) {int Max = a*b; Ss = new HashSet<Integer>(); For (int x = 0; a*x <= max ; X++) {// enumerate for (int y = 0; b*y <= max; y++) { ss.add(a*x+b*y); For (int I = max-1; int I = max-1; i > 0; i--) { if (! Ss. Contains (I)) {// If this number is not in the hash table, return I; } } return 0; }}Copy the code

Example output:

​

There are deficiencies or improvements, but also hope that small partners put forward messages, learn together!

Interested partners can pay attention to the column!

Grey ape accompany you to progress together!

Finally, I am participating in the contest for 2020 Blogger of the Year. Please help me vote for it!

Vote link:Bss.csdn.net/m/topic/blo…

​

​