A：

題干：

Input

The first line contains integer?n?(1?≤?n?≤?100) — the number of cars.

Each of the next?n?lines contains?n?space-separated integers that determine matrix?A.

It is guaranteed that on the main diagonal there are??-?1, and??-?1?doesn't appear anywhere else in the matrix.

It is guaranteed that the input is correct, that is, if?Aij?=?1, then?Aji?=?2, if?Aij?=?3, then?Aji?=?3, and if?Aij?=?0, then?Aji?=?0.

Output

Print the number of good cars and in the next line print their space-separated indices in the increasing order.

Examples

Input

3 -1 0 0 0 -1 1 0 2 -1

Output

2 1 3

Input

4 -1 3 3 3 3 -1 3 3 3 3 -1 3 3 3 3 -1

Output

0

題目大意：

? 給定一個N*N的矩陣a來描述N輛車的關系，如果a(i,j)=0代表這兩輛車都沒翻車，=1代表i車翻車了，=2代表j車翻車了，=3代表都翻車了。問你N輛車中有多少車是完好無損的？

解題報告：

? ?模擬、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n; int maze[555][555],qq[MAX]; int main() {cin>>n;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {scanf("%d",&maze[i][j]);}}int ans = 0;for(int i = 1;i<=n; i++) {bool flag = 1;for(int j = 1; j<=n; j++) {if(i == j) continue;if(maze[i][j] == 1 || maze[i][j] == 3) flag = 0;}if(flag) ++ans,qq[ans] = i;}printf("%d\n",ans);for(int i = 1; i<=ans; i++) {printf("%d%c",qq[i],i == ans ? '\n' : ' ');}return 0 ;}

---

B：

題干：

Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings?s?and?t?of the same length consisting of digits zero and one as the number of positions?i, such that?si?isn't equal to?ti.

As besides everything else Susie loves symmetry, she wants to find for two strings?sand?t?of length?n?such string?p?of length?n, that the distance from?p?to?s?was equal to the distance from?p?to?t.

It's time for Susie to go to bed, help her find such string?p?or state that it is impossible.

Input

The first line contains string?s?of length?n.

The second line contains string?t?of length?n.

The length of string?n?is within range from?1?to?105. It is guaranteed that both strings contain only digits zero and one.

Output

Print a string of length?n, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes).

If there are multiple possible answers, print any of them.

Examples

Input

0001 1011

Output

0011

Input

000 111

Output

impossible

Note

In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.

題目大意：

?先給出了漢明距離的定義，然后輸入s，t兩個字符串。讓你構造一個字符串p，st. Hamming(s,p) ==?Hamming(p.t)。

解題報告：

? 貪心就行了、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; char s[MAX],t[MAX]; int main() {cin>>(s+1);cin>>(t+1);int qq = 0;int len = strlen(s+1);for(int i = 1; i<=len; i++) {if(s[i] != t[i]) qq++;} if(qq%2 == 1) puts("impossible");else {int cur = 0;for(int i = 1; i<=len; i++) {if(s[i] != t[i] && cur*2 < qq) {cur++;printf("%c",t[i]);}else printf("%c",s[i]);}}return 0 ;}

---

C：

題干：

Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below.

There are?n?trees located along the road at points with coordinates?x1,?x2,?...,?xn. Each tree has its height?hi. Woodcutters can cut down a tree and fell it to the left or to the right. After that it occupies one of the segments?[xi?-?hi,?xi]?or?[xi;xi?+?hi]. The tree that is not cut down occupies a single point with coordinate?xi. Woodcutters can fell a tree if the segment to be occupied by the fallen tree doesn't contain any occupied point. The woodcutters want to process as many trees as possible, so Susie wonders, what is the maximum number of trees to fell.

Input

The first line contains integer?n?(1?≤?n?≤?105) — the number of trees.

Next?n?lines contain pairs of integers?xi,?hi?(1?≤?xi,?hi?≤?109) — the coordinate and the height of the??-th tree.

The pairs are given in the order of ascending?xi. No two trees are located at the point with the same coordinate.

Output

Print a single number — the maximum number of trees that you can cut down by the given rules.

Examples

Input

5 1 2 2 1 5 10 10 9 19 1

Output

3

Input

5 1 2 2 1 5 10 10 9 20 1

Output

4

Note

In the first sample you can fell the trees like that:

• fell the?1-st tree to the left — now it occupies segment?[?-?1;1]
• fell the?2-nd tree to the right — now it occupies segment?[2;3]
• leave the?3-rd tree — it occupies point?5
• leave the?4-th tree — it occupies point?10
• fell the?5-th tree to the right — now it occupies segment?[19;20]

In the second sample you can also fell?4-th tree to the right, after that it will occupy segment?[10;19].

