solved.ac Grand Arena #3

In this problem, we need to calculate the number of bundles of T-shirts of each size, and the number of bundles of pens that we need to order. First, let's look at how we can find the number of bundles of pens as this is simpler.

Pens

To find how many bundles of pens we should order, we need to group the $N$ pens in bundles of $P$. By dividing $N$ by $P$, we can get the quotient $q$ and remainder $r$. As a mathematical expression, we can denote this as $N \div P = q \cdots r$. This means by grouping the pens in bundles of $P$, we get $q$ complete bundles and $r$ remaining. These $q, r$ values are the number of bundles of pens that we need to order, and the number of pens we need to order one by one, respectively.

T-Shirts

Solution 1

Now let's find the number of bundles of T-shirts of size S that we need to buy.

We use division again to group T-shirts of size $S$ in bundles of $T$. Let's call the quotient and remainder of this division $q, r$ respectively. $(S \div T = q \cdots r)$

• If $r = 0$, we can distribute T-shirts without any leftovers by ordering exactly $q$ bundles. The answer is $q$.

• If $r > 0$, $r$ more T-shirts must be ordered after ordering $q$ bundles. Since T-shirts cannot be ordered one by one, we need to order one more bundle. Thus, the answer is $q+1$.

This can be implemented as follows in the following languages. Variable names are S, T respectively, and the answer is res .

C++

int q = S / T, r = S % T;
int res = q + (r > 0 ? 1 : 0);

Python

q, r = S // T, S % T
res = q + (1 if r > 0 else 0)

Rust

let q = S / T;
let r = S % T;
let res = q + if r > 0 { 1 } else { 0 };

Solution 2

We can write the code without using if statements too. First let's define the following symbols.

• $\frac{a}{b}$: The value of $a$ divided by $b$.
  • Here we use the division between real numbers instead of between integers.
  • For example, $\frac{9}{5} = 1.8$.
• $\left \lfloor x \right \rfloor, \left \lceil x \right \rceil$: The largest integer smaller than or equal to $x$, and the smallest integer larger than or equal to $x$, respectively.
  • For example, $\lfloor 3 \rfloor = 3, \lfloor 3.14 \rfloor = 3, \lfloor 4 \rfloor = 4$.
  • For example, $\lceil 3 \rceil = 3, \lceil 3.14 \rceil = 4, \lceil 4 \rceil = 4$.
  • If $x$ is an integer , $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor$.
  • If $x$ is not an integer, $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor + 1$.

The quotient in the integer division of $S$ by $T$ is $\left\lfloor \frac{S}{T} \right \rfloor$. After dividing $S$ by $T$, this is obtained by removing the fractional part that we cannot group in bundles of $T$. However, we need to find $\left \lceil \frac{S}{T} \right \rceil$ in this problem. Even if there is a fractional part remaining, we need to think of it as $1$ complete bundle.

Now, let's prove the following. For an integer $S$ greater than or equal to $0$, and an integer $T$ greater than or equal to $1$, $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac{S+T-1}{T} \right\rfloor$.

• If $S$ is a multiple of $T$, $\left\lceil \frac{S}{T} \right\rceil = \frac{S}{T}$, and $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S}{T} + \frac{T-1}{T} \right\rfloor$. Since $\frac{S}{T}$ is an integer, and $\frac{T-1}{T}$ is ignored as it is smaller than $1$, $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \frac{S}{T}$.

• If $S$ is not a multiple of $T$, $\frac{S}{T}$ is not an integer, so $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac S T \right\rfloor + 1$. Furthermore, since there is at least $1$ remainder from $S$, we get the same quotient when dividing $S-1$ by $T$. That is, $\left \lfloor \frac{S-1}{T} \right \rfloor = \left \lfloor \frac{S}{T} \right\rfloor$. $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S-1}{T} + \frac{T}{T} \right\rfloor = \left\lfloor \frac{S}{T} \right \rfloor + 1 = \left\lceil \frac S T \right \rceil$.

We can make our code much simpler using this method. Below are example solutions written in each language.

Code (C++)

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> sizes(6);
    for (int &size : sizes)
        cin >> size;
    int T, P;
    cin >> T >> P;
    int sumv = 0;
    for (int size : sizes)
        sumv += (size + T - 1) / T;
    cout << sumv << endl;
    cout << N / P << " " << N % P << endl;
}

Code (Python)

def main():
    N = int(input())
    sizes = list(map(int, input().split()))
    T, P = map(int, input().split())
    print(sum((size + T - 1) // T for size in sizes))
    print(N // P, N % P)


if __name__ == '__main__':
    main()

Code (Rust)

use std::io::*;

fn main() {
    let n = read_vec()[0];
    let sizes = read_vec();
    let (t, p) = {
        let v = read_vec();
        (v[0], v[1])
    };

    println!("{}", sizes.iter().map(|x| (x + t - 1) / t).sum::<u32>());
    println!("{} {}", n / p, n % p);
}

fn read_vec() -> Vec<u32> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}