Scribd Logo
Upload

Welcome to Scribd!

  • 39 views

    Best Compression Ever - Kattis, Kattis

    Uploaded by

    Ye
    This document describes a problem that asks whether it is possible to compress a collection of random bit strings, each 1000 bits long, into files of at most b bits given the number of files N. The input is N and b, and the output is "yes" if compression is possible or "no" if not. Sample inputs and outputs are provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Best Compression Ever - Kattis, Kattis

    Uploaded by

    Ye
    39 views3 pages
    This document describes a problem that asks whether it is possible to compress a collection of random bit strings, each 1000 bits long, into files of at most b bits given the number of files N. The input is N and b, and the output is "yes" if compression is possible or "no" if not. Sample inputs and outputs are provided.

    Original Title

    Best Compression Ever – Kattis, Kattis

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document describes a problem that asks whether it is possible to compress a collection of random bit strings, each 1000 bits long, into files of at most b bits given the number of files N. The input is N and b, and the output is "yes" if compression is possible or "no" if not. Sample inputs and outputs are provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    39 views3 pages

    Best Compression Ever - Kattis, Kattis

    Uploaded by

    Ye
    This document describes a problem that asks whether it is possible to compress a collection of random bit strings, each 1000 bits long, into files of at most b bits given the number of files N. The input is N and b, and the output is "yes" if compression is possible or "no" if not. Sample inputs and outputs are provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Best Compression Ever – Kattis, Kattis https://open.kattis.

    com/problems/bestcompression

     Due to a performance problem scoring is currently being


    updated slowly. We are working on it!

    Best Compression Ever


    Being educated in Computer Science and Mathematics is not always easy.
    Especially not if you have “friends” who repeatedly insist on showing you
    their new “proofs” that P equals NP, that the Riemann Hypothesis is true,
    and so on.

    One of your friends recently claims to have found a fantastic new


    compression algorithm. As an example of its amazing performance, your
    friend has told you that every �le in your precious collection of random bit
    strings after compression would be at most b bits long! Naturally, you �nd
    this a bit hard to believe, so you want to determine whether it is even
    theoretically possible for this to be true.

    Your collection of random bit strings consists of N �les, no two of which


    are identical, and each of which is exactly 1000 bits long.

    Input

    The input consists of two integers N (1 ≤ N ≤ 1015) and b (0 ≤ b ≤ 50),


    giving the number of �les in your collection and the maximum number of
    bits a compressed �le is allowed to have.

    Output

    Output a line containing either “yes” if it is possible to compress all the N


    �les in your collection into �les of size at most b bits, or “no” otherwise.

    Sample Input 1 Sample Output 1

    13 3 yes

    1 of 3 31/03/2023, 06:07
    Best Compression Ever – Kattis, Kattis https://open.kattis.com/problems/bestcompression

    Sample Input 2 Sample Output 2

    1 0 yes

    Sample Input 3 Sample Output 3

    31415926535897 40 no

    2 of 3 31/03/2023, 06:07
    Best Compression Ever – Kattis, Kattis https://open.kattis.com/problems/bestcompression

    CPU Time limit 1 second

    Memory limit 1024 MB

    Erfiðleiki 2.4 Easy

    Authors Per Austrin and Gunnar Kreitz

    Feng ið frá Nordic Collegiate Programming Contest (NCPC) 2008

    Leyfi

    3 of 3 31/03/2023, 06:07

    You might also like