### qzqzgfy's blog

By qzqzgfy, history, 6 years ago,

A. Joysticks

================== Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

Examples input 3 5 output 6 input 4 4 output 5 It doesn't stop me too much,and the solution is to charge the one with less electricity and discharge the one with more electricity.But the first three times I got f**k in the test No.7 and finally there is a trick(maybe not) that you should break at once the two joysticks are both in 1%.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
long long n,m,cnt;
int main(){
scanf("%I64d%I64d",&n,&m);
cnt=0;
while (1){
if (n<=0||m<=0) break;
if (n==1&&m==1) break;
if (n>m) std::swap(n,m);
n+=1;
m-=2;
cnt++;
}
printf("%I64d\n",cnt);
}

B. Beautiful Paintings

================== There are n pictures delivered for the new exhibition. The i-th painting has beauty ai. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that ai + 1 > ai.

Input The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai means the beauty of the i-th painting.

Output Print one integer — the maximum possible number of neighbouring pairs, such that ai + 1 > ai, after the optimal rearrangement.

Examples input 5 20 30 10 50 40 output 4 input 4 200 100 100 200 output 2

Another water problem..,use the counting sort and every time you got a longest monotonic rise sequence a1..ai..an,and the ans+=(n-1),and delete the sequence from the array sorted. when the num of the array is 0,then the ans is the ans.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
int n,x,a[1005],cnt,ans;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&x);
a[x]++;
}
while (1){
if (n==0) break;
int cnt=0;
for (int i=1;i<=1000;i++) if (a[i]) cnt++,a[i]--,n--;
ans+=cnt-1;
}
printf("%d\n",ans);
}

C. Watchmen

================== Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (xi, yi).

They need to arrange a plan, but there are some difficulties on their way. As you know, Doctor Manhattan considers the distance between watchmen i and j to be |xi - xj| + |yi - yj|. Daniel, as an ordinary person, calculates the distance using the formula .

The success of the operation relies on the number of pairs (i, j) (1 ≤ i < j ≤ n), such that the distance between watchman i and watchmen j calculated by Doctor Manhattan is equal to the distance between them calculated by Daniel. You were asked to compute the number of such pairs.

Input The first line of the input contains the single integer n (1 ≤ n ≤ 200 000) — the number of watchmen.

Each of the following n lines contains two integers xi and yi (|xi|, |yi| ≤ 109).

Some positions may coincide.

Output Print the number of pairs of watchmen such that the distance between them calculated by Doctor Manhattan is equal to the distance calculated by Daniel.

Examples input 3 1 1 7 5 1 5 output 2 input 6 0 0 0 1 0 2 -1 1 0 1 1 1 output 11

Solution: First,we should know about that : the pair of two points whose Manhattan distance equals to Euclidean distance must be in the same row or the same line.But if two points are in the same coordinate,the we must delete the number that repeated. so the final ans is: ∑the num of the points in same line+∑the num of points in the row- ∑the num of points in the same coordinate.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
struct op{
long long x,y;
}p[200005];
long long y[200005],x[200005],xx,yy,n,ans,nx[200005],ny[200005];
bool cmp(op q,op w){
if (q.x==w.x) return q.y<w.y;
return q.x<w.x;
}
int main(){
scanf("%I64d",&n);
for (int i=1;i<=n;i++){
scanf("%I64d%I64d",&xx,&yy);
x[++x[0]]=xx;
y[++y[0]]=yy;
p[i].x=xx;
p[i].y=yy;
}
std::sort(p+1,p+1+n,cmp);
std::sort(x+1,x+1+x[0]);
std::sort(y+1,y+1+y[0]);
long long tx=1;
nx[1]=1;
for (long long i=2;i<=x[0];i++)
if (x[i]!=x[i-1]) x[++tx]=x[i],nx[tx]=1;
else nx[tx]++;
x[0]=tx;
long long ty=1;
ny[1]=1;
for (long long i=2;i<=y[0];i++)
if (y[i]!=y[i-1]) y[++ty]=y[i],ny[ty]=1;
else ny[ty]++;
y[0]=ty;
for (long long i=1;i<=x[0];i++)
if (nx[i]>1) ans+=(nx[i]*(nx[i]-1))/2;
for (long long i=1;i<=y[0];i++)
if (ny[i]>1) ans+=(ny[i]*(ny[i]-1))/2;
long long cnt=1;
for (long long i=2;i<=n;i++)
if (p[i].x==p[i-1].x&&p[i].y==p[i-1].y){
cnt++;
}
else{
if (cnt>1) ans-=(cnt-1)*cnt/2;
cnt=1;
}
if (cnt>1) ans-=(cnt-1)*cnt/2;
printf("%I64d\n",ans);
}

D. Image Preview

==================

Vasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.

For each photo it is known which orientation is intended for it — horizontal or vertical. Phone is in the vertical orientation and can't be rotated. It takes b second to change orientation of the photo.

Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn't spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.

Help Vasya find the maximum number of photos he is able to watch during T seconds.

