UVA Problem 12708 – GCD The Largest Solution in Java

UVA Problem 12708 – GCD The Largest Solution Java Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

I have already solved this problem in c and cpp in this post 12708 – GCD The Largest Solution in c and c++. There I used obvious shortcut technique to solve the problem. Here I will elaborate on a better approach to think this problem. For some reason it was giving wrong answer with buffered string tokenizer with and without BigInteger I couldn’t figure out the problem so, I may later update this with a better java solution.

What is GCD ( Greatest Common Divisor )?

For this problem we are to find the Greatest common divisor for all pairs of number between 1 to N. Where if a number if p. We exclude GCD between (p,p) pair. Because other than the reason it is omitted at the table, the main reason is GCD of (p,p) is also p.

So if whatever the input was that will always be the output.

Explanation:

Here, two inputs given in the problem 2 and 5. Lets use 5.

Let, p = 5
GCD(p,p) = GCD(5,5) = 5

That is certainly wrong and doesn’t match the answer this input.

To generate the matrix of GCD we will require O(n^2) space of which less than ( \frac {n^2}{2} ) or, exactly ( \frac {n^2}{2} - \frac{n}{2} ) cells will be filled. Since whatever we calculate the upper or the lower half both will have mirror values.

Idea:

We know for a number n in a n * n matrix there exist all pairs of number between 1 to n.
Say if input is 3. All pairs of number between 1 and 3 are,

(1,1),(1,2),(1,3),
(2,1),(2,2),(2,3),
(3,1),(3,2),(3,3)

It can be easily that these can be represented in n by n matrix where n = 3.

Generating a larger GCD board to get an idea:

1 2 3 4 5 6 7 8
1
2  1
3  1  1
4  1  2  1
5  1  1  1  1
6  1  2  3  2  1
7  1  1  1  1  1  1
8  1  2  1  4  1  2  1

 

Extra useless information:

From the table it is clearly visible if for a cell the row number can be divided by column number then the column number is the value of that cell otherwise calculate the GCD.

How the table is filled:

From the board, lets take row: 8 and column: 4 for example.

Since (8,4) is number between all pair of number from 1 to 8.

8 = 1 * 8 
  = 2 * 4

The divisors of 8 are,
1, 2, 4, 8
4 = 1 * 4
  = 2 * 2

The divisors of 8 are,
1, 2, 4

The biggest common number between their divisors are 4.
So,

GCD(8,4) = 4

In the ( 8 * 8 ) board the biggest number between all pairs from 1 to 8 is 4. Similarly we can take any two pair of number and get their GCD.

Similarly the answer is calculated for other inputs. From this we see the pattern is that the answer is always floor of half of the input.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

2
2
5

 


Output:

1
2

Java Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: 12708 - GCD The Largest java
 */

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner k = new Scanner(System.in);

        int count = k.nextInt() + 1;

        while (--count > 0) {
            System.out.println( k.nextLong() >> 1);
        }

    }
}

Managerial Accounting: Break Even Point Analysis

Break Even Point:

The point where Total Revenue becomes equal to Total Cost. So at that point there is neither profit nor loss.

Methods of BEP (Break Even Point) Analysis:

(i) Graphical Method.
(ii) Equation Method.
(iii) Formula Method.

The equation and formula method are more accurate. Using equation and formula methods we can get a good graphical representation. Hand plotting graphical method won’t be that accurate.

Below are equation and formula method calculation formula. We can use any one of these methods to get same result.

Point Equation Method Formula Method
BEPQuantity \text{Total Revenue - Total Cost} \frac{\text{Fixed Cost}}{\text{Contribution Margin Ratio}}
BEPsales \text{(CM Ratio x Sales) - Fixed Cost} \frac{\text{Fixed Cost}}{\text{Contribution Margin Ratio}}
Contribution Margin (CM) \text{CM = Sales - Variable Cost} \text{CM = Sales - Variable Cost}
CM Ratio \frac{\text{CM}}{\text{Sales}} \times 100 \frac{\text{CM}}{\text{Sales}} \times 100

 

Sample:

Question:

A coffee shop owner sales per cup of coffee with a selling price of $10 and whose variable expense is $5. The owner’s monthly fixed cost is $500. Find the Break even point.

