#include<cstdio> #include<queue> using namespace std; priority_queue<int, vector<int>, greater<int> >q; typedef long long ll; ll ans; int main() { int n, t; while(scanf("%d", &n), n) { for(int i = 0; i < n; ++i) { scanf("%d", &t); q.push(t); }
ans = 0; while(!q.empty()) { int a = q.top(); q.pop(); int b = q.top(); q.pop(); ans += (a + b); if(q.empty()) break; q.push(a + b); } printf("%lld\n", ans); } return0; }
Yup!! The problem name reflects your task; just add a set of numbers. But you may feel yourselves condescended, to write a C/C++ program just to add a set of numbers. Such a problem will simply question your erudition. So, let’s add some flavor of ingenuity to it.
Addition operation requires cost now, and the cost is the summation of those two to be added. So, to add 1 and 10, you need a cost of11. If you want to add 1, 2 and 3. There are several ways –
1 + 2 = 3, cost = 3
3 + 3 = 6, cost = 6
Total = 9
1 + 3 = 4, cost = 4
2 + 4 = 6, cost = 6
Total = 10
2 + 3 = 5, cost = 5
1 + 5 = 6, cost = 6
Total = 11
I hope you have understood already your mission, to add a set of integers so that the cost is minimal.
Input
Each test case will start with a positive number, N (2 ≤ N ≤ 5000) followed by N positive integers (all are less than 100000). Input is terminated by a case where the value of N is zero. This case should not be processed.
Output
For each case print the minimum total cost of addition in a single line.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 300; int mat[N][N], des[N], d[N], ans, n, m;
voidprim() { memset(d, 0x3f, sizeof(d)); int s = 0; while(des[s]) ++s; d[s] = -1; int cur = s, next = n; for(int k = 1; k < n - m; ++k) { for(int i = 0; i < n; ++i) { if(des[i] || d[i] < 0) continue; d[i] = min(d[i], mat[cur][i]); if(d[i] < d[next]) next = i; } ans += d[next], d[next] = -1, cur = next, next = n; } }
int main() { int cas, l, e1, e2, a, b, c; scanf("%d", &cas); while(cas--) { memset(mat, 0x3f, sizeof(mat)); memset(des, 0, sizeof(des)); scanf("%d %d", &l, &e1); for(int i = 0; i < e1; ++i) { scanf("%d%d%d", &a, &b, &c); if(c < mat[a][b]) mat[a][b] = mat[b][a] = c; }
n = n + l; scanf("%d", &m); for(int i = 0; i < m; ++i) { scanf("%d", &a); des[a] = 1; }
ans = 0; prim(); if(ans < d[n]) printf("%d\n", ans); elseprintf("what a pity!\n"); } return0; }
The plan of city rebuild
Problem Description
News comes!~City W will be rebuilt with the expectation to become a center city. There are some villages and roads in the city now, however. In order to make the city better, some new villages should be built and some old ones should be destroyed. Then the officers have to make a new plan, now you , as the designer, have the task to judge if the plan is practical, which means there are roads(direct or indirect) between every two villages(of course the village has not be destroyed), if the plan is available, please output the minimum cost, or output”what a pity!”. Input
Input contains an integer T in the first line, which means there are T cases, and then T lines follow. Each case contains three parts. The first part contains two integers l(0<l<100), e1, representing the original number of villages and roads between villages(the range of village is from 0 to l-1), then follows e1 lines, each line contains three integers a, b, c (0<=a, b<l, 0<=c<=1000), a, b indicating the village numbers and c indicating the road cost of village a and village b . The second part first contains an integer n(0<n<100), e2, representing the number of new villages and roads(the range of village is from l to l+n-1), then follows e2 lines, each line contains three integers x, y, z (0<=x, y<l+n, 0<=z<=1000), x, y indicating the village numbers and z indicating the road cost of village x and village y. The third part contains an integer m(0<m<l+n), representing the number of deserted villages, next line comes m integers, p1,p2,…,pm,(0<=p1,p2,…,pm<l+n) indicating the village number. Pay attention: if one village is deserted, the roads connected are deserted, too. Output
For each test case, If all villages can connect with each other(direct or indirect), output the minimum cost, or output “what a pity!”. Sample Input
#include<cstdio> #include<cstring> using namespace std; const int N = 30, M = 100010; struct edge{int u, v; } e[M]; int vis[N], in[N], out[N], par[N], m, ok;
int Find(int x) { int r = x, tmp; while(par[r] >= 0) r = par[r]; while(x != r) { tmp = par[x]; par[x] = r; x = tmp; } return r; }
voidconnect() { memset(par, -1, sizeof(par)); //初始化并查集 for(int i = 0; i < m; ++i) { int u = e[i].u, v = e[i].v; if(Find(u) != Find(v)) Union(u, v); } for(int i = 0; i < 26; ++i) for(int j = 0; j < 26; ++j) if(vis[i] && vis[j] && Find(i) != Find(j)) ok = 0; }
int main() { char s[1005]; int u, v, cas; scanf("%d", &cas); while(cas--) { for(int i = 0; i < 26; ++i) vis[i] = in[i] = out[i] = 0; scanf("%d", &m); for(int i = 0; i < m; ++i) { scanf("%s", s); u = s[0] - 'a', v = s[strlen(s) - 1] - 'a'; vis[u] = vis[v] = 1; e[i].u = u, e[i].v = v; ++in[u], ++out[v]; }
int id = 0, od = 0;//i[d]记录入度比出度大1的点的个数 o[d]小1 ok = 1; for(int i = 0; i < 26; ++i) { if(!vis[i]) continue; int k = in[i] - out[i]; if(k < -1 || k > 1) {ok = 0; break;} if(k == 1) ++id; if(k == -1) ++od; } if(id > 1 || od > 1 || id - od) ok = 0; connect(); if(ok) printf("Ordering is possible.\n"); elseprintf("The door cannot be opened.\n"); } return0; }
Description You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc…). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and closing the doors behind you. Your biggest problem is determining whether it is possible to find a path through the sloppy rooms where you: Always shut open doors behind you immediately after passing through Never open a closed door End up in your chambers (room 0) with all doors closed In this problem, you are given a list of rooms and open doors between them (along with a starting room). It is not needed to determine a route, only if one is possible.
Input
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. A single data set has 3 components: Start line - A single line, “START M N”, where M indicates the butler’s starting room, and N indicates the number of rooms in the house (1 <= N <= 20). Room list - A series of N lines. Each line lists, for a single room, every open door that leads to a room of higher number. For example, if room 3 had open doors to rooms 1, 5, and 7, the line for room 3 would read “5 7”. The first line in the list represents room 0. The second line represents room 1, and so on until the last line, which represents room (N - 1). It is possible for lines to be empty (in particular, the last line will always be empty since it is the highest numbered room). On each line, the adjacent rooms are always listed in ascending order. It is possible for rooms to be connected by multiple doors! End line - A single line, “END” Following the final data set will be a single line, “ENDOFINPUT”. Note that there will be no more than 100 doors in any single data set.
Output
For each data set, there will be exactly one line of output. If it is possible for the butler (by following the rules in the introduction) to walk into his chambers and close the final open door behind him, print a line “YES X”, where X is the number of doors he closed. Otherwise, print “NO”.
#include <cstdio> #include <algorithm> using namespace std; const int N = 1005; int n, a[N]; int d[N], c[N], cas, ans;
int main() { scanf("%d", &cas); while (cas--) { scanf("%d", &n); int sum = ans = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); d[i] = 1, c[i] = 1; for (int j = 1; j < i; ++j) { if (a[j] >= a[i]) continue; if (d[j] + 1 > d[i]) { d[i] = d[j] + 1; c[i] = c[j]; } elseif (d[j] + 1 == d[i]) c[i] = 2; } if(d[i] > ans) ans = d[i]; } for (int i = 1; i <= n; ++i) if (d[i] == ans) sum += c[i]; printf("%d\n", sum > 1 ? ans : ans - 1); } return0; }
Revenge of LIS II
Problem Description
In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. —Wikipedia Today, LIS takes revenge on you, again. You mission is not calculating the length of longest increasing subsequence, but the length of the second longest increasing subsequence. Two subsequence is different if and only they have different length, or have at least one different element index in the same place. And second longest increasing subsequence of sequence S indicates the second largest one while sorting all the increasing subsequences of S by its length. Input
The first line contains a single integer T, indicating the number of test cases. Each test case begins with an integer N, indicating the length of the sequence. Then N integer Ai follows, indicating the sequence. [Technical Specification]
1 <= T <= 100
2 <= N <= 1000
1 <= Ai <= 1 000 000 000 Output
For each test case, output the length of the second longest increasing subsequence. Sample Input
3 2 1 1 4 1 2 3 4 5 1 1 2 2 2 Sample Output
1 3 2
HintFor the first sequence, there are two increasing subsequence: [1], [1]. So the length of the second longest increasing subsequence is also 1, same with the length of LIS.
int main() { int cas=0; while(scanf("%d",&n),n) { memset(d,0x3f,sizeof(d)); for(int i=1;i<=n;++i) { scanf("%d%d",&x[i],&y[i]); for(int j=1;j<i;++j) { int tx=x[i]-x[j],ty=y[i]-y[j]; d[i][j]=d[j][i]=sqrt(tx*tx+ty*ty); } } floyd(); printf("Scenario #%d\nFrog Distance = %.3f\n\n",++cas,d[1][2]); } return0; }
Frogger
Description Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence. The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones. You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.
Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone /#i. Stone /#1 is Freddy’s stone, stone /#2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying “Scenario /#x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
#include<cstdio> #include<cstring> using namespace std; const int N = 205; int d[N][N], n;
voidfloyd() { for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) d[i][j] |= (d[i][k] & d[k][j]);
}
int main() { int a, b; char s[30]; while(scanf("%d", &n), n) { memset(d, 0, sizeof(d)); while(scanf("%d%d", &a, &b), a) { scanf("%s", s); for(int i = 0; s[i] != '\0'; ++i) d[a][b] = d[a][b] | (1 << s[i] - 'a'); } floyd(); while(scanf("%d%d", &a, &b), a) { for(char c = 'a'; c <= 'z'; ++c) if(d[a][b] & (1 << c - 'a')) printf("%c", c); if(d[a][b] == 0) printf("-"); printf("\n"); } printf("\n"); } return0; }
Fiber Network
Description Several startup companies have decided to build a better Internet, called the “FiberNet”. They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes. Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.
Input
The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, …, n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters. After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.
Output
For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output “-“ instead. Output a blank line after each test case.
Sample Input
3 1 2 abc 2 3 ad 1 3 b 3 1 de 0 0 1 3 2 1 3 2 0 0 2 1 2 z 0 0 1 2 2 1 0 0 0
for(int i = 1; i <= n; ++i) scanf("%d", &tax[i]); floyd(); while(scanf("%d%d", &s, &t), s > 0) { int k=s; printf("From %d to %d :\nPath: %d", s, t, s); while(k!=t) printf("-->%d", k=nex[k][t]); printf("\nTotal cost : %d\n\n", cost[s][t]); } } return0; }
Minimum Transport Cost
Problem Description
These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts: The cost of the transportation on the path between these cities, and a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities. You must write a program to find the route which has the minimum cost. Input
First is N, number of cities. N = 0 indicates the end of input. The data of path cost, city tax, source and destination cities are given in the input, which is of the form: a11 a12 … a1N a21 a22 … a2N …………… aN1 aN2 … aNN b1 b2 … bN c d e f … g h where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, …, and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form: Output
From c to d : Path: c–>c1–>……–>ck–>d Total cost : …… …… From e to f : Path: e–>e1–>……….–>ek–>f Total cost : …… Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case. Sample Input
#include<cstdio> #include<cstring> #include<string> #include<map> using namespace std; map<string, int> na; const int N = 31; double d[N], rate[N][N], r; int n, m, ans;
int main() { int cas = 0; char s[100], a[100], b[100]; while(scanf("%d", &n), n) { na.clear(); ans = 0; memset(rate, 0, sizeof(rate)); for(int i = 1; i <= n; ++i) { rate[i][i] = 1.0; scanf("%s", s); na[s] = i; }
scanf("%d", &m); for(int i = 1; i <= m; ++i) { scanf("%s%lf%s", a, &r, b); rate[na[a]][na[b]] = r; }
for(int i = 1; i <= n; ++i) { if(bellman(i)) { ans = 1; break; } } printf("Case %d: %s\n", ++cas, ans ? "Yes" : "No"); } return0; }
Arbitrage
Description Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 /* 10.0 /* 0.21 = 1.05 US dollars, making a profit of 5 percent. Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input
The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format “Case case: Yes” respectively “Case case: No”.
