George woke up and saw the current time s on the digital clock. Besides, George knows that he has slept for time t.
Help George! Write a program that will, given time s and t, determine the time p when George went to bed. Note that George could have gone to bed yesterday relatively to the current time (see the second test sample).
The first line contains current time s as a string in the format "hh:mm". The second line contains time t in the format "hh:mm" — the duration of George‘s sleep. It is guaranteed that the input contains the correct time in the 24-hour format, that is, 00?≤?hh?≤?23, 00?≤?mm?≤?59.
In the single line print time p — the time George went to bed in the format similar to the format of the time in the input.
05:50 05:44
00:06
00:00 01:00
23:00
00:01 00:00
00:01
In the first sample George went to bed at "00:06". Note that you should print the time only in the format "00:06". That‘s why answers "0:06", "00:6" and others will be considered incorrect.
In the second sample, George went to bed yesterday.
In the third sample, George didn‘t do to bed at all.
A:水题，直接模拟时间即可。
#include <stdio.h>
#include <string.h>
int hh, mm;
int hhh, mmm;
int main() {
scanf("%d%*c%d", &hh, &mm);
scanf("%d%*c%d", &hhh, &mmm);
int ansh, ansm;
if (mm >= mmm) ansm = mm - mmm;
else {ansm = mm + 60 - mmm; hh--;}
if (hh >= hhh) ansh = hh - hhh;
else ansh = hh + 24 - hhh;
printf("%02d:%02d\n", ansh, ansm);
return 0;
}
George decided to prepare a Codesecrof round, so he has prepared m problems for the round. Let‘s number the problems with integers1 through m. George estimates the i-th problem‘s complexity by integer bi.
To make the round good, he needs to put at least n problems there. Besides, he needs to have at least one problem with complexity exactly a1, at least one with complexity exactly a2, ..., and at least one with complexity exactly an. Of course, the round can also have problems with other complexities.
George has a poor imagination. It‘s easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity c to any positive integer complexity d (c?≥?d), by changing limits on the input data.
However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a goodround. That‘s why he decided to find out the minimum number of problems he needs to come up with in addition to the m he‘s prepared in order to make a good round. Note that George can come up with a new problem of any complexity.
The first line contains two integers n and m (1?≤?n,?m?≤?3000) — the minimal number of problems in a good round and the number of problems George‘s prepared. The second line contains space-separated integers a1,?a2,?...,?an (1?≤?a1?<?a2?<?...?<?an?≤?106) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers b1,?b2,?...,?bm (1?≤?b1?≤?b2...?≤?bm?≤?106) — the complexities of the problems prepared by George.
Print a single integer — the answer to the problem.
3 5 1 2 3 1 2 2 3 3
0
3 5 1 2 3 1 1 1 1 1
2
3 1 2 3 4 1
3
In the first sample the set of the prepared problems meets the requirements for a good round.
In the second sample, it is enough to come up with and prepare two problems with complexities 2 and 3 to get a good round.
In the third sample it is very easy to get a good round if come up with and prepare extra problems with complexities: 2,?3,?4.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1000005;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n, m, i, j;
int a[3005], b[3005];
int Max = 0;
int main() {
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < m; i++)
scanf("%d", &b[i]);
sort(a, a + n);
sort(b, b + m);
int ans = 0;
int l = 0, r = 0;
while (l < n && r < m) {
if (a[l] <= b[r]) {
l++; r++;
}
else {
r++;
}
}
ans = n - l;
printf("%d\n", ans);
return 0;
}
George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers b. During the game, George modifies the array by using special changes. Let‘s mark George‘s current array as b1,?b2,?...,?b|b| (record |b| denotes the current length of the array). Then one change is a sequence of actions:
- Choose two distinct indexes i and j (1?≤?i,?j?≤?|b|; i?≠?j), such that bi?≥?bj.
- Get number v?=?concat(bi,?bj), where concat(x,?y) is a number obtained by adding number y to the end of the decimal record of number x. For example, concat(500,?10)?=?50010, concat(2,?2)?=?22.
- Add number v to the end of the array. The length of the array will increase by one.
- Remove from the array numbers with indexes i and j. The length of the array will decrease by two, and elements of the array will become re-numbered from 1 to current length of the array.
George played for a long time with his array b and received from array b an array consisting of exactly one number p. Now George wants to know: what is the maximum number of elements array b could contain originally? Help him find this number. Note that originally the array could contain only positive integers.
The first line of the input contains a single integer p (1?≤?p?<?10100000). It is guaranteed that number p doesn‘t contain any leading zeroes.
Print an integer — the maximum number of elements array b could contain originally.
9555
4
10000000005
2
800101
3
45
1
1000000000000001223300003342220044555
17
19992000
1
310200
2
C题：贪心，从后面往前推，如果可以分离就直接分离ans++，不行就在继续添加数字。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 100005;
char seq[N];
int i, j;
char save[N];
int sn = 0;
int len;
bool judge(int len) {
if (i > sn) return true;
if (i < sn) return false;
if (i == sn) {
for (int j = sn - 1; j >= 0; j--) {
if (seq[sn - 1 - j] < save[j]) return false;
}
}
return true;
}
int main() {
int ans = 1;
scanf("%s", seq);
len = strlen(seq);
for (i = len - 1; i >= 0; i--) {
if (seq[i] != ‘0‘) {
save[sn++] = seq[i];
if (judge(i)) {
ans++;
sn = 0;
}
}
else {
save[sn++] = seq[i];
}
}
printf("%d\n", ans);
return 0;
}
George loves graphs. Most of all, he loves interesting graphs. We will assume that a directed graph is interesting, if it meets the following criteria:
- The graph doesn‘t contain any multiple arcs;
- There is vertex v (we‘ll call her the center), such that for any vertex of graph u, the graph contains arcs (u,?v) and (v,?u). Please note that the graph also contains loop (v,?v).
- The outdegree of all vertexes except for the center equals two and the indegree of all vertexes except for the center equals two. The outdegree of vertex u is the number of arcs that go out of u, the indegree of vertex u is the number of arcs that go in u. Please note that the graph can contain loops.
However, not everything‘s that simple. George got a directed graph of n vertices and m arcs as a present. The graph didn‘t have any multiple arcs. As George loves interesting graphs, he wants to slightly alter the presented graph and transform it into an interesting one. In one alteration he can either remove an arbitrary existing arc from the graph or add an arbitrary arc to the graph.
George wonders: what is the minimum number of changes that he needs to obtain an interesting graph from the graph he‘s got as a present? Help George and find the answer to the question.
The first line contains two space-separated integers n and m (2?≤?n?≤?500,?1?≤?m?≤?1000) — the number of vertices and arcs in the presented graph.
Each of the next m lines contains two space-separated integers ai,?bi (1?≤?ai,?bi?≤?n) — the descriptions of the graph‘s arcs. Pair(ai,?bi) means that the graph contains an arc from vertex number ai to vertex number bi. It is guaranteed that the presented graph doesn‘t contain multiple arcs.
Assume that the grah vertices are numbered 1 through n.
Print a single integer — the answer to George‘s question.
3 7 1 1 2 2 3 1 1 3 3 2 2 3 3 3
0
3 6 1 1 2 2 3 1 3 2 2 3 3 3
1
3 1 2 2
6
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f
const int N = 505;
int n, m, g[N][N], ind[N], out[N], match[N], vis[N];
bool find(int u, int i) {
for (int j = 1; j <= n; j++) {
if (u == j || vis[j] || !g[i][j]) continue;
vis[j] = 1;
if (match[j] == -1 || find(u, match[j])) {
match[j] = i;
return true;
}
}
return false;
}
int cal(int u) {
int ans = 0;
memset(match, -1, sizeof(match));
for (int i = 1; i <= n; i++) {
if (i == u) continue;
memset(vis, 0, sizeof(vis));
if (find(u, i)) ans++;
}
return ans;
}
int solve(int u) {
int uedge = ind[u] + out[u] - g[u][u];//与u点相连的边数
int ans = 2 * n - 1 - uedge;
int Max = cal(u);
ans += m - uedge - Max; //需要删除的边数
ans += n - 1 - Max; //需要添加的边数
return ans;
}
int main() {
scanf("%d%d", &n, &m);
int x, y, ans = INF, mm = m;
while (mm--) {
scanf("%d%d", &x, &y);
g[x][y] = 1;
ind[y]++;
out[x]++;
}
for (int i = 1; i <= n; i++) {
int t = solve(i);
ans = min(ans, t);
}
printf("%d\n", ans);
return 0;
}
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 1000005;
#include <set>
using namespace std;
#define INF 0x3f3f3f3f
int n, k, v[N], vis[N], i, bit[N];
void Insert(int x, int v) {
while (x <= n) {
bit[x] += v;
x += (x&(-x));
}
}
int Sum(int x) {
int ans = 0;
while (x > 0) {
ans += bit[x];
x -= (x&(-x));
}
return ans;
}
__int64 solve() {
__int64 ans = 0;
set<int> s;
s.insert(0);
s.insert(n + 1);
for (int i = 1; i <= n; i++) {
if (vis[i]) {
s.insert(v[i]);
}
else {
set<int>::iterator it = s.lower_bound(v[i]);
int r = *it - 1;
int l = *(--it);
ans += Sum(r) - Sum(l);
Insert(v[i], -1);
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &k);
int num;
for (i = 1; i <= n; i++) {
scanf("%d", &num);
v[num] = i;
Insert(i, 1);
}
for (i = 1; i <= k; i++) {
scanf("%d", &num);
vis[num] = 1;
}
printf("%I64d\n", solve());
return 0;
}