題目大意：

無限長的數軸上有n個點，每個點的坐標為x[i]，種有高度為h[i]的樹，現在要把一些樹砍到，被砍倒的樹要么倒向左邊，要么倒向右邊，會分別把[xi?-?hi,?xi] 和 [xi,xi?+?hi]占用，如果某棵樹不被砍倒，那么它就只占用x[i]這一個點的位置，現在給定你n個點的x[i],h[i]，問最多能砍倒幾棵樹？（n<=1e5, x[i],h[i]<=1e9）

解題報告：

? 多階段決策問題，顯然dp。（不過這題好像貪心也能解決？因為關于第i棵樹的擺放，看他能不能往左倒，能倒就倒，否則看他如果往右倒那后面那顆能不能往左倒，，如果同時可以那就可以往右倒，如果左邊這個不可以倒，那就看右邊，如果左邊這個可以倒，那就一定倒。（為什么呢？因為你可以倒，那么就算你不倒，右邊那個如果往左倒，答案相同且對后面沒有影響，如果直立，答案還不如這種選擇，如果往右倒，那更不如這種選擇（因為這段空間就空著了啊）），，這樣貪心就行了，，但是顯然沒有dp簡單。）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n; ll x[MAX],h[MAX]; ll dp[MAX][3];//狀態表示：0不倒 1左邊 2右邊 ll Max(ll a,ll b,ll c) {return max(a,max(b,c)); } int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%lld %lld",x+i,h+i);x[0] = -0x3f3f3f3f;x[n+1] = 0x3f3f3f3f3f3f;ll ans = 0;for(int i = 1; i<=n; i++) {dp[i][0] = Max(dp[i-1][0],dp[i-1][1],dp[i-1][2]);if(x[i+1] - x[i] > h[i]) dp[i][2] = dp[i][0] + 1;else dp[i][2] = 0;dp[i][1] = max(dp[i-1][0],dp[i-1][2]);if(x[i] - x[i-1] > h[i]) dp[i][1] = max(dp[i][1],max(dp[i-1][1],dp[i-1][0])+1);if(x[i] - x[i-1] > h[i] + h[i-1]) dp[i][1] = max(dp[i][1],dp[i-1][2]+1);}printf("%lld\n",Max(dp[n][0],dp[n][1],dp[n][2]));return 0 ;}

---

D：

題干：

Little girl Susie went shopping with her mom and she wondered how to improve service quality.

There are?n?people in the queue. For each person we know time?ti?needed to serve him. A person will be disappointed if the time he waits is more than the time needed to serve him. The time a person waits is the total time when all the people who stand in the queue in front of him are served. Susie thought that if we swap some people in the queue, then we can decrease the number of people who are disappointed.

Help Susie find out what is the maximum number of not disappointed people can be achieved by swapping people in the queue.

Input

The first line contains integer?n?(1?≤?n?≤?105).

The next line contains?n?integers?ti?(1?≤?ti?≤?109), separated by spaces.

Output

Print a single number — the maximum number of not disappointed people in the queue.

Examples

Input

5 15 2 1 5 3

Output

4

Note

Value?4?is achieved at such an arrangement, for example:?1,?2,?3,?5,?15. Thus, you can make everything feel not disappointed except for the person with time 5.

題目大意：

有n個人，每個人都有一個等待時間，如果對于當前的人來說總等待時間超過自己的等待時間，那么這個人就會失望，問換一下順序，使失望的人最少，問最多有多少個人不失望。

解題報告：

? ?貪心，首先根據直覺排序，，然后如果他不失望那更好，如果他失望了，那么反正他也得失望，我們還不如把他換到最后去讓他失望的更多一些，所以掃一遍就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n; ll a[MAX]; int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i);sort(a+1,a+n+1);ll cur = 0,ans = 0;for(int i = 1; i<=n; i++) {if(cur <= a[i]) {ans++;cur += a[i];}}printf("%lld\n",ans);return 0 ;}

?

---

E：

題干：

Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows.

Let's assume that we are given a?connected?weighted undirected graph?G?=?(V,?E)?(here?V?is the set of vertices,?E?is the set of edges). The shortest-path tree from vertex?u?is such graph?G1?=?(V,?E1)?that is a tree with the set of edges?E1?that is the subset of the set of edges of the initial graph?E, and the lengths of the shortest paths from?u?to any vertex to?G?and to?G1?are the same.

You are given a?connected?weighted undirected graph?G?and vertex?u. Your task is to find the shortest-path tree of the given graph from vertex?u, the total weight of whose edges is minimum possible.

Input

The first line contains two numbers,?n?and?m?(1?≤?n?≤?3·105,?0?≤?m?≤?3·105) — the number of vertices and edges of the graph, respectively.

