ZOJ 3328 WuXing
テーマリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3328
タイトル:
Wu Xing
Time Limit: 1セット
メモリLimit: 32768 KB
Introduction
The Wu Xing、or the Five Movements、Five Pases or Five Step/Stags、are chiefly an ancint mnemonic device、in many trational Chinese fields.
The doctrine of five phass describes two cycles、a generation or creation cycle、also known as「mother-son」、and an overcorn or destruction cycle、also known as「grand far-nephew」、of interew.ine.ination.ine.
Generating: Wood feeds Fire; Fire creates Earth(sh); Earth bears Metal; Metal carries Water(as in a bucket or tap、or water condenses on metal); Water nourishes Wood. Overcomping: Wood parts Earth(such as roots)(or Trees can prevent soil erossion); Earth absorbs(or muddies)Water(or Earth dam control the water); Water quenches Fire; Fire melts Metal; Metal chocps Wood.
With the two types of interactions in the above graph,any two nodes are connected by an edge.
Problem
In graph with N nodes、to ensure that any two nodes are connected by at least one edge、how many types of interactions are required at least?Here a type of interaction shoud have the follwing properties: It can be represented as a set of directed edges in the grapph. For each type of interaction、there Shound be one and onlyone edge starting ah node. For each type of interaction,there shoud be one and onlyone edge ending at each node. The interactions are made up of cycles,i.e.starting from an arbitrry node and follwing the edges with the same type of interaction,you can always reach the starting node after several steps. Input
For each test case,there's a line with an integer N (3<= N < 1,000,000)、the number of nodes in the graph.
N
= 0 indicates the end of input.
Output
For each test case、output a line with the number of interactions that are required at least.
Sample Input
http://en.wikipedia.org/wiki/Wu_Xing
件名:
何種類の丸関係を使うと、どちらの両側でも直接に一本の端に繋げることができます.
問題を解く:
最初にこのような問題を見たら、目眩がしますよね.問題をよく読んだら、問題は簡単です.どのような丸関係が必要ですか?例えば、1つの点と他の2つの点との関係を作ることができます.したがって、必要な関係数はn/2となる.
コード:
タイトル:
Wu Xing
Time Limit: 1セット
メモリLimit: 32768 KB
Introduction
The Wu Xing、or the Five Movements、Five Pases or Five Step/Stags、are chiefly an ancint mnemonic device、in many trational Chinese fields.
The doctrine of five phass describes two cycles、a generation or creation cycle、also known as「mother-son」、and an overcorn or destruction cycle、also known as「grand far-nephew」、of interew.ine.ination.ine.
Generating:
With the two types of interactions in the above graph,any two nodes are connected by an edge.
Problem
In graph with N nodes、to ensure that any two nodes are connected by at least one edge、how many types of interactions are required at least?Here a type of interaction shoud have the follwing properties:
For each test case,there's a line with an integer N (3<= N < 1,000,000)、the number of nodes in the graph.
N
= 0 indicates the end of input.
Output
For each test case、output a line with the number of interactions that are required at least.
Sample Input
5
0
Sample Output2
Referencehttp://en.wikipedia.org/wiki/Wu_Xing
件名:
何種類の丸関係を使うと、どちらの両側でも直接に一本の端に繋げることができます.
問題を解く:
最初にこのような問題を見たら、目眩がしますよね.問題をよく読んだら、問題は簡単です.どのような丸関係が必要ですか?例えば、1つの点と他の2つの点との関係を作ることができます.したがって、必要な関係数はn/2となる.
コード:
#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n&&n)
{
cout<<n/2<<endl;
}
}