| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 1 | 0 | 0 | 0.000% |
How do setters come up with problems? Sometimes they just take a couple of buzzwords and smash them together. But we are in 2024, so this totally can be outsourced to AI. Introducing our creation based on ChatGPT: RICH B! And its second official problem:
Prompt: Minimum Spanning Tree
Problem: A complete graph with $n$ nodes and $\frac{n \cdot (n - 1)}{2}$ edges is chosen. Each edge is randomly assigned a real-valued weight within the range of $[0, 1]$. Your task is to find its minimum spanning tree. But you are not given the edges. Instead, you can make queries of the form "? $v_1$ $u_1$ $v_2$ $u_2$", and the jury program will respond to you with 1ドル$ if the weight of edge $(v_1, u_1)$ is less than the weight of edge $(v_2, u_2),ドル and it will respond with 0ドル$ if it's not.
When you think that you know the minimum spanning tree, print it as "! $v_1$ $u_1$ $v_2$ $u_2$ $\ldots$ $v_{n - 1}$ $u_{n - 1}$", where edges $(v_i, u_i)$ form the minimum spanning tree. Constraints: 2ドル \le n \le 100,ドル and you can make at most 6000ドル$ queries.
First, read a line that contains a single $n$ (2ドル \le n \le 100$): the size of the graph.
To compare two edges, print a single line in the following format: "? $v_1$ $u_1$ $v_2$ $u_2$". You will then have to read a line with the result of the comparison: 1ドル$ if the weight of the first edge is less than the weight of the second edge, or 0ドル$ otherwise.
To output the answer, print a single line in the following format: "! $v_1$ $u_1$ $v_2$ $u_2$ $\ldots$ $v_{n - 1}$ $u_{n - 1}$". Your program has to immediately terminate after printing this line, otherwise, you may get unpredictable verdicts.
In every line you print, $(v_i, u_i)$ should be pairs of integers where 1ドル \le v < u \le n$), otherwise, you may get unpredictable verdicts.
Your program should not make more than 6000ドル$ comparisons.
3 1 1
? 1 2 1 3 ? 1 3 2 3 ! 1 2 1 3
The Minimum Spanning Tree (MST) of a graph is defined as the graph's spanning tree having the minimum possible total weight.
A spanning tree is a connected subgraph of the given graph that contains all of the graph's vertices and does not contain cycles.
The interactor is not adaptive.
Remember to end the line and flush the output after every line you print. To flush the output, you can use fflush(stdout) in C/C++, System.out.flush() in Java, or sys.stdout.flush() in Python.