CodeforcesRound#256(Div.2)題解

Problem A: A. Rewards time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Bizon the Champion is called the Champion for a reason. Bizon the Champion has recently got a present — a n

Problem A:

A. Rewards

time limit per test

memory limit per test

input

output

Bizon the Champion is called the Champion for a reason.

Bizon the Champion has recently got a present — a new glass cupboard with n shelves and he decided to put all his presents there. All the presents can be divided into two types: medals and cups. Bizon the Champion has a₁ first prize cups, a₂ second prize cups and a₃third prize cups. Besides, he has b₁ first prize medals, b₂ second prize medals and b₃ third prize medals.

Naturally, the rewards in the cupboard must look good, that's why Bizon the Champion decided to follow the rules:

Help Bizon the Champion find out if we can put all the rewards so that all the conditions are fulfilled.

Input

The first line contains integers a₁, a₂ and a₃ (0?≤?a₁,?a₂,?a₃?≤?100). The second line contains integers b₁, b₂ and b₃ (0?≤?b₁,?b₂,?b₃?≤?100). The third line contains integer n (1?≤?n?≤?100).

The numbers in the lines are separated by single spaces.

Output

Print "YES" (without the quotes) if all the rewards can be put on the shelves in the described manner. Otherwise, print "NO" (without the quotes).

Sample test(s)

input

1 1 1
1 1 1
4

output

YES

input

1 1 3
2 3 4
2

output

YES

input

1 0 0
1 0 0
1

output

NO

解題思路：

求出放置所有獎杯和獎牌需要的最少架子的數目num，和n進行比較。

代碼：

#include 
#include 

int main()
{
 int a1, a2, a3, b1, b2, b3, n;
 scanf("%d%d%d%d%d%d%d", &a1, &a2, &a3, &b1, &b2, &b3, &n);
 int num = ceil((a1 + a2 + a3) * 1.0 / 5) + ceil((b1 + b2 + b3) * 1.0 / 10);
 printf("%s\n", num <= n ? "YES" : "NO");
 return 0;
}

Problem B:

B. Suffix Structures

time limit per test

memory limit per test

input

output

Bizon the Champion isn't just a bison. He also is a favorite of the "Bizons" team.

At a competition the "Bizons" got the following problem: "You are given two distinct words (strings of English letters), s and t. You need to transform word s into word t". The task looked simple to the guys because they know the suffix data structures well. Bizon Senior loves suffix automaton. By applying it once to a string, he can remove from this string any single character. Bizon Middle knows suffix array well. By applying it once to a string, he can swap any two characters of this string. The guys do not know anything about the suffix tree, but it can help them do much more.

Bizon the Champion wonders whether the "Bizons" can solve the problem. Perhaps, the solution do not require both data structures. Find out whether the guys can solve the problem and if they can, how do they do it? Can they solve it either only with use of suffix automaton or only with use of suffix array or they need both structures? Note that any structure may be used an unlimited number of times, the structures may be used in any order.

Input

The first line contains a non-empty word s. The second line contains a non-empty word t. Words s and t are different. Each word consists only of lowercase English letters. Each word contains at most 100 letters.

Output

In the single line print the answer to the problem. Print "need tree" (without the quotes) if word s cannot be transformed into word teven with use of both suffix array and suffix automaton. Print "automaton" (without the quotes) if you need only the suffix automaton to solve the problem. Print "array" (without the quotes) if you need only the suffix array to solve the problem. Print "both" (without the quotes), if you need both data structures to solve the problem.

It's guaranteed that if you can solve the problem only with use of suffix array, then it is impossible to solve it only with use of suffix automaton. This is also true for suffix automaton.

Sample test(s)

input

automaton
tomat

output

automaton

input

array
arary

output

array

input

both
hot

output

both

input

need
tree

output

need tree

解題思路：

如果串A中包含串B的所有字母，并且這些字母在串A和串B中排列順序相同，輸出“automaton”，否則，如果串A中包含串B的所有字母，我們在這種情況下在進行討論，如果A和B的長度相等，輸出“array”，如果A比B長，輸出“both”，否則輸出“need tree”。

代碼：

#include 
#include 
#include 
using namespace std;

const int MAXN = 105;
int vis[MAXN];

bool cmpa(string stra, string strb)
{
 memset(vis, 0, sizeof(vis));
 int lena = stra.length();
 int lenb = strb.length();
 int k = 0;
 for(int i = 0; i < lenb; i++)
 {
 bool flag = true;
 for(int j = k; j < lena; j++)
 {
 if(!vis[j] && strb[i] == stra[j])
 {
 vis[j] = 1;
 k = j + 1;
 flag = false;
 break;
 }
 }
 if(flag) return false;
 }
 return true;
}

bool cmpb(string stra, string strb)
{
 memset(vis, 0, sizeof(vis));
 int lena = stra.length();
 int lenb = strb.length();
 for(int i = 0; i < lenb; i++)
 {
 bool flag = true;
 for(int j = 0; j < lena; j++)
 {
 if(!vis[j] && strb[i] == stra[j])
 {
 vis[j] = 1;
 flag = false;
 break;
 }
 }
 if(flag) return false;
 }
 return true;
}

