Contest Python: USACO Bronze › Unit 11 — Number Systems, Bitwise & Number Theory

Exercises: Unit 11 — Number Systems, Bitwise & Number Theory

Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, then print. Convert by hand (no bin/hex); bitwise & | ^ ~ << >> are fair game. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.

Exercise 1: Decimal to Binary by Hand

The input is one non-negative decimal integer N. Print its binary representation with no leading zeroes, except that zero itself is printed as 0. Build the representation with repeated remainder and integer division; conversion shortcuts are not allowed. In the sample, the final remainder supplies the leftmost 1, so stopping one division early changes the answer.

Constraints. 0 <= N <= 10^18. The output contains only the characters 0 and 1. Use % 2, // 2, and string concatenation.

Sample Input

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build the representation with repeated remainder and integer division; conversion shortcuts are not allowed.
Use % 2, // 2, and string concatenation.

For parents and teachers: report a problem

Exercise 2: Two-Way Hexadecimal Converter

The input contains a non-negative decimal integer N followed by an uppercase hexadecimal string H. Print N written in uppercase hexadecimal on the first line, then print the decimal value of H on the second line. Use the digit string 0123456789ABCDEF, repeated division for the first conversion, and left-to-right positional value for the second. Do not use built-in base-conversion shortcuts. The final digit F in the sample is necessary for the decimal result 687.

Constraints. 0 <= N <= 10^18. H has between 1 and 15 characters and represents a value from 0 through 10^18. Neither output has leading zeroes unless its value is zero.

Sample Input

4095 2AF

Sample Output

FFF
687

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use the digit string 0123456789ABCDEF, repeated division for the first conversion, and left-to-right positional value for the second.
Do not use built-in base-conversion shortcuts.

For parents and teachers: report a problem

Exercise 3: Light Panel Commands

The first line contains a bit width W, a non-negative panel state S, and a command count Q. Each of the next Q lines is TEST i, SET i, CLEAR i, FLIP i, or NOT. Bits are numbered from 0 at the right. TEST i reports 1 if bit i is on and 0 otherwise without changing the state. Every other command changes the current state and reports the new state as a non-negative decimal integer. For NOT, complement exactly W bits by masking the result with (1 << W) - 1; Python's unlimited-width complement must not produce a negative state. Print one reported integer per line. The final NOT command is decisive in the sample.

Constraints. 1 <= W <= 60, 0 <= S < 2^W, and 1 <= Q <= 200000. Every bit index satisfies 0 <= i < W. All states and outputs stay inside the stated W bits and are non-negative.

Sample Input

4 5 5
TEST 0
SET 3
CLEAR 2
FLIP 1
NOT

Sample Output

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

For NOT, complement exactly W bits by masking the result with (1 << W) - 1

For parents and teachers: report a problem

Exercise 4: Lone Signal Code

The first line contains an odd integer N, and the second line contains N non-negative integer signal codes. Exactly one code appears once, and every other code appears exactly twice. Use the XOR property that equal values cancel and print the lone code. The last value in the sample completes the second copy of 9, leaving 6 as the only unpaired code.

Constraints. 1 <= N <= 200001, and N is odd. Every code is a non-negative integer less than 2^60. Use O(N) time and O(1) extra storage.

Sample Input

7
12 4 12 9 4 6 9

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use the XOR property that equal values cancel
Use O(N) time and O(1) extra storage.

For parents and teachers: report a problem

Exercise 5: Exact Cargo Team

The first line contains N and a target weight T, and the second line contains N positive cargo weights. Count the subsets whose total is exactly T. Represent each subset by one mask from 0 through (1 << N) - 1 and test item i with bit i. Your iteration must include both the empty mask and the full mask. In Sample 1, the middle items 1 and 4 form the unique matching subset. In Sample 2, the final weight 2 is necessary for the full mask to total 15.

Constraints. 1 <= N <= 20, 0 <= T <= 10^9, and every weight is between 1 and 10^9. The answer is a non-negative integer. An O(2^N · N) bitmask search is allowed.

Sample Input 1

4 5
8 1 4 10

Sample Output 1

Sample Input 2

4 15
8 1 4 2