Input The first line of the input contains 4 integers n, a, b, T (1 ≤ n ≤ 5·105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — the number of photos, time to move from a photo to adjacent, time to change orientation of a photo and time Vasya can spend for watching photo.

Second line of the input contains a string of length n containing symbols 'w' and 'h'.

If the i-th position of a string contains 'w', then the photo i should be seen in the horizontal orientation.

If the i-th position of a string contains 'h', then the photo i should be seen in vertical orientation.

Output Output the only integer, the maximum number of photos Vasya is able to watch during those T seconds.

Examples input 4 2 3 10 wwhw output 2 input 5 2 4 13 hhwhh output 4 input 5 2 4 1000 hhwhh output 5 input 3 1 100 10 whw output 0

Solution: First we must got to know: it's only once we can swipe from the one side back to the other side,because if we had read the photo,then if we back to the other side then the cost is depend on the length of the path.if we "across over" the photo we had read,then it's only once and if more,it's waste. So we can just pretreat the cost we swipe left and swipe right.And enums to swipe left,and use two pointers to find the how far can I get to the opside with the rest time. If I go right first,then is the same. (I forgot to consider the two situations but the only one yesterday,f**k)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define ll long long
ll l[500005],r[500005],n,a,b,T,cost[500005],ans;
ll find(ll x){
ll L=2,R=n,res=n;
if (x<l[n]) return n+1;
if (x>=l[2]) return 2;
while (L<=R){
ll mid=(L+R)/2;
if (l[mid]<=x) res=mid,R=mid-1;
else L=mid+1;
}
while (x<=l[res]&&res<n+1) res++;
while (res>2&&x>=l[res-1]) res--;
return res;
}
ll find1(ll x){
ll L=2,R=n,res=n;
if (x<r[2]) return 1;
if (x>=r[n]) return n;
while (L<=R){
ll mid=(L+R)/2;
if (r[mid]<=x) res=mid,L=mid+1;
else R=mid-1;
}
while (x<r[res]&&res>1) res--;
while (x>=r[res+1]&&res<n) res++;
return res;
}
int main(){
scanf("%I64d%I64d%I64d%I64d",&n,&a,&b,&T);
char s[500005];
scanf("%s",s+1);
for (ll i=1;i<=n;i++)
if (s[i]=='w')
cost[i]=b+1;
else
cost[i]=1;
for (ll i=2;i<=n;i++)
r[i]=r[i-1]+a+cost[i];
for (ll i=n;i>=2;i--)
l[i]=l[i+1]+a+cost[i];
for (ll i=n+1;i>=2;i--){
ll t;
if (i==n+1)
t=T-cost[1];
else
t=T-l[i]-cost[1]-(n-i+1)*a;
if (t<0) continue;
ll x=find1(t);
ans=std::max(ans,x+(n-i+1));
if (ans>n) ans=n;
}
for (ll i=1;i<=n;i++){
ll t;
if (i==1)
t=T-cost[1];
else
t=T-r[i]-cost[1]-(i-1)*a;
if (t<0) continue;
ll x=find(t);
ans=std::max(ans,i+n-x+1);
if (ans>n) ans=n;
}

printf("%I64d\n",ans);
}

E. Table Compression

==================
Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a' consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table a'i, j < a'i, k, and if ai, j = ai, k then a'i, j = a'i, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table a'i, j < a'p, j and if ai, j = ap, j then a'i, j = a'p, j.

Because large values require more space to store them, the maximum value in a' should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.

Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 109) that are the values in the table.

Output Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

Examples input 2 2 1 2 3 4 output 1 2 2 3 input 4 3 20 10 30 50 40 30 50 60 70 90 80 70 output 2 1 3 5 4 3 5 6 7 9 8 7

Solution: The last problem.I don't know how to deal with it in exam :| Next day,after consulting others'code,it passed finally. First we sort the n*m numbers in their value. Every time extract the same numbers,union the numbers in same rows or in same lines by using union-find,and find the max number which is in the same row or line to the number of the set.and the ans of the number now I'm solving is the maxinum+1.(My express maybe some kind of ambiguous:)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define N 1000005
struct op{
int x,y,num;
}f[N];
int tot,go[N],first[N],next[N],n,m,fa[N],a[N],b[N];
bool cmp1(op q,op w){
return q.x<w.x;
}
bool cmp2(op q,op w){
return q.num<w.num;
}
bool cmp3(op q,op w){
return (q.num-1)/m<(w.num-1)/m;
}
bool cmp4(op q,op w){
return (q.num-1)%m<(w.num-1)%m;
}
int find(int x){
if (x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n*m;i++){
scanf("%d",&f[i].x);
f[i].num=i;
fa[i]=i;
}
std::sort(f+1,f+1+n*m,cmp1);
int la=0;
for (int i=1;i<=n*m;i=la+1){
la=i;
while (f[la+1].x==f[la].x&&la<n*m) la++;
std::sort(f+i,f+la+1,cmp3);
for (int j=i+1;j<=la;j++)
if ((f[j].num-1)/m==(f[j-1].num-1)/m)
fa[find(f[j].num)]=find(f[j-1].num);
std::sort(f+i,f+la+1,cmp4);
for (int j=i+1;j<=la;j++)
if ((f[j].num-1)%m==(f[j-1].num-1)%m&&find(f[j-1].num)!=find(f[j].num))
fa[find(f[j].num)]=find(f[j-1].num);
for (int j=i;j<=la;j++)
insert(find(f[j].num),j);
for (int j=i;j<=la;j++){
int o=f[j].num,now=0;
for (int k=first[o];k;k=next[k]){
now=std::max(now,std::max(a[(f[k].num-1)/m+1],b[(f[k].num-1)%m+1]));
}
for (int k=first[o];k;k=next[k]){
f[k].y=now+1;
a[(f[k].num-1)/m+1]=b[(f[k].num-1)%m+1]=now+1;
}
}
}
std::sort(f+1,f+1+n*m,cmp2);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++)
printf("%d ",f[(i-1)*m+j].y);
printf("\n");
}
}


• -7

 » 6 years ago, # |   0 Auto comment: topic has been updated by qzqzgfy (previous revision, new revision, compare).