int main()
{
 string stra, strb;
 cin >> stra >> strb;
 int lena = stra.length();
 int lenb = strb.length();
 if(cmpa(stra, strb))
 {
 cout << "automaton" << endl;
 }
 else if(cmpb(stra, strb))
 {
 if(lena == lenb)
 {
 cout << "array" << endl;
 }
 else if(lena > lenb)
 {
 cout << "both" << endl;
 }
 else
 {
 cout << "need tree" << endl;
 }
 }
 else
 {
 cout << "need tree" << endl;
 }
 return 0;
}

Problem C:

C. Painting Fence

time limit per test

memory limit per test

input

output

Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of a_i meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.

Input

The first line contains integer n (1?≤?n?≤?5000) — the number of fence planks. The second line contains n space-separated integersa₁,?a₂,?...,?a_n (1?≤?a_i?≤?10⁹).

Output

Print a single integer — the minimum number of strokes needed to paint the whole fence.

Sample test(s)

input

5
2 2 1 2 1

output

3

input

2
2 2

output

2

input

1
5

output

1

解題思路：

遞歸，貪心。粉刷籬笆，我們可以水平方向粉刷（只能刷到連續的部分），也可以豎直方向粉刷。按水平方向粉刷的話，刷的最少次數是min(a1,a2,a3,...,an-1)；按豎直方向刷的話最少次數是這段連續籬笆的長度n。按上述方式刷完之后，必然會產生高度為0的籬笆（被全部刷過了），我們把這樣的籬笆作為分割點，分成左半部分，和右半部分，兩部分各是一段連續的籬笆，依次類推。

一個錯誤的思路：每次刷的時候找所有籬笆高度的最大值h，和最長的連續籬笆的長度len，刷的時候取max（h，len），最多刷n次，算法復雜度O(n2)。這樣做的話，可能會使得籬笆變得分散，導致最終粉刷的次數變多。

反例：

3
1 10 1

錯誤的代碼：

 #include 
 #include 
 using namespace std;

 const int MAXN = 5010;
 int n, ans = 0, a[MAXN];

 int main()
 {
 scanf("%d", &n);
 for(int i = 0; i < n; i++)
 {
 scanf("%d", &a[i]);
 }
 while(true)
 {
 int maxv = *max_element(a, a + n);
 int maxh = -1, tmp = 0, first = 1;
 int s = 0, t = 0, ts = 0, tt = 0;
 for(int i = 0; i < n; i++)
 {
 if(a[i])
 {
 if(first)
 {
 ts = i;
 first = 0;
 }
 tt = i;
 tmp++;
 if(i == n - 1)
 {
 if(tmp > maxh)
 {
 maxh = tmp;
 s = ts;
 t = tt;
 }
 }
 }
 else
 {
 if(tmp > maxh)
 {
 maxh = tmp;
 s = ts;
 t = tt;
 }
 tmp = 0;
 first = 1;
 }
 }
 if(maxv > maxh)
 {
 *max_element(a, a + n) = 0;
 }
 else
 {
 for(int i = s; i <= t; i++)
 {
 a[i]--;
 }
 }
 ans++;
 if(0 == *max_element(a, a + n)) break;
 }
 printf("%d\n", ans);
 return 0;
 }

代碼：

#include 
#include 
using namespace std;

const int MAXN = 5010;
int n, a[MAXN];

int solve(int l, int r)
{
 if(l > r) return 0;
 int minh = *min_element(a + l, a + r + 1);
 int ret = r - l + 1, tot = minh;
 if(ret < minh)
 {
 for(int i = l; i <= r; i++)
 a[i] = 0;
 return ret;
 }
 else
 {
 for(int i = l; i <= r; i++)
 a[i] -= minh;
 int t = min_element(a + l, a + r + 1) - a;
 tot += solve(l, t - 1) + solve(t + 1, r);
 }
 return min(ret, tot);
}

int main()
{
 scanf("%d", &n);
 for(int i = 0; i < n; i++)
 scanf("%d", &a[i]);
 printf("%d\n", solve(0, n - 1));
 return 0;
}

Problem D:

D. Multiplication Table

time limit per test

memory limit per test

input

output

Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann?×?m multiplication table, where the element on the interdiv of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.

Input

The single line contains integers n, m and k (1?≤?n,?m?≤?5·10⁵; 1?≤?k?≤?n·m).

Output

Print the k-th largest number in a n?×?m multiplication table.

Sample test(s)

input

2 2 2

output

2

input

2 3 4

output

3

input

1 10 5

output

5

解題思路:

二分。需要求的是n*m乘法表中第k大的數，我們可以對這個數ans進行二分查找，區間是[1, n * m]，對于每一個可能的ans，我們求出比他小的數的個數sum += min((mid - 1) / i, m);(i = 1,2,3,..,n)，記錄下小于k的最大的mid，即為我們所求的ans。

代碼：

#include 

inline long long min(long long a, int b)
{
 if(a < b) return a;
 return b;
}

int main()
{
 int n, m;
 long long k, ans, l, r, sum, mid;
 scanf("%d%d%I64d", &n, &m, &k);
 l = 1, r = 1ll * n * m;//r = (long long)n * m;
 while(l <= r)
 {
 mid = (l + r) >> 1;
 sum = 0;
 for(int i = 1; i <= n; i++)
 sum += min((mid - 1) / i, m);
 if(sum < k)
 l = mid + 1, ans = mid;
 else
 r = mid - 1;
 }
 printf("%I64d\n", ans);
 return 0;
}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com