Exchange Rates
Your job is to write a program that, given a list of exchange rates, calculates the exchange rate between any two items.
Input
The input file contains one or more commands, followed by a line beginning with a period that signals the end of the file. Each command is on a line by itself and is either an assertion or a query. An assertion begins with an exclamation point and has the format
! m itema = n itemb where itema and itemb are distinct item names and m and n are both positive integers less than 100. This command says that m of itema are worth n of itemb. A query begins with a question mark, is of the form ? itema = itemb and asks for the exchange rate between itema and itemb, where itema and itemb are distinct items that have both appeared in previous assertions (although not necessarily the same assertion).
Output
For each query, output the exchange rate between itema and itemb based on all the assertions made up to that point. Exchange rates must be in integers and must be reduced to lowest terms. If no exchange rate can be determined at that point, use question marks instead of integers. Format all output exactly as shown in the example. Note:
>Item names will have length at most 20 and will contain only lowercase letters. >Only the singular form of an item name will be used (no plurals). >There will be at most 60 distinct items. >There will be at most one assertion for any pair of distinct items. >There will be no contradictory assertions. For example, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig"are contradictory. >Assertions are not necessarily in lowest terms, but output must be. >Although assertions use numbers less than 100, queries may result in larger numbers that will not exceed 10000 when reduced to lowest terms.
Sample Input
! 6 shirt = 15 sock ! 47 underwear = 9 pant ? sock = shirt ? shirt = pant ! 2 sock = 1 underwear ? pant = shirt .
Sample Output 5 sock = 2 shirt
? shirt = ? pant
45 pant = 188 shirt
원문:http://accepted.com.cn/zoj1705/
코드는 원문의 코드만 번역할 뿐, 검색으로 시작하여 왜 안 되는지 모르겠다. 이 문제는 채택되었다
부모 노드를 합친 형식과 유사하게 구체적인 계산은 스스로 이해해야 한다.
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 1005;
int u, v, father[maxn][3], cnt;
string name[maxn], name1, name2;
int find ( string str )
{
for ( int i = 0; i < cnt; i ++ ) // str
if ( str == name[i] )
return i;
return -1;
}
template < class T >
void Swap ( T &a, T &b ) //
{
T t = a;
a = b;
b = t;
}
int GCD ( int a, int b ) //
{
if ( a < b )
Swap ( a, b );
while ( a%b )
{
int t = a%b;
a = b;
b = t;
}
return b;
}
int solve ( int pos, int & v1, int & v1a )
{
int a = father[pos][1], b = father[pos][2], v2, v2a;
if ( father[pos][0] == pos ) //
{
v1 = 1;
v1a = 1;
return pos; // , ( )
}
father[pos][0] = solve ( father[pos][0], v2, v2a );
father[pos][1] = v2*a; //
father[pos][2] = v2a*b;
v1 = father[pos][1];
v1a = father[pos][2];
int gcd = GCD ( v1, v1a ); //
father[pos][1] = father[pos][1]/gcd, father[pos][2] = father[pos][2]/gcd;
return father[pos][0];
}
void deal ( )
{
int x, y, pos, gcd;
x = find ( name1 );
y = find ( name2 );
gcd = GCD ( u, v );
u = u/gcd;
v = v/gcd;
//printf ( "%d %d
", x, y );
if ( x != -1 && y != -1 )
{
int v1, v1a, v2, v2a;
int sx = solve ( x, v1, v1a );
int sy = solve ( y, v2, v2a );
//printf ( "**%d %d %d %d
", v1, v1a, v2, v2a );
father[sx][0] = sy;
father[sx][1] = v2*v1a*v; //1 sx->sy
father[sx][2] = v1*v2a*u; //2 sy->sx
gcd = GCD ( father[sx][1], father[sx][2] );
father[sx][1] = father[sx][1]/gcd, father[sx][2] = father[sx][2]/gcd;
}
if ( x != -1 && y == -1 )
{
Swap ( u, v ); // x -1
Swap ( x, y );
Swap ( name1, name2 );
}
if ( y == -1 )
{
y = cnt ++; // name2
name[y] = name2;
father[y][0] = y;
father[y][1] = father[y][2] = 1;
}
x = cnt ++;
name[x] = name1;
father[x][0] = y;
father[x][1] = v; //y
father[x][2] = u;
}
void query ( )
{
int x, y, sx, sy, v1, v1a, v2, v2a;
x = find ( name1 );
y = find ( name2 );
sx = solve ( x, v1, v1a );
sy = solve ( y, v2, v2a );
if ( sx != sy )
cout << "? " << name1 << " = ? " << name2 << endl;
else
{
int ans1 = v2*v1a; //
int ans2 = v1*v2a;
int gcd = GCD ( ans1, ans2 );
cout << ans1/gcd << " " << name1 << " = " << ans2/gcd
<< " " << name2 << endl;
}
}
int main ( )
{
string op, eq;
while ( cin >> op && op[0] != '.' )
{
if ( op[0] == '!' )
{
cin >> u >> name1 >> eq >> v >> name2;
deal ( );
}
else
{
cin >> name1 >> eq >> name2;
query ( );
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.