Articles tagged as
USACO

  1. [USACO] Ordered Fractions

    OI algorithm USACO

    Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

    Here is the set when N = 5: :

    0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

    Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

    PROGRAM NAME: frac1

    INPUT FORMAT

    One line with a single integer N.

    OUTPUT FORMAT

    One fraction per line, sorted in order of magnitude.

    SOLUTION

    这是一道很好过的题目。我的方法是穷举所有可能的分数，然后排序后输出。就这种最直观最笨的方法也不会超时。代码很好写，这里就略去了。

    下面是我在usaco的官方Analysis上看到的解法，它利用递归直接生成分数并输出，没有互质数判断，没有排序。真是非常漂亮——虽然其中数学原理我还是有点搞不懂。比如：它怎么保证每次得到的分数分子分母都互质的？两个分数分子分母分别相加的到的分数，为什么它的值一定介于两者之间？希望能有达人仔细解释。

    下面是我翻译自usaco的：

    下面是来自Russ的超快解法：

    我们发现可以把0/1和1/1分别作为起点和终点，然后通过增大分子和分母来递归地生成中间的点。

    0/1                                                             1/1
                                1/2
                  1/3                       2/3
        1/4              2/5          3/5              3/4
    1/5      2/7     3/8    3/7    4/7   5/8     5/7        4/5

    每个分数都是由它左边和右边的分数生成的。这种想法有助于在递归过深时跳出。

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int n;
FILE *fout;

/* 打印在n1/d1和n2/d2之间且分母小于等于n的分数*/
void
genfrac(int n1, int d1, int n2, int d2)
{
  if(d1+d2 > n)  /*跳出递归*/
  return;

  genfrac(n1,d1, n1+n2,d1+d2);
  fprintf(fout, "%d/%d\n ...
    Read more

  2. [USACO] The Clocks

    OI algorithm USACO

    Consider nine clocks arranged in a 3×3 array thusly:

    |-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

    The goal is to find a minimal sequence of moves to return all the dials to 12 o’clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

    Move Affected clocks
    1 ABDE
    2 ABC
    3 BCEF
    4 ADG
    5 BDEFH
    6 CFI
    7 DEGH
    8 GHI
    9 EFHI

    EXAMPLE

    Each number represents a time accoring to following table:

    9 9 12          9 12 12       9 12 12        12 12 12         12 12 12
6 6 6   5 ->    9  9  9   8-> 9  9  9   4 -> 12  9  9   9 ->  12 12 12
6 3 6           6  6  6       9  9  9        12  9  9         12 12 12

    [But this might or might not be the `correct’ answer; see below.]

    PROGRAM NAME: clocks

    INPUT FORMAT

    Line1:

    Three lines of three space-separated numbers ...

    Read more

  3. [USACO] Mixing Milk

    OI algorithm USACO

    Since milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the cheapest possible manner.

    The Merry Milk Makers company has several farmers from which they may buy milk, and each one has a (potentially) different price at which they sell to the milk packing plant. Moreover, as a cow can only produce so much milk a day, the farmers only have so much milk to sell per day. Each day, Merry Milk Makers can purchase an integral amount of milk from each farmer, less than or equal to the farmer’s limit.

    Given the Merry Milk Makers’ daily requirement of milk, along with the cost per gallon and amount of available milk for each farmer, calculate the minimum amount of money that it takes to fulfill the Merry Milk Makers’ requirements.

    Note: The total milk produced per day by the farmers will be sufficient to meet the demands of the Merry Milk Makers.

    PROGRAM NAME: milk

    INPUT FORMAT

    Line1:

    Two integers, N and M.

    The first value, N, (0 <= N <= 2,000,000) is the ...

    Read more

  4. [USACO] Milking Cows / [Vijos1165] 火烧赤壁

    OI algorithm USACO

    Milking Cows

    Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200). Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):

    • The longest time interval at least one cow was milked.
    • The longest time interval (after milking starts) during which no cows were being milked.

    PROGRAM NAME: milk2

    INPUT FORMAT

    Line1: The single integer
    Lines2..N+ 1: Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500

    OUTPUT FORMAT

    A single line with two integers that represent the longest ...

    Read more

Page 1 / 1