CCC '97 S5 - Long Division - Olympiads Online Judge

CCC '97 S5 - Long Division

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 256M

Problem types

Allowed languages

ALGOL 68, Assembly, Brain****, C, C++, COBOL, Forth, Fortran, Java, Lua, Pascal, Text, Turing

In days of yore (circa 1965), mechanical calculators performed division by shifting and repeated subtraction. For example, to divide 987654321 by 3456789, the numbers would first be aligned by their leftmost digit (see Figure 1 below), and the divisor subtracted from the dividend as many times as possible without yielding a negative number. The number of successful subtractions (in this example, 2) is the first digit of the quotient. The divisor, shifted to the right (see Figure 2 below), is subtracted from the remainder several times to yield the next digit, and so on until the remainder is smaller than the divisor.

Figure 1:

    987654321
-   3456789         first successful subtraction
    ========
    641975421
-   3456789         second successful subtraction
    ========
    296296521       remainder
-   3456789         unsuccessful subtraction
    ========
    negative

Figure 2:

     296296521
-     3456789
     ========
     261728631
     etc.

Write a program to implement this method of division. See the input and output specifications below.

Input Specification

The first line of the input file will contain a positive integer $n$ ~n~, $n < 20$ ~n < 20~, which represents the number of test cases which follow. Each test case is provided on a pair of lines, with the number on the first line being the dividend, and the number on the second line being the divisor. Each line will contain a positive integer of up to 80 digits in length.

Output Specification

For each pair of input lines, your output file should contain a pair of lines representing the quotient followed by the remainder. Output for different test cases should be separated by a single blank line. Your output should omit unnecessary leading zeros.

Sample Input

Sample Output

Comments

0

maxcruickshanks commented on Dec. 19, 2022, 3:55 a.m.

Since the checker was not implemented properly, it was fixed, and all submissions were rejudged.

15

echofox commented on Dec. 5, 2019, 4:54 a.m.

thank god text is allowed, not sure what i would do if it was banned

8

Evan commented on Dec. 4, 2019, 3:28 a.m.

Why isn't python allowed?

-15

Plasmatic commented on Dec. 4, 2019, 2:21 p.m.

This is likely because of arbitrary precision integers. On that note, I suggest that Java and Pascal should also be banned from this question.

This comment is hidden due to too much negative feedback. Show it anyway.

5

noYou commented on July 20, 2020, 5:48 p.m. ← edited →

SHHHHHHHHHHHHHHH

jk, BigInteger is disabled