Codeforces Round #358 (Div. 2) A B C D - dblank

# Codeforces Round #358 (Div. 2) A B C D

<h2>A. Alyona and Numbers</h2>
<div>

After finishing eating her bun, Alyona came up with two integers <span class="tex-span">n</span> and <span class="tex-span">m</span>. She decided to write down two columns of integers — the first column containing integers from <span class="tex-span">1</span> to <span class="tex-span">n</span> and the second containing integers from <span class="tex-span">1</span> to <span class="tex-span">m</span>. Now the girl wants to count how many pairs of integers she can choose, one from the first column and the other from the second column, such that their sum is divisible by <span class="tex-span">5</span>.

Formally, Alyona wants to count the number of pairs of integers <span class="tex-span">(x, y)</span> such that <span class="tex-span">1 ≤ x ≤ n</span>, <span class="tex-span">1 ≤ y ≤ m</span> and equals <span class="tex-span">0</span>.

As usual, Alyona has some troubles and asks you to help.

</div>
<div class="input-specification">
<div class="section-title">Input</div>
The only line of the input contains two integers <span class="tex-span">n</span> and <span class="tex-span">m</span> (<span class="tex-span">1 ≤ n, m ≤ 1 000 000</span>).

</div>
<div class="output-specification">
<div class="section-title">Output</div>
Print the only integer — the number of pairs of integers <span class="tex-span">(x, y)</span> such that <span class="tex-span">1 ≤ x ≤ n</span>, <span class="tex-span">1 ≤ y ≤ m</span> and <span class="tex-span">(x + y)</span> is divisible by <span class="tex-span">5</span>.

