#include <cstdio> using namespace std; const int N = 1000005; int a[N]; int main() { int n, k, l, r, le, ri, m; while(~scanf("%d%d", &n, &k)) { for(int i = 0; i < n; ++i) scanf("%d", &a[i]); if(n < k) {puts("-1"); continue;} l = 0, r = n - 1; while(l <= r) { m = a[le = l], ri = r; while(le < ri) { while(le < ri && a[ri] > m) --ri; a[le] = a[ri]; while(le < ri && a[le] < m) ++le; a[ri] = a[le]; } a[le] = m; if(le < k - 1) l = le + 1; else r = le - 1; } printf("%d\n", a[r + 1]); } return0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n, m, cur, cnt, ans, k; while(~scanf("%lld%lld", &n, &m)) { if (n > m) swap(n, m); cur = ans = 1, cnt = 0, k = m; while(cur != k) { cur += n - 1, ans += n - 1 - 2 * cnt; if(cur > k) k += m - 1, ++cnt; } printf("%lld\n", ans); } return0; }
Search for a Hiding-Place
Scooby-Doo is fond of adventures. This time he wanted to find a hiding-place in a vampire castle. After a long search, Scooby ended up in a huge rectangular hall with four entrances, one in each corner, through one of which he had entered. The floor was paved with white square tiles. Scooby thought that the hiding-place was under one of these tiles. He started searching for it by turning the tiles over, the grey side up. He began his search from a corner moving at an angle of 45° to the walls. Each time he came to a wall, he made a 90° turn. If he stepped on a grey tile, he turned it back the white side up. The search went on until Scooby reached an entrance at one of the corners. Then, not having found the hiding-place, the tired dog sighed and went out to have a snack. Given the dimensions of the hall, calculate the total number of tiles that were turned the grey side up at the end of the search.
The only input line contains integers n and m separated with a space. They are the length and width of the hall measured in tiles (2 ≤ n, m ≤ 1 000 000).
In the only line output the number of grey tiles in the hall after Scooby-Doo’s search.
#include <bits/stdc++.h> using namespace std; const int N = 505; char g[N][N]; stack<pair<int, int> > s; int x[] = { -1, 1, 0, 0}; int y[] = {0, 0, -1, 1}; int n, m, a, b, cnt, is_first;
int dfs(int i, int j) { int r, c; if(is_first) is_first = 0; else s.push(make_pair(i, j)); g[i][j] = 'R', cnt += 3; for(int k = 0; k < 4; ++k) { r = i + x[k], c = j + y[k]; if(g[r][c] == '.') dfs(r, c); } }
int main() { while(~scanf("%d%d", &n, &m)) { cnt = 0; for(int i = 1; i <= n; ++i) scanf("%s", g[i] + 1); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(g[i][j] == '.') is_first = 1, cnt -= 2, dfs(i, j); printf("%d\n", cnt); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(g[i][j] != '#') printf("B %d %d\n", i, j);
while(!s.empty()) { a = s.top().first, b = s.top().second; printf("D %d %d\nR %d %d\n", a, b, a, b); s.pop(); } } return0; }
Block Tower
After too much playing on paper, Iahub has switched to computer games. The game he plays is called “Block Towers”. It is played in a rectangular grid with n rows and m columns (it contains n × m cells). The goal of the game is to build your own city. Some cells in the grid are big holes, where Iahub can’t build any building. The rest of cells are empty. In some empty cell Iahub can build exactly one tower of two following types:
Iahub is also allowed to destroy a building from any cell. He can do this operation as much as he wants. After destroying a building, the other buildings are not influenced, and the destroyed cell becomes empty (so Iahub can build a tower in this cell if needed, see the second example for such a case).
Iahub can convince as many population as he wants to come into his city. So he needs to configure his city to allow maximum population possible. Therefore he should find a sequence of operations that builds the city in an optimal way, so that total population limit is as large as possible.
He says he’s the best at this game, but he doesn’t have the optimal solution. Write a program that calculates the optimal one, to show him that he’s not as good as he thinks. Input
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 500). Each of the next n lines contains m characters, describing the grid. The j-th character in the i-th line is ‘.’ if you’re allowed to build at the cell with coordinates (i, j) a tower (empty cell) or ‘/#’ if there is a big hole there.
Output
Print an integer k in the first line (0 ≤ k ≤ 106) — the number of operations Iahub should perform to obtain optimal result.
Each of the following k lines must contain a single operation in the following format:
If there are multiple solutions you can output any of them. Note, that you shouldn’t minimize the number of operations. Sample test(s)
#include <cstdio> #include <algorithm> using namespace std;
const int N = 50005; int p[N], l, n, m;
bool ok(int k) { int last = 0, cnt = 0; for(int i = 1; i < n; ++i) { if(p[i] - p[last] < k) ++cnt; else last = i; } return cnt <= m; }
int main() { int le, ri, mid; while(~scanf("%d%d%d", &l, &n, &m)) { p[++n] = l; for (int i = 1; i < n; ++i) scanf("%d", &p[i]);
sort(p, p + n); le = 0, ri = l; while(le <= ri) { mid = (le + ri) >> 1; if(ok(mid)) le = mid + 1; else ri = mid - 1; } printf("%d\n", le - 1); } return0; }
River Hopscotch
Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤N ≤ 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).
To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.
Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to Mrocks (0 ≤ M ≤ N).
FJ wants to know exactly how much he can increase the shortest distance /before/ he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.
Input
Line 1: Three space-separated integers: L, N, and M Lines 2.. N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.
Output
Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks
Sample Input
25 5 2 2 14 11 21 17
Sample Output
4
Hint
Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).
#include <bits/stdc++.h> #define l(x) d[x][j+1] using namespace std; const int N = 105; int n, m, g[N][N], d[N][N], fol[N][N]; int main() { int n, m, u, b, t, k; while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) scanf("%d", &g[i][j]);
memset(d, 0x3f, sizeof(d)); for(int i = 0; i < n; ++i) d[i][m - 1] = g[i][m - 1]; for(int j = m - 2; j >= 0; --j) { for(int i = 0; i < n; ++i) { u = (i + n - 1) % n, b = (i + 1) % n, t = i; if(l(u) < l(t) || (l(u) == l(t) && u < t)) t = u; if(l(b) < l(t) || (l(b) == l(t) && b < t)) t = b; d[i][j] = g[i][j] + d[t][j + 1], fol[i][j] = t; } }
for(int i = k = 0; i < n; ++i) if(d[i][0] < d[k][0] || (d[i][0] == d[k][0] && i < k)) k = i; int ans = d[k][0]; for(int j = 0; j < m - 1; ++j) printf("%d ", k + 1), k = fol[k][j]; printf("%d\n%d\n", k + 1, ans); } return0; }
Background
Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) – finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit on travel time – is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check.
This problem deals with finding a minimal path through a grid of points while traveling only from left to right.
The Problem
Given an matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix ``wraps’’ so that it represents a horizontal cylinder. Legal steps are illustrated below.
The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited.
For example, two slightly different matrices are shown below (the only difference is the numbers in the bottom row).
The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.
The Input
The input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file.
For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path’s weight will exceed integer values representable using 30 bits.
The Output
Two lines should be output for each matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that islexicographically smallest should be output.
John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small plane and starts visiting beautiful places. To save money, John must determine the shortest closed tour that connects his destinations. Each destination is represented by a point in the plane pi = < *x*i, *y*i > . John uses the following strategy: he starts from the leftmost point, then he goes strictly left to right to the rightmost point, and then he goes strictly right back to the starting point. It is known that the points have distinct x -coordinates.
Write a program that, given a set of n points in the plane, computes the shortest closed tour that connects the points according to John’s strategy.
The program input is from a text file. Each data set in the file stands for a particular set of points. For each set of points the data set contains the number of points, and the point coordinates in ascending order of the x coordinate. White spaces can occur freely in input. The input data are correct.
For each set of data, your program should print the result to the standard output from the beginning of a line. The tour length, a floating-point number with two fractional digits, represents the result.
Note: An input/output sample is in the table below. Here there are two data sets. The first one contains 3 points specified by their x and y coordinates. The second point, for example, has the xcoordinate 2, and the y coordinate 3. The result for each data set is the tour length, (6.47 for the first data set in the given example).
#include <bits/stdc++.h> using namespace std; const int N = 55, M = 205; int t[N], d[N][M]; //j时刻在i号车站剩下的最小总等待时间 bool l[N][M], r[N][M]; //j时刻在i号车站是否有往左(右)的车
Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. After several thrilling events we find her in the first station of Algorithms City Metro, examining the time table. The Algorithms City Metro consists of a single line with trains running both ways, so its time table is not complicated.
Maria has an appointment with a local spy at the last station of Algorithms City Metro. Maria knows that a powerful organization is after her. She also knows that while waiting at a station, she is at great risk of being caught. To hide in a running train is much safer, so she decides to stay in running trains as much as possible, even if this means traveling backward and forward. Maria needs to know a schedule with minimal waiting time at the stations that gets her to the last station in time for her appointment. You must write a program that finds the total waiting time in a best schedule for Maria.
The Algorithms City Metro system has N stations, consecutively numbered from 1 to N. Trains move in both directions: from the first station to the last station and from the last station back to the first station. The time required for a train to travel between two consecutive stations is fixed since all trains move at the same speed. Trains make a very short stop at each station, which you can ignore for simplicity. Since she is a very fast agent, Maria can always change trains at a station even if the trains involved stop in that station at the same time.
The input file contains several test cases. Each test case consists of seven lines with information as follows. Line 1. The integer N ( 2N50), which is the number of stations. Line 2. The integer T ( 0T200), which is the time of the appointment. Line 3.N - 1 integers: t1, t2,…, tN - 1 ( 1ti70), representing the travel times for the trains between two consecutive stations: t1 represents the travel time between the first two stations, t2 the time between the second and the third station, and so on. Line 4. The integer M1 ( 1M150), representing the number of trains departing from the first station. Line 5.M1 integers: d1, d2,…, dM1 ( 0di250 and di < di + 1), representing the times at which trains depart from the first station. Line 6. The integer M2 ( 1M250), representing the number of trains departing from the N-th station. Line 7.M2 integers: e1, e2,…, eM2 ( 0ei250 and ei < ei + 1) representing the times at which trains depart from the N-th station.
The last case is followed by a line containing a single zero.
For each test case, print a line containing the case number (starting with 1) and an integer representing the total waiting time in the stations for a best schedule, or the word ` impossible ‘ in case Maria is unable to make the appointment. Use the format of the sample output.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 505; int a[N], d[N], m, k, maxi; ll s[N], le, ri, mid, mins, t;
int divs() { int last = 0, cnt = 1; for(int i = 1; i <= m; ++i) { if(s[i] - s[last] > mid) last = i - 1, ++cnt; } return cnt; }
int main() { int cas; scanf("%d", &cas); while(cas--) { scanf("%d %d", &m, &k); for(int i = maxi = 1; i <= m; ++i) { scanf("%d", &a[i]); s[i] = s[i - 1] + a[i]; if(a[i] > a[maxi]) maxi = i; }
le = a[maxi], ri = s[m]; while(le <= ri) { mid = (le + ri) >> 1; if(divs() <= k) mins = mid, ri = mid - 1; else le = mid + 1; }
t = 0; memset(d, 0, sizeof(d)); for(int i = m; i > 0; --i) { if(t + a[i] > mins) d[i] = k--, t = 0; if(k >= i) while(i > 0) d[--i] = 1; t = t + a[i]; }
for(int i = 1; i <= m; ++i) { printf("%d%c", a[i], i < m ? ' ' : '\n'); if(d[i]) printf("/ "); } } return0; }
Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered ) that may have different number of pages ( ) and you want to make one copy of each of them. Your task is to divide these books among k scribes, . Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers such that i-th scriber gets a sequence of books with numbers between b**i-1+1 and b**i. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.
The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integersm and k, . At the second line, there are integers separated by spaces. All these values are positive and less than 10000000.
For each case, print exactly one line. The line must contain the input succession divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character (`/‘) to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.
If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.
Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered ) that may have different number of pages ( ) and you want to make one copy of each of them. Your task is to divide these books among k scribes, . Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers such that i-th scriber gets a sequence of books with numbers between b**i-1+1 and b**i. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.
The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integersm and k, . At the second line, there are integers separated by spaces. All these values are positive and less than 10000000.
For each case, print exactly one line. The line must contain the input succession divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character (`/‘) to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.
If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.
#include <bits/stdc++.h> using namespace std; int main() { int n, t; long long ans, last; while(~scanf("%d", &n), n) { ans = last = 0; //last记录需要从i-1运输到i的量 for(int i = 1; i <= n; ++i) { scanf("%d", &t); ans += abs(last), last += t; } printf("%lld\n", ans); } return0; }
Wine trading in Gergovia
As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street, and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple enough: everyone buys wine from other inhabitants of the city. Every day each inhabitant decides how much wine he wants to buy or sell. Interestingly, demand and supply is always the same, so that each inhabitant gets what he wants.
There is one problem, however: Transporting wine from one house to another results in work. Since all wines are equally good, the inhabitants of Gergovia don’t care which persons they are doing trade with, they are only interested in selling or buying a specific amount of wine. They are clever enough to figure out a way of trading so that the overall amount of work needed for transports is minimized.
In this problem you are asked to reconstruct the trading during one day in Gergovia. For simplicity we will assume that the houses are built along a straight line with equal distance between adjacent houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of work.
Input Specification
The input consists of several test cases. Each test case starts with the number of inhabitants n (2 ≤ n ≤ 100000). The following line contains n integers ai (-1000 ≤ ai ≤ 1000). If ai ≥ 0, it means that the inhabitant living in the ith house wants to buy ai bottles of wine, otherwise if ai < 0, he wants to sell -ai bottles of wine. You may assume that the numbers ai sum up to 0. The last test case is followed by a line containing 0.
Output Specification
For each test case print the minimum amount of work units needed so that every inhabitant has his demand fulfilled. You may assume that this number fits into a signed 64-bit integer (in C/C++ you can use the data type “long long”, in JAVA the data type “long”).
matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix ``wraps’’ so that it represents a horizontal cylinder. Legal steps are illustrated below.
matrices are shown below (the only difference is the numbers in the bottom row).
integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file.
N
) that may have different number of pages ( 
) and you want to make one copy of each of them. Your task is to divide these books among k scribes, 
. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 
such that i-th scriber gets a sequence of books with numbers between b**i-1+1 and b**i. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.
. At the second line, there are integers 
separated by spaces. All these values are positive and less than 10000000.