1 second
256 megabytes
standard input
standard output
There are n students who have taken part in an olympiad. Now it's time to award the students.
Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Students with diplomas and certificates are called winners. But there are some rules of counting the number of diplomas and certificates. The number of certificates must be exactly k times greater than the number of diplomas. The number of winners must not be greater than half of the number of all students (i.e. not be greater than half of n). It's possible that there are no winners.
You have to identify the maximum possible number of winners, according to these rules. Also for this case you have to calculate the number of students with diplomas, the number of students with certificates and the number of students who are not winners.
The first (and the only) line of input contains two integers n and k (1 ≤ n, k ≤ 1012), where n is the number of students and k is the ratio between the number of certificates and the number of diplomas.
Output three numbers: the number of students with diplomas, the number of students with certificates and the number of students who are not winners in case when the number of winners is maximum possible.
It's possible that there are no winners.
18 2
3 6 9
9 10
0 0 9
1000000000000 5
83333333333 416666666665 500000000002
1000000000000 499999999999
1 499999999999 500000000000
题意：
题解：水
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
ll n,k;
int main()
{
scanf("%I64d %I64d",&n,&k);
ll now=n//(+k);
printf("%I64d %I64d %I64d",now,now*k,n-(+k)*now);
return ;
}
1 second
256 megabytes
standard input
standard output
n children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation a1, a2, ..., an of length n. It is an integer sequence such that each integer from 1 to n appears exactly once in it.
The game consists of m steps. On each step the current leader with index i counts out ai people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.
You are given numbers l1, l2, ..., lm — indices of leaders in the beginning of each step. Child with number l1 is the first leader in the game.
Write a program which will restore a possible permutation a1, a2, ..., an. If there are multiple solutions then print any of them. If there is no solution then print -1.
The first line contains two integer numbers n, m (1 ≤ n, m ≤ 100).
The second line contains m integer numbers l1, l2, ..., lm (1 ≤ li ≤ n) — indices of leaders in the beginning of each step.
Print such permutation of n numbers a1, a2, ..., an that leaders in the game will be exactly l1, l2, ..., lm if all the rules are followed. If there are multiple solutions print any of them.
If there is no permutation which satisfies all described conditions print -1.
4 5
2 3 1 4 4
3 1 2 4
3 3
3 1 2
-1
Let's follow leadership in the first example:
- Child 2 starts.
- Leadership goes from 2 to 2 + a2 = 3.
- Leadership goes from 3 to 3 + a3 = 5. As it's greater than 4, it's going in a circle to 1.
- Leadership goes from 1 to 1 + a1 = 4.
- Leadership goes from 4 to 4 + a4 = 8. Thus in circle it still remains at 4.
题意：(L[i]+a[L[i]]])modn=L[i+1] 求满足条件的a数组 a数组为 1~n
题解：stl乱搞 注意a数组为 1~n
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
int n,m;
int l[];
map<int,set< int > >mp;
map<int,int>s;
int main(){ scanf("%d %d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d",&l[i]);
for(int i=;i<m;i++)
{
if(l[i]<l[i+])
mp[l[i]].insert((l[i+]-l[i]));
else
mp[l[i]].insert((l[i+]-l[i]+n));
}
for(int i=;i<=n;i++)
{
if(mp[i].size()>)
{
printf("-1\n");
return ;
}
}
for(int i=;i<=n;i++)
{
if(mp[i].size()==)
{
int exm=*(mp[i].begin());
if(s[exm]==)
{
s[exm]=;
}
else
{
printf("-1\n");
return ;
}
}
}
for(int i=;i<=n;i++)
{
if(mp[i].size()==)
{
for(int j=;j<=n;j++)
{
if(s[j]==)
{
mp[i].insert(j);
s[j]=;
break;
}
}
}
}
for(int i=;i<=n;i++)
printf("%d ",*(mp[i].begin()));
return ;
}
1 second
256 megabytes
standard input
standard output
Yet another round on DecoForces is coming! Grandpa Maks wanted to participate in it but someone has stolen his precious sofa! And how can one perform well with such a major loss?
Fortunately, the thief had left a note for Grandpa Maks. This note got Maks to the sofa storehouse. Still he had no idea which sofa belongs to him as they all looked the same!
The storehouse is represented as matrix n × m. Every sofa takes two neighbouring by some side cells. No cell is covered by more than one sofa. There can be empty cells.
Sofa A is standing to the left of sofa B if there exist two such cells a and b that xa < xb, a is covered by A and b is covered by B. Sofa A is standing to the top of sofa B if there exist two such cells a and b that ya < yb, a is covered by A and b is covered by B. Right and bottom conditions are declared the same way.
Note that in all conditions A ≠ B. Also some sofa A can be both to the top of another sofa B and to the bottom of it. The same is for left and right conditions.
The note also stated that there are cntl sofas to the left of Grandpa Maks's sofa, cntr — to the right, cntt — to the top and cntb — to the bottom.
Grandpa Maks asks you to help him to identify his sofa. It is guaranteed that there is no more than one sofa of given conditions.
Output the number of Grandpa Maks's sofa. If there is no such sofa that all the conditions are met for it then output -1.
The first line contains one integer number d (1 ≤ d ≤ 105) — the number of sofas in the storehouse.
The second line contains two integer numbers n, m (1 ≤ n, m ≤ 105) — the size of the storehouse.
Next d lines contains four integer numbers x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — coordinates of the i-th sofa. It is guaranteed that cells (x1, y1) and (x2, y2) have common side, (x1, y1) ≠ (x2, y2) and no cell is covered by more than one sofa.
The last line contains four integer numbers cntl, cntr, cntt, cntb (0 ≤ cntl, cntr, cntt, cntb ≤ d - 1).
Print the number of the sofa for which all the conditions are met. Sofas are numbered 1 through d as given in input. If there is no such sofa then print -1.
2
3 2
3 1 3 2
1 2 2 2
1 0 0 1
1
3
10 10
1 2 1 1
5 5 6 5
6 4 5 4
2 1 2 0
2
2
2 2
2 1 1 1
1 2 2 2
1 0 0 0
-1
Let's consider the second example.
- The first sofa has 0 to its left, 2 sofas to its right ((1, 1) is to the left of both (5, 5) and (5, 4)), 0 to its top and 2 to its bottom (both 2nd and 3rd sofas are below).
- The second sofa has cntl = 2, cntr = 1, cntt = 2 and cntb = 0.
- The third sofa has cntl = 2, cntr = 1, cntt = 1 and cntb = 1.
So the second one corresponds to the given conditions.
In the third example
- The first sofa has cntl = 1, cntr = 1, cntt = 0 and cntb = 1.
- The second sofa has cntl = 1, cntr = 1, cntt = 1 and cntb = 0.
And there is no sofa with the set (1, 0, 0, 0) so the answer is -1.
题意：有一个n*m的矩阵 每个sofa占据两个格子 一个格子不会同时被两个sofa占据 现在在这个矩阵上有d个sofa 分别给你各个格子的坐标 同一sofa的两个格子相邻 现在你要选取一个sofa 使得它左 右 上 下的sofa的个数为cntl, cntr, cntt, cntb
题解：
注意 x为行 y为列 一开始就搞错了 所以下面的代码中的变量名不对应
xa < xb 左
xa >xb 右
Ya < Yb 上
Ya < Yb 下
左右 上下 分别求前缀 对每一个sofa O（1） 判断是否满足条件
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
int d;
int n,m;
int x1[],y1[];
int x2[],y2[];
int l[],r[];
int u[],dd[];
int suml[],sumr[];
int sumu[],sumdd[];
int b[];
int main()
{
scanf("%d",&d);
scanf("%d %d",&n,&m);
for(int i=;i<=d;i++){
scanf("%d %d %d %d",&x1[i],&y1[i],&x2[i],&y2[i]);
if(y1[i]==y2[i]){
l[y1[i]]++;
r[y2[i]]++;
if(x1[i]>x2[i]){
dd[x1[i]]++;
u[x2[i]]++;
}
else{
dd[x2[i]]++;
u[x1[i]]++;
}
}
if(x1[i]==x2[i]){
dd[x1[i]]++;
u[x2[i]]++;
if(y1[i]>y2[i]){
r[y1[i]]++;
l[y2[i]]++;
}
else{
r[y2[i]]++;
l[y1[i]]++;
}
}
}
for(int i=;i<=;i++)
scanf("%d",&b[i]);
suml[]=;
for(int i=;i<=m;i++)
suml[i]=suml[i-]+l[i];
sumr[m+]=;
for(int i=m;i>=;i--)
sumr[i]=sumr[i+]+r[i];
sumu[]=;
for(int i=;i<=n;i++)
sumu[i]=sumu[i-]+u[i];
sumdd[n+]=;
for(int i=n;i>=;i--)
sumdd[i]=sumdd[i+]+dd[i];
int num[];
int jishu=;
for(int i=;i<=d;i++){
if(x1[i]==x2[i]){
num[]=sumu[x1[i]-];
num[]=sumdd[x2[i]+];
if(y1[i]<y2[i]){
num[]=suml[y1[i]]-;
num[]=sumr[y2[i]]-;
}
else{
num[]=suml[y2[i]]-;
num[]=sumr[y1[i]]-;
}
//cout<<num[1]<<" ^^^^"<<num[2]<<" "<<num[3]<<" "<<num[4]<<endl;
}
if(y1[i]==y2[i]){
num[]=suml[y1[i]-];
num[]=sumr[y2[i]+];
if(x1[i]<x2[i]){
num[]=sumu[x1[i]]-;
num[]=sumdd[x2[i]]-;
}
else{
num[]=sumu[x2[i]]-;
num[]=sumdd[x1[i]]-;
}
}
int flag=;
for(int j=;j<=;j++)
{
if(num[j]==b[j])
flag++;
}
if(flag==)
{
printf("%d\n",i);
return ;
}
}
printf("-1\n");
return ;
}
2 seconds
256 megabytes
standard input
standard output
Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another.
The game rules are like this. Firstly Alice chooses some color A, then Bob chooses some color B (A ≠ B). After each car they update the number of cars of their chosen color that have run past them. Let's define this numbers after i-th car cntA(i) and cntB(i).
- If cntA(i) > cntB(i) for every i then the winner is Alice.
- If cntB(i) ≥ cntA(i) for every i then the winner is Bob.
- Otherwise it's a draw.
Bob knows all the colors of cars that they will encounter and order of their appearance. Alice have already chosen her color A and Bob now wants to choose such color B that he will win the game (draw is not a win). Help him find this color.
If there are multiple solutions, print any of them. If there is no such color then print -1.
The first line contains two integer numbers n and A (1 ≤ n ≤ 105, 1 ≤ A ≤ 106) – number of cars and the color chosen by Alice.
The second line contains n integer numbers c1, c2, ..., cn (1 ≤ ci ≤ 106) — colors of the cars that Alice and Bob will encounter in the order of their appearance.
Output such color B (1 ≤ B ≤ 106) that if Bob chooses it then he will win the game. If there are multiple solutions, print any of them. If there is no such color then print -1.
It is guaranteed that if there exists any solution then there exists solution with (1 ≤ B ≤ 106).
4 1
2 1 4 2
2
5 2
2 2 4 5 3
-1
3 10
1 2 3
4
Let's consider availability of colors in the first example:
- cnt2(i) ≥ cnt1(i) for every i, and color 2 can be the answer.
- cnt4(2) < cnt1(2), so color 4 isn't the winning one for Bob.
- All the other colors also have cntj(2) < cnt1(2), thus they are not available.
In the third example every color is acceptable except for 10.
题意：给你一个长度为n的序列 要求选取一个不为A的数B 使得所有的cntB(i) ≥ cntA(i) 前i个数中B出现的次数大于A出现的次数
题解： mp[i].set()出现i次数有哪些；
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
int n,A;
int a[];
map<int,int>mp;
map<int,set< int > > se;
set<int>::iterator it,itt;
set<int > re;
int main()
{
scanf("%d %d",&n,&A);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int now=;
int flag=;
for(int i=;i<=n;i++)
{
if(a[i]!=A){
it=se[mp[a[i]]].find(a[i]);
if(it!=se[mp[a[i]]].end())
se[mp[a[i]]].erase(it);
mp[a[i]]++;
se[mp[a[i]]].insert(a[i]);
if(flag==)
re.insert(a[i]);
}
else{
now++;
if(now==)
flag=;
for(it=re.begin();it!=re.end();)
{
if(mp[*it]<now)
{
re.erase(it++);
}
else
it++;
}
if(re.size()==){
printf("-1\n");
return ;
}
}
}
printf("%d\n",*re.begin());
return ;
}
/*
10 6
8 5 1 6 6 5 10 6 9 8
*/
2 seconds
256 megabytes
standard input
standard output
Vova again tries to play some computer card game.
The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number ai is written on the i-th card in the deck.
After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck.
Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?
The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the cards.
Print the number of ways to choose x and y so the resulting deck is valid.
3 4
6 2 8
4
3 6
9 1 14
1
In the first example the possible values of x and y are:
- x = 0, y = 0;
- x = 1, y = 0;
- x = 2, y = 0;
- x = 0, y = 1.
题意：给你一个序列 现在让你前面去掉x个后面去掉y个 问有多少中选择的方式使得剩下的数的连乘的结果能够除尽k
题解：将k分解质因子 并记录各个数以及个数 现 在遍历序列 记录 各个因子的前缀个数 固定左界二分右界 check各个因子的个数是否符合
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#define ll __int64
#define mod 100000000
using namespace std;
ll n,k;
ll p;
ll num[];
ll numci[];
ll sum[][];
int jishu=;
bool check(int x,int y)
{
for(int i=;i<jishu;i++){
ll zha=sum[y][i]-sum[x-][i];
if(zha<numci[i])
return false;
}
return true;
}
int main()
{
scanf("%I64d %I64d",&n,&k);
ll exm=k; for(ll i=; i*i<=exm; i++)
{
if(exm%i==)
{
int now=;
num[jishu++]=i;
while(exm%i==){
exm/=i;
now++;
}
numci[jishu-]=now;
}
}
if(exm>){
num[jishu++]=exm;
numci[jishu-]=;
}
for(int i=;i<jishu;i++)
sum[][i]=;
for(int j=; j<=n; j++)
{
scanf("%I64d",&p);
for(int k=;k<jishu;k++){
sum[j][k]=sum[j-][k];
while(p%num[k]==){
sum[j][k]++;
p/=num[k];
}
}
}
ll ans=;
for(int i=;i<=n;i++)
{
int l=i,r=n,mid;
while(l<r)
{
mid=(l+r)/;
if(check(i,mid))
r=mid;
else
l=mid+;
}
if(check(i,r))
ans=ans+n-r+;
}
printf("%I64d\n",ans);
return ;
}