Next?m?lines contain three integers each, representing an edge —?ui,?vi,?wi?— the numbers of vertices connected by an edge and the weight of the edge (ui?≠?vi,?1?≤?wi?≤?109). It is guaranteed that graph is connected and that?there is no more than one edge between any pair of vertices.

The last line of the input contains integer?u?(1?≤?u?≤?n) — the number of the start vertex.

Output

In the first line print the minimum total weight of the edges of the tree.

In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from?1?in the order they follow in the input. You may print the numbers of the edges in any order.

If there are multiple answers, print any of them.

Examples

Input

3 3 1 2 1 2 3 1 1 3 2 3

Output

2 1 2

Input

4 4 1 2 1 2 3 1 3 4 1 4 1 2 4

Output

4 2 3 4

Note

In the first sample there are two possible shortest path trees:

• with edges?1?–?3?and?2?–?3?(the total weight is?3);
• with edges?1?–?2?and?2?–?3?(the total weight is?2);

And, for example, a tree with edges?1?–?2?and?1?–?3?won't be a shortest path tree for vertex?3, because the distance from vertex?3?to vertex?2?in this tree equals?3, and in the original graph it is?1.

題目大意：

給定一個n個結點m條邊的無向圖，并給出源點s，讓你找出圖中權值最小的最短路樹，并輸出這個權值，和選擇的邊的編號。

定義最短路樹：設最短路的圖為圖G，最短路樹的圖為圖Q，則源點s到G中任意一個頂點的距離，應該等于s到Q中任意一個頂點的距離，且Q為一棵樹。

解題報告：

? 首先不難證明，這個其實就是在所有最短路的可能的邊中去選擇其中的一些，其實可以看成是松弛（將一個點松弛成兩個點，也就是將邊數變得越多越好，當然，這是在保證最短路的基礎之上的）。所以我們可以在Dijkstra的時候同時維護邊權的最小值（也就是如果dis[] > dis[] + e[i].w 更新，else if dis[] ==?dis[] + e[i].w，則取權值最小，并且將該邊的編號記錄到對應的e[i].to對應的數組上，Dijkstra完了之后就結束了，最后按要求輸出就行了）。

? 這題我選擇了另外一種做法，先跑一邊裸的Dijkstra，然后我們得到了最短路數組dis，然后枚舉除了起點之外的每一個點，然后枚舉他的每一條邊，并記錄它到起點的那條邊的邊權最小值，這條邊一定選在這棵樹內，最后按要求輸出。這樣寫代碼更好實現一些。其實兩個方法是等價的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #include<ctime> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 6e5 + 5; struct Edge {int to,ne,ii;ll w; } e[MAX]; int head[MAX],tot,n,m; bool vis[MAX]; int ans[MAX],cnt; ll dis[MAX]; void add(int u,int v,ll w,int i) {e[++tot].to = v;e[tot].ne = head[u];e[tot].w = w;e[tot].ii = i;head[u] = tot; } struct Point {int id;ll c;Point(){}Point(int id,ll c):id(id),c(c){}bool operator<(const Point & b) const{return c > b.c;} }; void Dijkstra(int st) {for(int i = 1; i<=n; i++) dis[i] = LLONG_MAX;dis[st] = 0;priority_queue<Point> pq;pq.push(Point(st,0));while(!pq.empty()) {Point cur = pq.top();pq.pop();if(vis[cur.id]) continue;vis[cur.id] = 1;for(int i = head[cur.id]; i!=-1; i = e[i].ne) {int v = e[i].to;if(dis[v] > dis[cur.id] + e[i].w) {dis[v] = dis[cur.id] + e[i].w;pq.push(Point(v,dis[v]));}}} } int main() {int u,v;memset(head,-1,sizeof head);ll w;cin>>n>>m;for(int i = 1; i<=m; i++) {scanf("%d%d%lld",&u,&v,&w);add(u,v,w,i);add(v,u,w,i);}cin>>u;Dijkstra(u);int minid;ll ANS = 0;for(int i = 1; i<=n; i++) {if(i == u) continue;ll minn = LLONG_MAX;for(int j = head[i]; j != -1; j = e[j].ne) {if(dis[i] == dis[e[j].to] + e[j].w && minn > e[j].w) {minn = e[j].w;minid = e[j].ii;}}ANS += minn;ans[++cnt] = minid;}printf("%lld\n",ANS);for(int i = 1; i<=cnt; i++) {printf("%d ",ans[i]);}return 0 ;}

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【CodeForces - 545 ABCDE套题训练题解】贪心， 构造，模拟，dp，最短路树（Dijkstra+变形）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。