Solution :

It can be solved in many ways. We can directly plot the graph or use equation method to get the equation and then plot the graph. BEP can be found using formulas above.

To draw the graph we know that,
\text{fixed cost + variable cost = Total cost}

Also at BEP,
\text{Total Revenue - Total cost = 0}

And,
Total \ Revenue - Total \ Cost =  \begin{cases} Profit & \quad \text{if} > 0 \\ Loss & \quad \text{if} < 0 \end{cases}

Let, x be the number of coffee’s sold. Then,

Revenue for 1 cup $10.
Revenue for x cup $10x.
variable cost for 1 cup $5.
variable cost for x cup $5x.
 Total Revenue - Total Cost = 0
 => Total Revenue - (Fixed Cost + variable cost) = 0
 => 10x - (500 + 5x) = 0
 => 5x = 500
 => x = 100  units
To draw the graph we know, fixed cost is stationary so,

fixed cost,

f(x) = 500

total cost,

g(x) = fixed cost + variable cost for x cups
     = f(x) + 5x
     = 500 + 5x

total revenue,

h(x) = selling cost for x cups
     = 10x

Graphing these function, The point where total revenue and total cost touch is the Break even point.
Break even point analysis
Break even point analysis
So after selling more than 100 cups at $10 per cup the owner can expect profit.

 

Question:

ABC company distributes a single product with selling price $16 and whose variable expense is per unit $11. The company’s fixed expense is $16000 monthly.
(i) Prepare profit graph for company up to sales level of $ 4000 units.
(ii) Estimate company’s BEP in unit sales using the profit graph.

Solution:

In 4000 units,

Total revenue = 16 * 4000 
              = 64000
Total Cost = fixed cost + variable cost
           = 16000 + 11 * 4000
           = 60000
Profit = T.R - T.C
       = 64000 - 60000
       = 4000

In 4000 units BEP,

BEP = \frac{F.C}{Sales - V.C} = \frac{16000}{16 - 11} = 3200 \ units

BEP \ sales = 3200 \times 16 = 51200


Now from the information above the graph will be,
BEP analysis
BEP analysis

Managerial Accounting: Cost Sheet Preparation

Application:
Cost Calculation Software.

Question:

Prepare cost sheet for ABC Corporation for last year,
(i) Determine cost of goods manufactured.
(ii) Determine cost of goods sold.
(iii) Prepare an income statement.

Selling expenses 140000
Raw materials Inventories, January 1 90000
Raw materials Inventories, December 31 60000
Direct Labor Cost 150000
Purchase of raw materials 750000
Sales 2500000
Administrative expenses 270000
Manufacturing overhead 640000
Work in process inventory, January 1 180000
Work in process inventory, January 1 100000
Finished goods inventory, January 1 260000
Finished goods inventory, December 31 210000

 

Solution:

ABC Corporation
Statement of cost of goods sold
Particulars Amount ($) Amount ($)
Direct Materials: Raw materials, January 1 90000
Add: Purchase of raw materials 750000
* Raw Materials Available for use 840000
Deduct: Raw Materials, December 31 (60000)
* Raw Materials used / consumed 780000
Add: Direct Labor cost 150000
* Prime cost 930000
Add: Manufacturing overhead 640000
* Total manufacturing cost 1570000
Add: Work in process, January 1 180000
Less: Work in process, January 1 (100000)
(i) Cost of goods manufactured 1650000
Add: Finished goods Inventory, January 1 260000
* Finished goods available for sale 1910000
Less: Finished goods Inventory, December 31 (210000)
(ii) Cost of goods sold 1700000
Note:

Statement of cost of goods sold has both cost of goods manufactured and cost of goods sold. So calculating the Statement of cost of goods sold we can get both.


 

Income Statement:

ABC Corporation
Income statement
For the year ended December 31
Particulars Amount ($) Amount ($)
Sales 2500000
Less: Cost of goods sold (1700000)
* Gross Profit 800000
Less: Operating Expenses
Selling Expenses (140000)
Administrative Expenses (270000)
* Operating Income 390000
Note:

Only manufacturing cost are shown in COGS statement. Non manufacturing cost such as selling, administrative costs are shown in income statement.