#include<cstdio> #include<cstring> using namespace std; const int N = 100005; int h[N]; int main() { int n, e, ans; scanf("%d",&n); for (int i = 1; i <= n; ++i) scanf ("%d", &h[i]); ans = 0; for (int i = e = 0; i < n; ++i) { if (h[i] + e < h[i + 1]) { int t = (h[i + 1] - e - h[i]); h[i] += t; ans += t; } e += (h[i] - h[i + 1]); } printf ("%d\n", ans); return0; }
Caisa solved the problem with the sugar and now he is on the way back to home.
Caisa is playing a mobile game during his path. There are(n + 1)pylons numbered from0tonin this game. The pylon with number0has zero height, the pylon with numberi(i > 0)has heighth**i. The goal of the game is to reachn-th pylon, and the only move the player can do is to jump from the current pylon (let’s denote its number ask) to the next one (its number will bek + 1). When the player have made such a move, its energy increases byh**k - h**k + 1(if this value is negative the player loses energy). The player must have non-negative amount of energy at any moment of the time.
Initially Caisa stand at0pylon and has0energy. The game provides a special opportunity: one can pay a single dollar and increase the height of anyone pylon by one. Caisa may use that opportunity several times, but he doesn’t want to spend too much money. What is the minimal amount of money he must paid to reach the goal of the game? Input
The first line contains integern(1 ≤ n ≤ 105). The next line containsnintegersh1,h2, …,h**n(1 ≤ h**i ≤ 105)representing the heights of the pylons.
Output
Print a single number representing the minimum number of dollars paid by Caisa. Sample test(s)
input 5 3 4 3 2 4
output 4 input 3 4 4 4
output 4
Note
In the first sample he can pay4dollars and increase the height of pylon with number0by4units. Then he can safely pass to the last pylon.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { int n, s, cos; while (~scanf ("%d%d", &n, &s)) { s *= 100; int flag = 0, a, b, ans = 0; while (n--) { scanf ("%d%d", &a, &b); cos = a * 100 + b; for (int j = 1; cos * j <= s; ++j) { flag = 1; ans = max (ans, (s - cos) % 100); } } printf ("%d\n", flag ? ans : -1); } return0; }
Caisais going to have a party and he needs to buy the ingredients for a big chocolate cake. For that he is going to the biggest supermarket in town.
Unfortunately, he has justsdollars for sugar. But that’s not a reason to be sad, because there arentypes of sugar in the supermarket, maybe he able to buy one. But that’s not all. The supermarket has very unusual exchange politics: instead of cents the sellers give sweets to a buyer as a change. Of course, the number of given sweets always doesn’t exceed99, because each seller maximizes the number of dollars in the change (100cents can be replaced with a dollar).
Caisa wants to buy only one type of sugar, also he wants to maximize the number of sweets in the change. What is the maximum number of sweets he can get? Note, that Caisa doesn’t want to minimize the cost of the sugar, he only wants to get maximum number of sweets as change. Input
The first line contains two space-separated integersn, s(1 ≤ n, s ≤ 100).
Thei-th of the nextnlines contains two integersx**i,y**i(1 ≤ x**i ≤ 100; 0 ≤ y**i < 100), wherex**irepresents the number of dollars andy**ithe number of cents needed in order to buy thei-th type of sugar.
Output
Print a single integer representing the maximum number of sweetshe can buy, or-1if he can’t buy any type of sugar. Sample test(s)
input 5 10 3 90 12 0 9 70 5 50 7 0
output 50 input 5 5 10 10 20 20 30 30 40 40 50 50
output -1
Note
In the first test sample Caisa can buy the fourth type of sugar, in such a case he will take50sweets as a change.
#include<cstdio> #include<cstring> using namespace std; int t, n, a, b, ans, l; int main() { scanf ("%d", &t); while (t--) { scanf ("%d", &n); ans = 0; for (int i = n-50; i < n; ++i) { a = b = i; while (b) { a += b % 10; b /= 10; } if (a + b == n) { ans = i; break; } } printf ("%d\n", ans); } return0; }
For a positive integer N , the digit-sum of N is defined as the sum of N itself and its digits. When M is the digitsum of N , we call N a generator of M .
For example, the digit-sum of 245 is 256 (= 245 + 2 + 4 + 5). Therefore, 245 is a generator of 256.
Not surprisingly, some numbers do not have any generators and some numbers have more than one generator. For example, the generators of 216 are 198 and 207.
You are to write a program to find the smallest generator of the given integer.
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case takes one line containing an integer N , 1N100, 000 .
Your program is to write to standard output. Print exactly one line for each test case. The line is to contain a generator of N for each test case. If N has multiple generators, print the smallest. If N does not have any generators, print 0.
The following shows sample input and output for three test cases.
#include<cstdio> #include<cctype> #include<cstring> const int N = 35; int l; char s[N], mc[] = "A 3 HIL JM O 2TUVWXY5", mn[] = "1SE Z 8 ";
bool isRegular() { for (int i = 1; i <= l / 2; ++i) if (s[i] != s[l - i + 1]) returnfalse; returntrue; }
bool isMirrored() { for (int i = 1; i <= (l + 1) / 2 ; ++i) { if (isalpha (s[i]) && s[l - i + 1] != mc[s[i] - 'A']) returnfalse; elseif (isdigit (s[i]) && s[l - i + 1] != mn[s[i] - '1']) returnfalse; } returntrue; }
int main() { while (scanf ("%s", s + 1) != EOF) { l = strlen (s + 1); if (isMirrored()) { if (isRegular()) printf ("%s -- is a mirrored palindrome.\n\n", s + 1); elseprintf ("%s -- is a mirrored string.\n\n", s + 1); } elseif (isRegular()) printf ("%s -- is a regular palindrome.\n\n", s + 1); elseprintf ("%s -- is not a palindrome.\n\n", s + 1); } return0; }
A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string “ABCDEDCBA” is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left.
A mirrored string is a string for which when each of the elements of the string is changed to its reverse (if it has a reverse) and the string is read backwards the result is the same as the original string. For example, the string “3AIAE” is a mirrored string because “A” and “I” are their own reverses, and “3” and “E” are each others’ reverses.
A mirrored palindrome is a string that meets the criteria of a regular palindrome and the criteria of a mirrored string. The string “ATOYOTA” is a mirrored palindrome because if the string is read backwards, the string is the same as the original and because if each of the characters is replaced by its reverse and the result is read backwards, the result is the same as the original string. Of course, “A”, “T”, “O”, and “Y” are all their own reverses.
A list of all valid characters and their reverses is as follows.
Character Reverse Character Reverse Character Reverse A A M M Y Y B N Z 5 C O O 1 1 D P 2 S E 3 Q 3 E F R 4 G S 2 5 Z H H T T 6 I I U U 7 J L V V 8 8 K W W 9 L J X X
Note that O (zero) and 0 (the letter) are considered the same character and therefore ONLY the letter “0” is a valid character.
Input consists of strings (one per line) each of which will consist of one to twenty valid characters. There will be no invalid characters in any of the strings. Your program should read to the end of file.
For each input string, you should print the string starting in column 1 immediately followed by exactly one of the following strings.
STRING CRITERIA “ – is not a palindrome.” if the string is not a palindrome and is not a mirrored string “ – is a regular palindrome.” if the string is a palindrome and is not a mirrored string “ – is a mirrored string.” if the string is not a palindrome and is a mirrored string “ – is a mirrored palindrome.” if the string is a palindrome and is a mirrored string
Note that the output line is to include the -‘s and spacing exactly as shown in the table above and demonstrated in the Sample Output below.
In addition, after each output line, you must print an empty line.
NOTAPALINDROME ISAPALINILAPASI 2A3MEAS ATOYOTA
NOTAPALINDROME – is not a palindrome. ISAPALINILAPASI – is a regular palindrome. 2A3MEAS – is a mirrored string. ATOYOTA – is a mirrored palindrome.
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N = 1000; int n, k, ans; bool isPrime (int a) { for (int i = 2; i <= sqrt (a); ++i) if (a % i == 0) return0; return1; } int main() { int ai = 1, bi = 0, a[N], b[N]; a[1] = 2; for (int i = 3; i <= N; ++i) if (isPrime (i)) { a[++ai] = i; b[++bi] = a[ai] + a[ai - 1] + 1; } scanf ("%d%d", &n, &k); ans = 0; for (int i = 13; i <= n; ++i) if (isPrime (i) && find (b + 1, b + bi + 1, i) != b + bi + 1) ans++; if (ans >= k) printf ("YES\n"); elseprintf ("NO\n"); return0; }
Nick is interested in prime numbers. Once he read about Goldbach problem. It states that every even integer greater than 2 can be expressed as the sum of two primes. That got Nick’s attention and he decided to invent a problem of his own and call it Noldbach problem. Since Nick is interested only in prime numbers, Noldbach problem states that at least k prime numbers from 2 to n inclusively can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 =5 + 7 + 1.
Two prime numbers are called neighboring if there are no other prime numbers between them.
You are to help Nick, and find out if he is right or wrong. Input
The first line of the input contains two integers n (2 ≤ n ≤ 1000) and k (0 ≤ k ≤ 1000).
Output
Output YES if at least k prime numbers from 2 to n inclusively can be expressed as it was described above. Otherwise output NO. Sample test(s)
input 27 2
output YES input 45 7
output NO
Note
In the first sample the answer is YES since at least two numbers can be expressed as it was described (for example, 13 and 19). In the second sample the answer is NO since it is impossible to express 7 prime numbers from 2 to 45 in the desired form.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M = 25; int a[M], b[M], c[M], n, m, ans; bool cmp (int i, int j) { return b[i] > b[j]; } int main() { scanf ("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { c[i] = i; scanf ("%d%d", &a[i], &b[i]); } sort (c + 1, c + m + 1, cmp); ans = 0; for (int i = 1; i <= m; ++i) { if (n >= a[c[i]]) { n -= a[c[i]]; ans += a[c[i]] * b[c[i]]; } else { ans += n * b[c[i]]; break; } } printf ("%d\n", ans); return0; }
A burglar got into a matches warehouseand wants to steal as many matches as possible. In the warehouse there are mcontainers, in the i-th container there are a**i matchboxes, and each matchbox contains b**i matches. All the matchboxes are of the same size. The burglar’s rucksack can hold n matchboxes exactly. Your task is to find out the maximum amount of matches that a burglar can carry away. He has no time to rearrange matches in the matchboxes, that’s why he just chooses not more than n matchboxes so that the total amount of matches in them is maximal. Input
The first line of the input contains integer n (1 ≤ n ≤ 2·108) and integer m (1 ≤ m ≤ 20). The i + 1-th line contains a pair of numbers a**i and b**i (1 ≤ a**i ≤ 108, 1 ≤ b**i ≤ 10). All the input numbers are integer.
Output
Output the only number — answer to the problem. Sample test(s)
#include<cstdio> #include<cstring> using namespace std; const int N = 1500;
int main() { char s[3]; int n, m, l; double p[N], ans; while (~scanf ("%d%d", &n, &m)) { memset (p, 0, sizeof (p)); l = m;
for (int i = 1; i <= n; ++i) { scanf ("%s", s); p[l] = 1; if (s[0]<'A' && s[1]!='0') l += s[0] - '0'; elseif (s[0] == 'A') l += 11; else l+= 10; }
ans = 0; for (int i = l ; i >= 1; --i) { if (p[i] == 0) { for (int j = 2; j <= 11; ++j) { int t = (j == 10 ? 4 : 1); p[i] += t * p[i + j]; } p[i] /= 13; } if (i <= 10) ans += p[i]; }
printf ("%.8f\n", ans / 10); } return0; }
Card Trick
Time Limit: 2999/999MS (Java/Others) Memory Limit: 65432/65432KB (Java/Others)
Submit Status I am learning magic tricks to impress my girlfriend Alice. My latest trick is a probabilistic one, i.e. it does work in most cases, but not in every case. To perform the trick, I first shuffle a set of many playing cards and put them all in one line with faces up on the table. Then Alice secretly selects one of the first ten cards (i.e. she choosesx0, a secret number between1and10inclusive) and skips cards repeatedly as follows: after having selected a card at positionxiwith a numberc(xi)on its face, she will select the card at positionxi+1=xi+c(xi). Jack (
1
J
), Queen (
1
Q
), and King (
1
K
) count as10, Ace (
1
A
) counts as11. You may assume that there are at least ten cards on the table.
Alice stops this procedure as soon as there is no card at positionxi+c(xi). I then perform the same procedure from a randomly selected starting position that may be different from the position selected by Alice. It turns out that often, I end up at the same position. Alice is very impressed by this trick.
However, I am more interested in the underlying math. Given my randomly selected starting position and the card faces of every selected card (including my final one), can you compute the probability that Alice chose a starting position ending up on the same final card? You may assume that her starting position is randomly chosen with uniform probability (between1and10inclusive). I forgot to note the cards that I skipped, so these cards are unknown. You may assume that the card face of every single of the unknown cards is independent of the other card faces and random with uniform probability out of the possible card faces (i.e.
1
2
1
10
,
1
J
,
1
Q
,
1
K
, and
1
A
).
*Illustration of first sample input: my starting position is2, so I start selecting that card. Then I keep skipping cards depending on the card’s face. This process iterates until there are not enough cards to skip (in this sample:
1
Q
). The final
1
Q
card is followed by0to9unknown cards, since
1
Q
counts as10.*
Input
For each test case:
Output
For each test case, print one line containing the probability that Alice chooses a starting position that leads to the same final card. Your output should have an absolute error of at most10−7.
#include<cstdio> #include<cstring> using namespace std; const int N = 1441; int hi, ho, mi, mo, si, so, t, n, ans, p, peo[N]; int main() { scanf ("%d", &t); while (t--) { scanf ("%d", &n); memset (peo, 0, sizeof (peo)); for (int i = 1; i <= n; ++i) { scanf ("%d %d:%d %d:%d", &p, &hi, &mi, &ho, &mo); si = hi * 60 + mi; so = ho * 60 + mo; for (int j = si; j < so; ++j) peo[j] += p; } for (int i = ans = 1; i < N; ++i) if (peo[i] > ans) ans = peo[i]; printf ("%d\n", ans); } return0; }
TIANKENG’s restaurant
Problem Description
TIANKENG manages a restaurant after graduating from ZCMU, and tens of thousands of customers come to have meal because of its delicious dishes. Today n groups of customers come to enjoy their meal, and there are Xi persons in the ith group in sum. Assuming that each customer can own only one chair. Now we know the arriving time STi and departure time EDi of each group. Could you help TIANKENG calculate the minimum chairs he needs to prepare so that every customer can take a seat when arriving the restaurant? Input
The first line contains a positive integer T(T<=100), standing for T test cases in all. Each cases has a positive integer n(1<=n<=10000), which means n groups of customer. Then following n lines, each line there is a positive integer Xi(1<=Xi<=100), referring to the sum of the number of the ith group people, and the arriving time STi and departure time Edi(the time format is hh:mm, 0<=hh<24, 0<=mm<60), Given that the arriving time must be earlier than the departure time. Pay attention that when a group of people arrive at the restaurant as soon as a group of people leaves from the restaurant, then the arriving group can be arranged to take their seats if the seats are enough. Output
For each test case, output the minimum number of chair that TIANKENG needs to prepare. Sample Input
<span style="font-size:14px;">#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N = 100050; ll k[N], o[N], t[N], e[N], n; bool cmp (int i, int j) { return (e[i] * k[j] < e[j] * k[i]); } int main() { while (scanf ("%I64d", &n) != EOF) { for (int i = 1; i <= n; ++i) scanf ("%I64d", &e[i]); for (int i = 1; i <= n; ++i) { o[i] = i; scanf ("%I64d", &k[i]); } sort (o + 1, o + n + 1, cmp); ll ans=0; for (int i = 1; i <= n; ++i) { int j=o[i]; t[j]=t[o[i-1]]+e[j]; ans += k[j] * t[j]; } printf ("%I64d\n", ans); } return0; } </span>
Though ZCC has many Fans, ZCC himself is a crazy Fan of a coder, called “Memset137”. It was on Codefires(CF), an online competitive programming site, that ZCC knew Memset137, and immediately became his fan. But why? Because Memset137 can solve all problem in rounds, without unsuccessful submissions; his estimation of time to solve certain problem is so accurate, that he can surely get an Accepted the second he has predicted. He soon became IGM, the best title of Codefires. Besides, he is famous for his coding speed and the achievement in the field of Data Structures. After become IGM, Memset137 has a new goal: He wants his score in CF rounds to be as large as possible. What is score? In Codefires, every problem has 2 attributes, let’s call them Ki and Bi(Ki, Bi＞0). if Memset137 solves the problem at Ti-th second, he gained Bi-Ki/*Ti score. It’s guaranteed Bi-Ki/*Ti is always positive during the round time. Now that Memset137 can solve every problem, in this problem, Bi is of no concern. Please write a program to calculate the minimal score he will lose.(that is, the sum of Ki/*Ti). Input
The first line contains an integer N(1≤N≤10^5), the number of problem in the round. The second line contains N integers Ei(1≤Ei≤10^4), the time(second) to solve the i-th problem. The last line contains N integers Ki(1≤Ki≤10^4), as was described. Output
One integer L, the minimal score he will lose. Sample Input
#include<iostream> #include<string> #include<map> using namespace std; map<string, int> d; int n, ans; string t, S;
int dp (string s) { if (d[s] > 0) return d[s]; d[s] = 1; for (int i = 0; i < 10; ++i) { if (s[i] == 'o' && s[i + 1] == 'o' && s[i + 2] == '-') { t = s; t[i] = t[i + 1] = '-'; t[i + 2] = 'o'; d[s] = max (d[s], dp (t) + 1); } if (s[i] == '-' && s[i + 1] == 'o' && s[i + 2] == 'o') { t = s; t[i] = 'o'; t[i + 1] = t[i + 2] = '-'; d[s] = max (d[s], dp (t) + 1); } } return d[s]; }
int main() { cin >> n; while (n--) { ans = 1; cin >> S; for (int i = 0; i < 12; ++i) if (S[i] == 'o') ans++; ans -= dp (S); cout << ans << endl; } return0; }
Pebble Solitaire
Pebble solitaire is an interesting game. This is a game where you are given a board with an arrangement of small cavities, initially all but one occupied by a pebble each. The aim of the game is to remove as many pebbles as possible from the board. Pebbles disappear from the board as a result of a move. A move is possible if there is a straight line of three adjacent cavities, let us call themA,B, andC, withBin the middle, whereAis vacant, butBandCeach contain a pebble. The move constitutes of moving the pebble fromCtoA, and removing the pebble inBfrom the board. You may continue to make moves until no more moves are possible.
In this problem, we look at a simple variant of this game, namely a board with twelve cavities located along a line. In the beginning of each game, some of the cavities are occupied by pebbles. Your mission is to find a sequence of moves such that as few pebbles as possible are left on the board.
Input
The input begins with a positive integernon a line of its own. Thereafterndifferent games follow. Each game consists of one line of input with exactly twelve characters, describing the twelve cavities of the board in order. Each character is either**’-‘or‘o’(The fifteenth character of English alphabet in lowercase). A‘-‘(minus) character denotes an empty cavity, whereas a‘o’**character denotes a cavity with a pebble in it. As you will find in the sample that there may be inputs where no moves is possible.
Output
For each of the n games in the input, output the minimum number of pebbles left on the board possible to obtain as a result of moves, on a row of its own.
N