Home » 國際競賽 » Details

USACO 2019 US Open Contest, Platinum Problem 1. Tree Boxes

Category: 國際競賽, 計(jì)算機(jī)國際競賽 Date: 2019年5月17日下午6:32

Farmer John is planning to build? $N$ ?( $1 \leq N \leq 10^{5}$ ) farms that will be connected by? $N ? 1$ ?roads, forming a tree. Typically, whenever one of his farms is having an issue he is not told the specific farm that is having an issue. Instead, he is told that one of the farms along the path from some farm? $A$ ?to another farm? $B$ ?is having an issue. This is often confusing for Farmer John, as he usually drives offroad tractors and isn't familiar with the road system.

Farmer John considers the location of a farm to be a 2D point. He would prefer to be told that there is a problem in one of the farms in a specified axis-aligned rectangular box. This way Farmer John can decide for himself how to navigate between the farms. Bessie told him that this is a little too ambitious, so he will be satisfied if he is notified with at most two axis-aligned rectangular boxes whose intersection (of farms) is empty and whose union is exactly the farms along the path from? $A$ ?to? $B$ . You must help Farmer John determine where he should build his farms such that this condition is satisfied.

This is an interactive problem, you will not be using standard (or file) I/O.?Solutions that use standard (or file) I/O will be disqualified.?However, you ARE ALLOWED to use global and static variables. You must implement the following functions to help Farmer John:

void addRoad(int A, int B): processes a road between farms? $A$ ?and? $B$ ?( $0 \leq A, B \leq N ? 1$ ).
void buildFarms(): determines where Farmer John should build all his farms.
void notifyFJ(int A, int B): notifies Farmer John with either one or two boxes that satisfy the aforementioned conditions.

Your implementation of the above functions will be able to call the functions given below. You may assume that? $notifyFJ$ ?will be called? $Q$ ?times ( $1 \leq Q \leq 10^{5}$ ).

int getN(): gets the value of? $N$ .
int getQ(): gets the value of? $Q$ .
void setFarmLocation(int ID, int X, int Y): determines that Farmer John should build farm? $I D$ ?( $0 \leq I D \leq N ? 1$ ) at location? $(X, Y)$ ?where? $(1 \leq X, Y \leq N)$ . Should only be called from? $buildFarms$ .
void addBox(int X1, int Y1, int X2, int Y2): adds a box to notify Farmer John where? $(1 \leq X 1 \leq X 2 \leq N)$ ?and? $(1 \leq Y 1 \leq Y 2 \leq N)$ . Should only be called from? $notifyFJ$ .

The interactive protocol works as follows. First,? $addRoad$ ?will be called? $N ? 1$ ?times, to inform your program of the road system. Then,? $buildFarms$ ?will be called and you must determine where Farmer John should build each farm and call? $setFarmLocation$ for every farm accordingly. Finally, there will be? $Q$ ?calls to? $notifyFJ$ ?where you must make either one or two calls to? $addBox$ ?to notify Farmer John.

It is guaranteed there is always a valid way to notify Farmer John using either one or two boxes. The memory limit for this problem is set to 512MB, above the usual 256MB limit.

For a C++ solution, use this template:

#include "grader.h"

void addRoad(int a, int b){
	// Fill in code here
}

void buildFarms(){
	// Fill in code here
}

void notifyFJ(int a, int b){
	// Fill in code here
}

For a Java solution, use this template:

import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {

  	// Copy this exactly:
        
@Override
  	public static void main(String args[]) throws IOException { new boxes().run(); }

        
@Override
  	public void addRoad(int a, int b) {
      // Fill in code here
  	}
        
@Override
  	public void buildFarms(){
      // Fill in code here
	  }
  	
@Override
  	public void notifyFJ(int a, int b){
      // Fill in code here
  	}
}

Sample Interaction

Grader calls? $addRoad(0,1)$

Grader calls? $addRoad(1,2)$

Grader calls? $buildFarms()$

Solution calls? $setFarmLocation(0,1,1)$

Solution calls? $setFarmLocation(1,1,2)$

Solution calls? $setFarmLocation(2,2,2)$

Solution ends? $buildFarms()$

Grader calls? $notifyFJ(0,0)$

Solution calls? $addBox(1,1,1,1)$

Solution ends? $notifyFJ(0,0)$

Grader calls? $notifyFJ(0,2)$

Solution calls? $addBox(1,1,1,2)$

Solution calls? $addBox(2,2,2,2)$

Solution ends? $notifyFJ(0,2)$

Grader terminates, and solution passes test-case

(Note: if you do not pass the first test case, the grader will indicate this as usual. However, note that the short sample interaction above does not correspond to the first test case or any other).

Problem credits: Spencer Compton

中文版

Farmer John計(jì)劃建造 $N$ （ $1 \leq N \leq 10^{5}$ ）個(gè)農(nóng)場，由 $N ? 1$ 條道路連通，構(gòu)成一棵樹。通常，當(dāng)他的一個(gè)農(nóng)場出現(xiàn)問題時(shí)，他不會(huì)被告知具體出現(xiàn)了問題的農(nóng)場。取而代之的是，他會(huì)被告知從某個(gè)農(nóng)場 $A$ 到某個(gè)農(nóng)場 $B$ 的路徑上的農(nóng)場之一出現(xiàn)了問題。這經(jīng)常使Farmer John感到困惑，因?yàn)樗綍r(shí)都駕駛越野拖拉機(jī)，所以對道路系統(tǒng)并不熟悉。

