## Codeforces Round #261 (Div. 2)

2017年12月16日 ⁄ 综合 ⁄ 共 6990字 ⁄ 字号 评论关闭

A，B两题就不写了。。。

C. Pashmak and Buses
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Pashmak has been employed in a transportation company. The company has k buses and has a contract with a school which has n students.
The school planned to take the students to d different places for d days
(each day in one place). Each day the company provides all the buses for the trip. Pashmak has to arrange the students in the buses. He wants to arrange the students in a way that no two students become close friends. In his ridiculous idea, two students will
become close friends if and only if they are in the same buses for all d days.

Input

The first line of input contains three space-separated integers n, k, d (1 ≤ n, d ≤ 1000; 1 ≤ k ≤ 109).

Output

If there is no valid arrangement just print -1. Otherwise print d lines,
in each of them print n integers. The j-th integer
of the i-th line shows which bus the j-th student
has to take on the i-th day. You can assume that the buses are numbered from 1 to k.

Sample test(s)
input
```3 2 2
```
output
```1 1 2
1 2 1
```
input
```3 2 1
```
output
```-1
```
Note

Note that two students become close friends only if they share a bus each day. But the bus they share can differ from day to day.

```#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
const int N=1100;
char arr[N][N];
int n,k,d;
int main()
{
while(cin>>n>>k>>d)
{
if(k==1)
{
if(d>1)
{
if(n>1)
cout<<-1<<endl;
else
{
for(int i=0;i<d;i++)
cout<<1<<endl;
}
}
else
{
if(n==1)
{
cout<<1<<endl;
}
else
cout<<-1<<endl;
}
}
else
{
if(d==1)
{
if(k<n)
cout<<-1<<endl;
else
{
for(int i=1;i<=n;i++)
cout<<i<<" ";
cout<<endl;
}
continue;
}
string s = "";
for(int i=0;i<d;i++)
s+="1";
bool flag = true;
int j=1;
for(;j<=n;j++)
{
for(int i=1;i<=d;i++)
{
arr[i][j] = s[i-1];
}
int end = s.length()-1;
char c = '9';
if(k>9)
c = '9';
else
c = k+'0';
while(end>=0&&s[end]==c)
end--;
if(end==-1)
{
flag=false;
break;
}
else
{
int p = (s[end]-'0') +1;
s[end] = (char)(p+'0');
end++;
while(end<s.length())
s[end++] = '1';
}
}
if(!flag&&j<n)
{
cout<<-1<<endl;
continue;
}
for(int i=1;i<=d;i++)
{
for(int j=1;j<=n;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
}
return 0;
}```

D. Pashmak and Parmida's problem
time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence a that consists of n integers a1, a2, ..., an.
Let's denote f(l, r, x) the number of indices k such
that: l ≤ k ≤ r andak = x.
His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such
that f(1, i, ai) > f(j, n, aj).

Help Pashmak with the test.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 106).
The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a single integer — the answer to the problem.

Sample test(s)
input
```7
1 2 1 1 2 2 1
```
output
```8
```
input
```3
1 1 1
```
output
```1
```
input
```5
1 2 3 4 5
```
output
```0
```

```#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
const int N=2000000;
int arr[N];
int temp1[N];
int temp2[N];
#define mid (l+r)/2

typedef long long ll;
int n;
ll solve(int l,int r)
{
if(l>=r)
return 0;
if(l==r-1)
{
if(temp1[l]>temp2[r])
return 1;
else
return 0;
}
ll ret1 = solve(l,mid);
ll ret2 = solve(mid+1,r);
vector<int> v1;
vector<int> v2;
for(int i=l;i<=mid;i++)
v1.push_back(temp1[i]);
for(int i=mid+1;i<=r;i++)
v2.push_back(temp2[i]);
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end(),greater<int>());
int start1 = 0;
int start2 = v2.size()-1;
while(start1<v1.size()&&v1[start1]<=v2[start2])
start1++;
ll ret = ret1+ret2;
while(start1<v1.size())
{
while(v1[start1]>v2[start2]&&start2>=0)
start2--;
ret+=(v2.size()-1-start2);
start1++;
}
return ret;
}
int main()
{
cin>>n;
map<int,int> m1;
map<int,int> mn;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
m1[arr[i]]++;
temp1[i] = m1[arr[i]];
}
for(int i=n;i>=1;i--)
{
mn[arr[i]]++;
temp2[i] = mn[arr[i]];
}
ll ret = 0;
ret = solve(1,n);
cout<<ret<<endl;

return 0;
}```

E. Pashmak and Graph
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Pashmak's homework is a problem about graphs. Although he always tries to do his homework completely, he can't solve this problem. As you know, he's really weak at graph theory; so try to help him in solving the problem.

You are given a weighted directed graph with n vertices and m edges.
You need to find a path (perhaps, non-simple) with maximum number of edges, such that the weights of the edges increase along the path. In other words, each edge of the path must have strictly greater weight than the previous edge in the path.

Help Pashmak, print the number of edges in the required path.

Input

The first line contains two integers nm (2 ≤ n ≤ 3·105; 1 ≤ m ≤ min(n·(n - 1), 3·105)).
Then, m lines follows. The i-th line contains three
space separated integers: uiviwi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105) which
indicates that there's a directed edge with weight wifrom
vertex ui to
vertex vi.

It's guaranteed that the graph doesn't contain self-loops and multiple edges.

Output

Print a single integer — the answer to the problem.

Sample test(s)
input
```3 3
1 2 1
2 3 1
3 1 1
```
output
```1
```
input
```3 3
1 2 1
2 3 2
3 1 3
```
output
```3
```
input
```6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4
```
output
```6
```
Note

In the first sample the maximum trail can be any of this trails: .

In the second sample the maximum trail is .

In the third sample the maximum trail is .

```#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
const int N=410000;
int n,m;
struct edge
{
int from;
int to;
int weight;
}edges[N];
bool cmp(edge e1,edge e2)
{
return e1.weight<e2.weight;
}
int dp[N];
int f[N];
int main()
{
while(cin>>n>>m)
{
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
for(int i=0;i<m;i++)
{
cin>>edges[i].from>>edges[i].to>>edges[i].weight;
}
sort(edges,edges+m,cmp);
for(int i=0;i<m;i++)
{
int j=i;
while(j<m&&edges[j].weight==edges[i].weight)
j++;
for(int k=i;k<j;k++)
{
f[edges[k].to] = max(f[edges[k].to],dp[edges[k].from]+1);
}
for(int k=i;k<j;k++)
dp[edges[k].to] = f[edges[k].to];
i = j-1;
}
int ans = 0;
for(int i=1;i<=n;i++)
ans = max(ans,dp[i]);
cout<<ans<<endl;
}
return 0;
}```