</div>
<div class="sample-tests">
<div class="section-title">题意:给你一个n和m，你有多少对满足1<=x<=n和1<=y<=m并且(x+y)%5==0的 数对.</div>
<div class="section-title">思路:因为n和m很大所以不能循环，我们可以枚举x，对于一个一定是((y%5）+ (x%5))%5==0,于是可以得对于每一个x,都有(m+(x%5))/5个对应的y。</div>
<div class="section-title">代码:</div>
<div class="section-title">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 3e1 + 10, Mod = 1000000007;
typedef long long ll;
int main()
{
ll ans = 0;
int n, m;
while(cin>>n>>m)
{
ans = 0;
for(int i = 1; i<=n; i++)
{
ans += (m+(i%5))/5;
}
cout<<ans<<endl;
}
return 0;
}

<h2>B. Alyona and Mex</h2>
<div>

Someone gave Alyona an array containing <span class="tex-span">n</span> positive integers <span class="tex-span">a1, a2, ..., an</span>. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of <span class="tex-span">n</span> positive integers <span class="tex-span">b1, b2, ..., bn</span> such that <span class="tex-span">1 ≤ bi ≤ ai</span> for every<span class="tex-span">1 ≤ i ≤ n</span>. Your task is to determine the maximum possible value of mex of this array.

<span class="tex-font-style-it">Mex</span> of an array in this problem is the <span class="tex-font-style-bf">minimum positive</span> integer that doesn't appear in this array. For example, mex of the array containing <span class="tex-span">1</span>, <span class="tex-span">3</span> and <span class="tex-span">4</span> is equal to <span class="tex-span">2</span>, while mex of the array containing <span class="tex-span">2</span>, <span class="tex-span">3</span> and <span class="tex-span">2</span> is equal to <span class="tex-span">1</span>.

</div>
<div class="input-specification">
<div class="section-title">Input</div>
The first line of the input contains a single integer <span class="tex-span">n</span> (<span class="tex-span">1 ≤ n ≤ 100 000</span>) — the number of elements in the Alyona's array.

The second line of the input contains <span class="tex-span">n</span> integers <span class="tex-span">a1, a2, ..., an</span> (<span class="tex-span">1 ≤ ai ≤ 109</span>) — the elements of the array.

</div>
<div class="output-specification">
<div class="section-title">Output</div>
Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 1000000007;
typedef long long ll;
int a[N];
int main()
{
int n;
while(cin>>n)
{
for(int i = 0; i<n; i++)
scanf("%d", &a[i]);
sort(a, a+n);
int k = 1;
for(int i = 0; i<n; i++)
{
if(a[i] >= k)
k++;
}
cout<<k<<endl;
}
return 0;
}

<h2>C. Alyona and the Tree</h2>
<div>

Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex <span class="tex-span">1</span>, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are <span class="tex-font-style-it">sad</span>, so she decided to play with them. Let's call vertex <span class="tex-span">v</span> <span class="tex-font-style-it">sad</span> if there is a vertex <span class="tex-span">u</span> in subtree of vertex <span class="tex-span">v</span> such that <span class="tex-span">dist(v, u) > au</span>, where <span class="tex-span">au</span> is the number written on vertex <span class="tex-span">u</span>, <span class="tex-span">dist(v, u)</span> is the sum of the numbers written on the edges on the path from <span class="tex-span">v</span> to <span class="tex-span">u</span>.

<span class="tex-font-style-it">Leaves</span> of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a <span class="tex-font-style-it">leaf</span> if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

</div>
<div class="input-specification">
<div class="section-title">Input</div>
In the first line of the input integer <span class="tex-span">n</span> (<span class="tex-span">1 ≤ n ≤ 105</span>) is given — the number of vertices in the tree.

In the second line the sequence of <span class="tex-span">n</span> integers <span class="tex-span">a1, a2, ..., an</span> (<span class="tex-span">1 ≤ ai ≤ 109</span>) is given, where <span class="tex-span">ai</span> is the number written on vertex <span class="tex-span">i</span>.

The next <span class="tex-span">n - 1</span> lines describe tree edges: <span class="tex-span">ith</span> of them consists of two integers <span class="tex-span">pi</span> and <span class="tex-span">ci</span> <span class="tex-span">(1 ≤ pi ≤ n</span>, <span class="tex-span"> - 109 ≤ ci ≤ 109)</span>, meaning that there is an edge connecting vertices <span class="tex-span">i + 1</span> and <span class="tex-span">pi</span> with number <span class="tex-span">ci</span> written on it.

</div>
<div class="output-specification">
<div class="section-title">Output</div>
<div class="section-title">Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.</div>
<div class="section-title">代码:</div>
<div class="section-title">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 1000000007;
typedef long long ll;
int a[N], n, ans, vis[N];
struct node
{
int to, x;
};
vector<node> path[N];
ll dp[N];
void bfs(int fa)
{
int x, y;
queue<int>q;
q.push(fa);
memset(vis, 0, sizeof(vis));
vis[fa] = 1;
ans = 1;
memset(dp, 0, sizeof(dp));
while(!q.empty())
{
x = q.front();
q.pop();
for(int i = 0, sz = path[x].size(); i<sz; i++)
{
y = pathx.to;
if(!vis[y])
{
dp[y] = max(dp[x] + pathx.x, dp[y]);
if(dp[y] > a[y])
continue;
q.push(y);
++ans;
vis[y] = 1;
}
}
}
}
int main()
{
while(~scanf("%d", &n))
{
ans = 0;
for(int i = 1; i<=n; i++)
path[i].clear();
for(int i = 1; i<=n; i++)
scanf("%d", &a[i]);
int u, v;
node in;
for(int i = 1; i<n; i++)
{
scanf("%d%d", &u, &v);
in.to = i+1;
in.x = v;
path[u].push_back(in);
in.to = u;
path[i+1].push_back(in);
}
bfs(1);
cout<<n-ans<<endl;
}
return 0;
}

<h2>D. Alyona and Strings</h2>
<div>

After returned from forest, Alyona started reading a book. She noticed strings <span class="tex-span">s</span> and <span class="tex-span">t</span>, lengths of which are <span class="tex-span">n</span> and <span class="tex-span">m</span> respectively. As usual, reading bored Alyona and she decided to pay her attention to strings <span class="tex-span">s</span> and <span class="tex-span">t</span>, which she considered very similar.

Alyona has her favourite positive integer <span class="tex-span">k</span> and because she is too small, <span class="tex-span">k</span> does not exceed <span class="tex-span">10</span>. The girl wants now to choose <span class="tex-span">k</span> disjoint non-empty substrings of string <span class="tex-span">s</span> such that these strings appear as disjoint substrings of string <span class="tex-span">t</span> and in the same order as they do in string <span class="tex-span">s</span>. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of <span class="tex-span">k</span> non-empty strings <span class="tex-span">p1, p2, p3, ..., pk</span> satisfying following conditions:

• <span class="tex-span">s</span> can be represented as concatenation <span class="tex-span">a1p1a2p2... akpkak + 1</span>, where <span class="tex-span">a1, a2, ..., ak + 1</span> is a sequence of arbitrary strings (some of them may be possibly empty);
• <span class="tex-span">t</span> can be represented as concatenation <span class="tex-span">b1p1b2p2... bkpkbk + 1</span>, where <span class="tex-span">b1, b2, ..., bk + 1</span> is a sequence of arbitrary strings (some of them may be possibly empty);
• sum of the lengths of strings in sequence is maximum possible.

Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A <span class="tex-font-style-it">substring</span> of a string is a subsequence of consecutive characters of the string.

</div>
<div class="input-specification">
<div class="section-title">Input</div>
In the first line of the input three integers <span class="tex-span">n</span>, <span class="tex-span">m</span>, <span class="tex-span">k</span> (<span class="tex-span">1 ≤ n, m ≤ 1000</span>, <span class="tex-span">1 ≤ k ≤ 10</span>) are given — the length of the string <span class="tex-span">s</span>, the length of the string <span class="tex-span">t</span> and Alyona's favourite number respectively.

The second line of the input contains string <span class="tex-span">s</span>, consisting of lowercase English letters.

The third line of the input contains string <span class="tex-span">t</span>, consisting of lowercase English letters.

</div>
<div class="output-specification">
<div class="section-title">Output</div>
In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

<span class="tex-font-style-bf">It is guaranteed</span>, that at least one desired sequence exists.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 1000000007;
typedef long long ll;
char s[N], t[N];
int dpN, ansN[12];
int main()
{
int n, m, k;
while(cin>>n>>m>>k)
{
scanf("%s", s+1);
scanf("%s", t+1);
memset(dp, 0, sizeof(dp));
memset(ans, 0, sizeof(ans));
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
{
if(s[i] == t[j])
dpi = dpi-1 + 1;
}
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
for(int r = 1; r<=k; r++)
{
ansi[r] = max(ansi[r], ansi-1[r]);
if(dpi)
ansi[r] = max(ansi[r],
ansi-dp[i]j-dp[i][r-1] + dpi);
}
cout<<ansn[k]<<endl;
}
return 0;
}


</div>
</div>
</div>
</div>
</div>
</div>