Codeforces Round #249 (Div. 2) (ABCD題解)

Codeforces Round #249 (Div. 2) (ABCD題解)

 

 

A. Queue on Bus Stop time limit per test：1 second memory limit per test：256 megabytes

It's that time of the year when the Russians flood their countryside summer cottages (dachas) and the bus stop has a lot of people. People rarely go to the dacha on their own, it's usually a group, so the people stand in queue by groups.

The bus stop queue has n groups of people. The i-th group from the beginning has a_i people. Every 30 minutes an empty bus arrives at the bus stop, it can carry at most m people. Naturally, the people from the first group enter the bus first. Then go the people from the second group and so on. Note that the order of groups in the queue never changes. Moreover, if some group cannot fit all of its members into the current bus, it waits for the next bus together with other groups standing after it in the queue.

Your task is to determine how many buses is needed to transport all n groups to the dacha countryside.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100). The next line contains n integers: a₁, a₂, ..., a_n (1 ≤ a_i ≤ m).

Output

Print a single integer — the number of buses that is needed to transport all n groups to the dacha countryside.

Sample test(s) Input

4 3
2 3 2 1

Output

3

Input

3 4
1 2 1

Output

1

 

題目大意：一共n個站台，每個站台一開始有ai個人，一輛車一次最多載m個人，如果當前這輛車不能裝下當前站的所有人，則當前站的人都不上車而等下一輛，問搭載所有的人需要幾輛車

題目分析：照著題意模擬即可

 

#include 
#include 
#include 
using namespace std;

int a[105];

int main()
{
    int n, m;
    scanf(%d %d, &n, &m);
    for(int i = 0; i < n; i++)
        scanf(%d, &a[i]);
    int ans = 1;
    int now = m;
    for(int i = 0; i < n;)
    {
        if(a[i] <= now)
        {
            now -= a[i];
            i ++;
        }
        else
        {
            now = m;
            ans ++;
        }
    }
    printf(%d
, ans);
}

 

 

 

 

B. Pasha Maximizes time limit per test：1 second memory limit per test：256 megabytes

Pasha has a positive integer a without leading zeroes. Today he decided that the number is too small and he should make it larger. Unfortunately, the only operation Pasha can do is to swap two adjacent decimal digits of the integer.

Help Pasha count the maximum number he can get if he has the time to make at most k swaps.

Input

The single line contains two integers a and k (1 ≤ a ≤ 10¹⁸; 0 ≤ k ≤ 100).

Output

Print the maximum number that Pasha can get if he makes at most k swaps.

Sample test(s) Input

1990 1

Output

9190

Input

300 0

Output

300

Input

1034 2

Output

3104

Input

9090000078001234 6

Output

9907000008001234

 

題目大意：給一個數a，每次只能交換相鄰兩個數，最多交換k次，求交換後的最大數字

題目分析：貪心問題，顯然大數字往前放的貪心策略是錯的，正確的應該是盡量讓高位的數字大，從最高位開始向低位找，先找到k步之內的最大數，如果k步之內的最大數不是當前位置的數，那麼把最大數交換到當前為止，沒交換一次，k減1

 

#include 
#include 
#include 
using namespace std;

char s[20];
int k;

int main()
{
    scanf(%s %d, s, &k);
    int len = strlen(s);
    int now;
    for(int i = 0; i < len; i++)
    {
        now = i;
        for(int j = i + 1; j <= i + k && j < len; j++)
            if(s[j] > s[now])
                now = j;
        if(now != i)
        {
            for(int j = now; j > i; j--)
            {
                swap(s[j], s[j - 1]);
                k --;
            }
        }
    }
    printf(%s
, s);
}

 

 

 

 

C. Cardiogram time limit per test：1 second memory limit per test：256 megabytes

In this problem, your task is to use ASCII graphics to paint a cardiogram.

A cardiogram is a polyline with the following corners:

That is, a cardiogram is fully defined by a sequence of positive integers a₁, a₂, ..., a_n.

Your task is to paint a cardiogram by given sequence a_i.

Input

The first line contains integer n (2 ≤ n ≤ 1000). The next line contains the sequence of integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 1000). It is guaranteed that the sum of all a_i doesn't exceed 1000.

Output

