Home » 国际竞赛 » Details

USACO 2020 December Contest, Bronze Problem 2. Daisy Chains

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午3:43

USACO 2020 December Contest, Bronze Problem 2. Daisy Chains

Every day, as part of her walk around the farm, Bessie the cow visits her favorite pasture, which has $N$ flowers (all colorful daisies) labeled $1 \dots N$ lined up in a row $(1 \leq N \leq 100)$ . Flower $i$ has $p_{i}$ petals $(1 \leq p_{i} \leq 1000)$ .

As a budding photographer, Bessie decides to take several photos of these flowers. In particular, for every pair of flowers $(i, j)$ satisfying $1 \leq i \leq j \leq N$ , Bessie takes a photo of all flowers from flower $i$ to flower $j$ (including $i$ and $j$ ).

Bessie later looks at these photos and notices that some of these photos have an "average flower" -- a flower that has $P$ petals, where $P$ is the exact average number of petals among all flowers in the photo.

How many of Bessie's photos have an average flower?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains $N$ . The second line contains $N$ space-separated integers $p_{1} \dots p_{N}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Please print out the number of photos that have an average flower.

SAMPLE INPUT:

4
1 1 2 3

SAMPLE OUTPUT:

Every picture containing just a single flower contributes to the count (there are four of these in the example). Also, the $(i, j)$ ranges $(1, 2)$ and $(2, 4)$ in this example correspond to pictures that have an average flower.

Problem credits: Nick Wu

USACO 2020 December Contest, Bronze Problem 2. Daisy Chains 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Nick Wu)

The most direct solution involves taking each photo and then checking every flower in that photo for an average flower.

There are $O (N^{2})$ photos, and checking each flower in the photo takes $O (N)$ , so this solution runs in $O (N^{3})$ time.

Code is as follows.

import java.io.*;
import java.util.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int n = Integer.parseInt(br.readLine());
    int[] petals = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i = 0; i < n; i++) {
      petals[i] = Integer.parseInt(st.nextToken());
    }
    int photos = 0;
    for(int i = 0; i < n; i++) {
      for(int j = i; j < n; j++) {
        int totalPetals = 0;
        for(int k = i; k <= j; k++) {
          totalPetals += petals[k];
        }
        boolean present = false;
        for(int k = i; k <= j; k++) {
          if(petals[k] * (j-i+1) == totalPetals) {
            present = true;
          }
        }
        if(present) {
          photos++;
        }
      }
    }
    pw.println(photos);
    pw.close();
  }
}

It's possible (but not necessary) to optimize this down to $O (N^{2})$ . One observation we can make is that all photos with more than one flower consist of taking a smaller photo and then including the next rightmost flower.

Let us consider processing all photos that use flower $i$ as the leftmost flower, starting by using the photo that contains only flower $i$ and then adding flowers one by one to the right. We can maintain a collection of all the flowers we have seen so far. As we do this, we also need to keep track of the total sum of petals we have seen so far so we know what the average petal count is, and then we can check whether we have seen that petal count before. Because the number of petals is bounded above by $10^{3}$ , we can use a boolean array to track which petal counts we have seen. Alternatively, we can use a set.

import java.io.*;
import java.util.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int n = Integer.parseInt(br.readLine());
    int[] petals = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i = 0; i < n; i++) {
      petals[i] = Integer.parseInt(st.nextToken());
    }
    int photos = 0;
    for(int i = 0; i < n; i++) {
      boolean[] present = new boolean[1001];
      int petalsSeen = 0;
      for(int j = i; j < n; j++) {
        petalsSeen += petals[j];
        present[petals[j]] = true;
        if(petalsSeen % (j-i+1) == 0 && present[petalsSeen / (j-i+1)]) {
          photos++;
        }
      }
    }
    pw.println(photos);
    pw.close();
  }
}

[/hide]