Farmer John將農(nóng)場的位置視為二維坐標(biāo)系中的點(diǎn)。他更希望被告知出現(xiàn)問題的是某個(gè)四邊平行于坐標(biāo)軸的長方形區(qū)域中的某個(gè)農(nóng)場。這樣Farmer John就可以自己決定如何在農(nóng)場之間通行。Bessie告訴他這有些太困難了，所以只要他被告知兩個(gè)不包含相同農(nóng)場并且總共包含了沿 $A$ 到 $B$ 路徑上的所有農(nóng)場的四邊與坐標(biāo)軸平行的長方形，他就滿意了。你需要幫助Farmer John決定他應(yīng)當(dāng)建造他的農(nóng)場的位置，使得這一條件被滿足。

這是一道交互題，你不可以使用標(biāo)準(zhǔn)（或文件）輸入輸出。?使用標(biāo)準(zhǔn)（或文件）輸入輸出的程序?qū)?huì)被取消成績。?然而，你可以使用全局或是靜態(tài)變量。為了幫助Farmer John，你需要實(shí)現(xiàn)如下函數(shù)：

void addRoad(int A, int B)：處理一條建造在農(nóng)場 $A$ 和 $B$ 之間的道路（ $0 \leq A, B \leq N ? 1$ ）。
void buildFarms()：確定Farmer John需要建造所有農(nóng)場的位置。
void notifyFJ(int A, int B)：告知Farmer John滿足前述條件的一個(gè)或兩個(gè)長方形。

你對上述函數(shù)的實(shí)現(xiàn)中可以調(diào)用下面給出的函數(shù)。假設(shè) $notifyFJ$ 會(huì)被調(diào)用 $Q$ 次。

int getN()：獲得 $N$ 的值。
int getQ()：獲得 $Q$ 的值。
void setFarmLocation(int ID, int X, int Y)：決定Farmer John應(yīng)當(dāng)將農(nóng)場 $I D$ （ $0 \leq I D \leq N ? 1$ ）建造在位置 $(X, Y)$ ，其中 $1 \leq X, Y \leq 10^{5} 。應(yīng) 當(dāng) 僅被$ texttt{buildFarms}$調(diào)用。
void addBox(int X1, int Y1, int X2, int Y2)：增加一個(gè)告知Farmer John的長方形，其中 $1 \leq X 1 \leq X 2 \leq 10^{5}$ ，? $1 \leq Y 1 \leq Y 2 \leq 10^{5}$ 。應(yīng)當(dāng)僅被 $notifyFJ$ 調(diào)用。

交互方式如下。首先， $addRoad$ 會(huì)被調(diào)用 $N ? 1$ 次，用來告知你的程序道路系統(tǒng)。接下來， $buildFarms$ 會(huì)被調(diào)用，你需要確定Farmer John需要建造每個(gè)農(nóng)場的位置，并且相應(yīng)地為每個(gè)農(nóng)場調(diào)用 $setFarmLocation$ 。最后，會(huì)有 $Q$ 次對 $notifyFJ$ 的調(diào)用，在每次調(diào)用中你必須調(diào)用一次或兩次 $addBox$ 來告知Farmer John。

保證始終存在一種符合條件的方式可以使用一個(gè)或兩個(gè)長方形來告知Farmer John。這個(gè)問題的運(yùn)行內(nèi)存限制為512MB，超過一般問題所給的256MB內(nèi)存限制。

C++的程序請使用下面的模板：

#include "grader.h"

void addRoad(int a, int b){
    // Fill in code here
}

void buildFarms(){
    // Fill in code here
}

void notifyFJ(int a, int b){
    // Fill in code here
}

Java的程序請使用下面的模板：

import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {

    // Copy this exactly:
        
Override
    public static void main(String args[]) throws IOException { new boxes().run(); }

        
Override
    public void addRoad(int a, int b) {
      // Fill in code here
    }
        
Override
    public void buildFarms(){
      // Fill in code here
    }
    
Override
    public void notifyFJ(int a, int b){
      // Fill in code here
    }
}

交互樣例：

評測機(jī)調(diào)用 $addRoad(0,1)$

評測機(jī)調(diào)用 $addRoad(1,2)$

評測機(jī)調(diào)用 $buildFarms()$

選手程序調(diào)用 $setFarmLocation(0,1,1)$

選手程序調(diào)用 $setFarmLocation(1,1,2)$

選手程序調(diào)用 $setFarmLocation(2,2,2)$

選手程序結(jié)束 $buildFarms()$

評測機(jī)調(diào)用 $notifyFJ(0,0)$

選手程序調(diào)用 $addBox(1,1,1,1)$

選手程序結(jié)束 $notifyFJ(0,0)$

評測機(jī)調(diào)用 $notifyFJ(0,2)$