Print max |y_i - y_j| lines (where y_k is the y coordinate of the k-th point of the polyline), in each line print characters. Each character must equal either « / » (slash), « » (backslash), « » (space). The printed image must be the image of the given polyline. Please study the test samples for better understanding of how to print a cardiogram.

Note that in this problem the checker checks your answer taking spaces into consideration. Do not print any extra characters. Remember that the wrong answer to the first pretest doesn't give you a penalty.

Sample test(s) Input

5
3 1 2 5 1

Output

      /      
   /  /       
  /          
 /           
           / 

Input

3
1 5 1

Output

 /      
      
      
      
      / 

Note

Due to the technical reasons the answers for the samples cannot be copied from the statement. We've attached two text documents with the answers below.

http://assets.codeforces.com/rounds/435/1.txt

http://assets.codeforces.com/rounds/435/2.txt

 

題目大意：這題意著實醒神。。。給一個數列，按其順序一上一下打印圖形

題目分析：因為還好ai最大是1000，可以用一個2000*2000的矩陣存起來，然後就模擬吧，注意動態取豎直方向的最大最小值，沒想到cf還有這樣的題

 

#include 
#include 
#include 
using namespace std;
char g[2005][2005];

int main()
{
    int n;
    scanf(%d, &n);
    int sign = 1;
    int maxy = 1000, miny = 1000;
    int x = -1, y = 1000;
    memset(g, 0, sizeof(g));
    while(n--)
    {
        int a;
        scanf(%d, &a);
        if(sign == 1)
            y --;
        else
            y ++;
        for(int i = 1; i <= a; i++)
        {
            if(sign == 1)
            {
                y ++;
                x ++;
                g[x][y] = '/';
            }
            else
            {
                y --;
                x ++;
                g[x][y] = '\';
            }
        }www.Bkjia.com
        maxy = max(maxy, y);
        miny = min(miny, y);
        sign *= -1;
    }
    for(int i = 0; i <= x; i++)
        for(int j = miny; j <= maxy; j++)
            if(!g[i][j])
                g[i][j] = ' ';
            int cnt =0 ;
    for(int j = maxy; j >= miny; j--)
    {
        for(int i = 0; i <= x; i++)
            printf(%c, g[i][j]);
        printf(
);
    }
}

 

 

 

 

D. Special Grid time limit per test：4 seconds memory limit per test：256 megabytes

You are given an n × m grid, some of its nodes are black, the others are white. Moreover, it's not an ordinary grid — each unit square of the grid has painted diagonals.

The figure below is an example of such grid of size 3 × 5. Four nodes of this grid are black, the other 11 nodes are white.

Your task is to count the number of such triangles on the given grid that:

the corners match the white nodes, and the area is positive; all sides go along the grid lines (horizontal, vertical or diagonal); no side contains black nodes. Input

The first line contains two integers n and m (2 ≤ n, m ≤ 400). Each of the following n lines contain m characters (zeros and ones) — the description of the grid. If the j-th character in the i-th line equals zero, then the node on the i-th horizontal line and on the j-th vertical line is painted white. Otherwise, the node is painted black.

The horizontal lines are numbered starting from one from top to bottom, the vertical lines are numbered starting from one from left to right.

Output

Print a single integer — the number of required triangles.

Sample test(s) Input

3 5
10000
10010
00001

Output

20

Input

2 2
00
00

Output

4

Input

2 2
11
11

Output

0

Note

The figure below shows red and blue triangles. They are the examples of the required triangles in the first sample. One of the invalid triangles is painted green. It is invalid because not all sides go along the grid lines.

 

 

題目大意：給個0/1矩陣，0的地方可以相互連接，問矩陣中共有多少個三角形，注意三角形的邊必須是垂直水平或者斜45度的

題目分析：做的特別糾結的一題，根據題意顯然所有三角形都是直角三角形，所以可以直接枚舉直角來做，我說下我的做法吧。。。

我是枚舉邊做的，首先預處理出每個點往其周圍的8個方向可以延伸的最遠距離（距離及點數），用dp[i][j][0-7]表示，然後分成兩種情況，第一種是只有一個邊是斜45度方向的，枚舉全部情況，注意這種情況我是按45度角枚舉的，所以最後要除2，然後是有兩條斜45度方向邊的情況，這種情況是按90度枚舉的，所以不會重復，其實直接全部枚舉直角就可以了，我做的時候調來調去給調亂了，就搞成了這樣

 

 