Sample Output 2

How this is checked: Checked by running your program on 7 test inputs (1 sample, 6 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Represent each subset by one mask from 0 through (1 << N) - 1 and test item i with bit i.

For parents and teachers: report a problem

Exercise 6: GCD and LCM Reports

The first line contains Q, followed by Q lines containing non-negative integers a b. For each pair, print its GCD and LCM separated by one space, with one pair of answers per line. Compute GCD with iterative Euclid. If either input is zero, the LCM is zero; otherwise compute it by dividing by the GCD before multiplying. The cases include coprime inputs, equal inputs, one input dividing the other, and a shared factor in the decisive final pair.

Constraints. 1 <= Q <= 200000 and 0 <= a, b <= 10^18. The pair a = b = 0 does not occur. Every output is a non-negative integer, and every LCM is at most 10^18.

Sample Input

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Compute GCD with iterative Euclid.
otherwise compute it by dividing by the GCD before multiplying.

For parents and teachers: report a problem

Exercise 7: Prime Count Through a Boundary

The input is one integer N. Use a Sieve of Eratosthenes to print the number of primes from 2 through N, inclusive. Build the Boolean list by appending values in a loop, and begin crossing multiples of each prime p at p * p. The sample ends at 49, so the sieve must cross off the prime square itself rather than leave it marked prime.

Constraints. 0 <= N <= 5000000. The answer is a non-negative integer. Use one sieve through N; testing every candidate by trial division is too slow.

Sample Input

Sample Output

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use a Sieve of Eratosthenes
Build the Boolean list by appending values in a loop, and begin crossing multiples of each prime p at p * p.

For parents and teachers: report a problem

Exercise 8: Astronomical Power Modulo M

The input contains a non-negative base A, a positive modulus M, and a non-negative exponent E, in that order. Print A to the power E, modulo M, as a non-negative integer. Use repeated squaring and reduce every multiplication modulo M; computing the unreduced power first is infeasible. Do not use a built-in modular-power shortcut. The enormous final exponent in the sample makes reduce-as-you-go essential.

Constraints. 0 <= A <= 10^18, 1 <= M <= 10^18, and 0 <= E <= 10^18. The result is always between 0 and M - 1. Your algorithm must use O(log E) modular multiplications.

Sample Input

7 13 1000000000000000000

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use repeated squaring and reduce every multiplication modulo M
Do not use a built-in modular-power shortcut.
Your algorithm must use O(log E) modular multiplications.

For parents and teachers: report a problem

Exercise 9: Fixed-Width Hex Complement

Challenge

The input contains a bit width W followed by an uppercase hexadecimal string H representing a non-negative value x. The width is a multiple of 4, and H has exactly W / 4 digits, including leading zeroes when needed. Print the uppercase hexadecimal representation of the complement of exactly those W bits. Parse and write hexadecimal by hand, compute the complement with ~x & ((1 << W) - 1), and restore leading zeroes with a loop and string concatenation. The final input digit 5 changes the final output digit to A.

Constraints. 4 <= W <= 60, and W is a multiple of 4. H contains exactly W / 4 characters from 0 through 9 or A through F. The output has the same number of digits as H and represents a non-negative W-bit value.

Sample Input

8 A5

Sample Output

5A

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Parse and write hexadecimal by hand, compute the complement with ~x & ((1 << W) - 1), and restore leading zeroes with a loop and string concatenation.

For parents and teachers: report a problem

Exercise 10: Nth Prime

Challenge

The input is one positive integer K. Build a Sieve of Eratosthenes through 200000 and print the Kth prime, where 2 is the first prime. Build the Boolean list with a loop, cross multiples from p * p, and scan the finished sieve in increasing order. The final candidate 47 is the fifteenth prime in the sample.

Constraints. 1 <= K <= 10000. The fixed upper bound 200000 contains at least 10000 primes. The printed prime is a positive integer.

Sample Input

Sample Output

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build a Sieve of Eratosthenes through 200000
Build the Boolean list with a loop, cross multiples from p * p, and scan the finished sieve in increasing order.

For parents and teachers: report a problem

Back to Unit 11 — Number Systems, Bitwise & Number Theory