#include 
#include 
#include 
using namespace std;
int const MAX = 405;
int dp[MAX][MAX][8], g[MAX][MAX];
char s[MAX][MAX];

int main()
{
    int n, m;
    scanf(%d %d, &n, &m);
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++)
    {   
        scanf(%s, s[i] + 1);
        for(int j = 1; j <= m; j++)
        {
            g[i][j] = s[i][j] - '0';
            if(!g[i][j])
                for(int k = 0; k < 8; k++)
                    dp[i][j][k] = 1;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(dp[i - 1][j][0] && dp[i][j][0])
                dp[i][j][0] += dp[i - 1][j][0];
            if(dp[i - 1][j - 1][7] && dp[i][j][7])
                dp[i][j][7] += dp[i - 1][j - 1][7];
            if(dp[i][j - 1][6] && dp[i][j][6])
                dp[i][j][6] += dp[i][j - 1][6];
        }
        for(int j = m; j >= 1; j--)
        {
            if(dp[i - 1][j + 1][1] && dp[i][j][1])
                dp[i][j][1] += dp[i - 1][j + 1][1];
            if(dp[i][j + 1][2] && dp[i][j][2])
                dp[i][j][2] += dp[i][j + 1][2];
        }
    }
    for(int i = n; i >= 1; i--)
    {
        for(int j = 1; j <= m; j++)
        {
            if(dp[i + 1][j][4] && dp[i][j][4])
                dp[i][j][4] += dp[i + 1][j][4];
            if(dp[i + 1][j - 1][5] && dp[i][j][5])
                dp[i][j][5] += dp[i + 1][j - 1][5];
        }
        for(int j = m; j >= 1; j--)
        {
            if(dp[i + 1][j + 1][3] && dp[i][j][3])
                dp[i][j][3] += dp[i + 1][j + 1][3];
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 0; k < 8; k++)
                dp[i][j][k] -= 1;
    int ans1 = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            for(int k = 1; k <= max(n, m); k++)
            {
                if(dp[i][j][0] >= k && dp[i][j][7] >= k && i - k >= 1 && dp[i - k][j][6] >= k)
                    ans1 ++;
                if(dp[i][j][0] >= k && dp[i][j][1] >= k && i - k >= 1 && dp[i - k][j][2] >= k)
                    ans1 ++;
                if(dp[i][j][2] >= k && dp[i][j][1] >= k && j + k <= m && dp[i][j + k][0] >= k)
                    ans1 ++;
                if(dp[i][j][2] >= k && dp[i][j][3] >= k && j + k <= m && dp[i][j + k][4] >= k)
                    ans1 ++;
                if(dp[i][j][4] >= k && dp[i][j][3] >= k && i + k <= n && dp[i + k][j][2] >= k)
                    ans1 ++;
                if(dp[i][j][4] >= k && dp[i][j][5] >= k && i + k <= n && dp[i + k][j][6] >= k)
                    ans1 ++;
                if(dp[i][j][6] >= k && dp[i][j][5] >= k && j - k >= 1 && dp[i][j - k][4] >= k)
                    ans1 ++;
                if(dp[i][j][6] >= k && dp[i][j][7] >= k && j - k >= 1 && dp[i][j - k][0] >= k)
                    ans1 ++;
            }
        }
    }
    ans1 /= 2;
    int ans2 = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            for(int k = 1; k <= max(n, m); k++)
            {

                if(dp[i][j][1] >= k && dp[i][j][3] >= k && i - k >= 1 && j + k <= m && dp[i - k][j + k][4] >= 2 * k)
                    ans2 ++;
                if(dp[i][j][5] >= k && dp[i][j][3] >= k && i + k <= n && j - k >= 1 && dp[i + k][j - k][2] >= 2 * k)
                    ans2 ++;
                if(dp[i][j][5] >= k && dp[i][j][7] >= k && i - k >= 1 && j - k >= 1 && dp[i - k][j - k][4] >= 2 * k)
                    ans2 ++;
                if(dp[i][j][1] >= k && dp[i][j][7] >= k && i - k >= 1 && j - k >= 1 && dp[i - k][j - k][2] >= 2 * k)
                    ans2 ++;
            }
        }
    }
    printf(%d
, ans1 + ans2);
}