Codeforces #402

Codeforces 779A Pupils Redistribution

The question ： Yes A Group and B Group , Each group has n personal ,A The score of each person in the group is $$a_i$$,B The score of each person in the group is $$b_i$$,$$1\le a_i ,b_i\le5$$, At least how many people should be exchanged between the two sides to make A Each score in the group should be compared with B There are as many in the group .

Ideas ： If two are in $$i$$ The difference in the number of people on this score is odd , No way. , If it's an even number , If A Than B many , So A Follow B Half the difference in exchange , If B The in $$j$$ This score is higher than A many , Then you can just talk to $$i$$ This score exchange , So the answer is half the difference between them .

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
using namespace std;
int cnta[10],cntb[10];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(cnta,0,sizeof(cnta));
memset(cntb,0,sizeof(cntb));
int x;
for(int i=1;i<=n;i++){
scanf("%d",&x);
cnta[x]++;
}
for(int i=1;i<=n;i++){
scanf("%d",&x);
cntb[x]++;
}
bool flag=true;
int cnt=0;
for(int i=1;i<=5;i++){
int num=abs(cnta[i]-cntb[i]);
if(num>0){
if(num%2==1) {
flag=false;
break;
}
else cnt+=num/2;
}
}
if(flag){
printf("%d\n",cnt/2);
}
else {
printf("-1\n");
}
}
}


Codeforces 779B Weird Rounding

The question ： There are two numbers $$n,k$$, At least delete $$n$$ How many numbers are there , Can make $$n$$ to be divisible by $$10^k$$.30020 If you delete 2 for 3000, If 1000, Delete 1, by 000, Delete all as 0, There are many. 0 To delete it, it's just 1 individual 0 In order to be 0.

Ideas ： greedy , It must be deleted from the back , Every time you delete it, judge once , No, go on , If it's deleted, it's just 0 But more than one 0, At this time, you can directly delete the current number of digits -1 There is only one left 0 了 .

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
using namespace std;
int a[20];
int cnt;
long long mod;
void change(long long tmp){
cnt=0;
while(tmp){
a[cnt++]=tmp%10;
tmp/=10;
}
}
long long changenum(int num[],int len){
long long tmp=0;
long long dig=1;
for(int i=0;i<len;i++){
tmp+=num[i]*dig;
dig*=10;
}
return tmp;
}
int ans;
int main(){
long long num;
int k;
while(scanf("%I64d",&num)!=EOF){
scanf("%d",&k);
mod=1;
for(int i=1;i<=k;i++){
mod*=10;
}
ans=0;
if(num%mod==0) {
printf("0\n");
continue;
}
else {
bool flag=false;
while(!flag){
if(num==0&&cnt!=1){
ans+=(cnt-2);
}
if(num%mod==0){
flag=true;
break;
}
change(num);
for(int i=0;i<cnt;i++){
if(a[i]!=0){
for(int j=i+1;j<cnt;j++){
a[j-1]=a[j];
}
ans++;
break;
}
}
num=changenum(a,cnt-1);
}
printf("%d\n",ans);
}
}
return 0;
}


Codeforces 779C Dishonest Sellers

The question ： Yes $$n$$ A commodity , Each item has a current price $$a_i$$, And the discount price after a week $$b_i$$, Now be sure to buy at least $$k$$ Items , Ask how to buy in order to make it finished $$n$$ Each item costs the least

Ideas ： The original price =$$a1+...+a_n$$, Discount price =$$b_1+...+b_k+...+a_n$$, The original price - Discount price =$$\sum_{i=1}^{k}(a_i-b_i)$$, So if you want to get a lower price after discount , We should choose the one with the largest price difference between the two , That is to say, if the price difference is small, buy the original price . Note that if the discount price is higher than the original price , Then you can choose the original price directly .

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN=2e5+10;
int n,k;
int a[MAXN],b[MAXN];
bool flag[MAXN];
struct node{
int id;
int num;
};
node c[MAXN];
bool cmp(node a,node b){
return a.num<b.num;
}
int main(){
while(scanf("%d %d",&n,&k)!=EOF){
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
for(int i=1;i<=n;i++){
c[i].num=a[i]-b[i];
c[i].id=i;
if(c[i].num<=0) flag[c[i].id]=true;
}
sort(c+1,c+1+n,cmp);
long long ans=0;
for(int i=1;i<=k;i++) flag[c[i].id]=true;
for(int i=1;i<=n;i++){
if(!flag[i]) ans+=b[i];
else ans+=a[i];
}
printf("%lld\n",ans);
}
return 0;
}


Codeforces 779D String Game

The question ： Now there's a string, the original string $$t$$, There is a pattern string $$p$$, Now make sure to delete some letters from the original string ,$$p$$ Still exist in $$t$$ Inside （ Subsequence ）, Give the order of deletion $$a_i$$, Ask which step can be deleted at most $$p$$ It also contains $$t$$.

Ideas ： Two points answer ,O(n) Judge the subsequence

Codeforces #402 More articles about

1. codeforces 402 D. Upgrading Array（ number theory + greedy ）

Topic link :http://codeforces.com/contest/402/problem/D The question : Give a a String and prime string b .f(1) = 0; p by s The smallest prime factor of if p Do not belong to b , otherwise  . a ...

2. CodeForces 402 E Strictly Positive Matrix

Strictly Positive Matrix Answer key : If the original a[i][j] = 0, Now a[i][j] = 1, So is equal to the sum{a[i][k] + a[k][j]} > 1. ...

3. Codeforces Round #402 (Div. 2)

Codeforces Round #402 (Div. 2) A. Daily sabiti #include<iostream> #include<cstdio> #include< ...

4. Codeforces Round #402 (Div. 2) A+B+C+D

Codeforces Round #402 (Div. 2) A. Pupils Redistribution Simulation Dafa is good . The two sequences contain respectively n Number x(1<=x<=5) . Now we need to exchange some numbers ...

5. Codeforces Round #402 (Div. 2) D. String Game

D. String Game time limit per test 2 seconds memory limit per test 512 megabytes input standard inpu ...

6. Codeforces Round #402 (Div. 2) Death in battle

I haven't played for a long time Codeforces 了 , Today is ysf I had a fight . lrd Come and join us (nian) Add (ya) Than (zhong) " (sheng) Problem A: I went to , see SB Do you have any questions .. Count each number in a bucket ...

7. CodeForces Round #402 (Div.2) A-E

2017.2.26 CF D2 402 It's tolerable this time …… All the way to the front ABC( No hurry, no delay, no delay ), Stuck in D, And then run to see E and F—— How come there are still F, I knew it would be faster …… F Have a look , Can't , Discard ...

8. Diary of Codeforces Round #402 (Div. 2)

This performance can be used " Mentally retarded all the way "4 A word , Vividly and vividly describe . About Writing questions : A. Wrote a bunch of if Compare the size , It's very industrious .( Absolute value to yourself の The sense of being is 0 I'm sorry .) B. topic , Direct reading ...

9. http://codeforces.com/contest/402/problem/E

E. Strictly Positive Matrix time limit per test 1 second memory limit per test 256 megabytes input s ...

Random recommendation

1. Common Bugs in C Programming

There are some Common Bugs in C Programming. Most of the contents are directly from or modified from ...

2. Linux Shell 2&gt;&amp;1 &amp;

turn   Scripts like : nohup /mnt/Nand3/H2000G >/dev/null 2>&1 & Yes On & 1 To be more precise, it should be a file descriptor 1, and 1 The general representative is ...

3. To configure Kotlin Environmental Science (DataBinding)

1. install Kotlin plug-in unit stay plugin Mid search kotlin, Install two kotlin plug-in unit , Restart Android Studio.2.build.gradle(project level) buildscr ...

4. FTL label

<#if blockObject ??> <#else> </if> Determines whether an object exists <#if componentid ?? &&compon ...

5. ubuntu Automatically turn off the screen display

In the program, the system calls the following two commands , You can turn off the monitor . 1,xset dpms force off 2,system("vbetool dpms off"); Because the application should be in ubuntu Turn it on ...

6. PHPSTORM/IntelliJ IDEA Commonly used Set up configuration optimization

PHPSTORM/IntelliJ IDEA Commonly used Set up configuration optimization - meetrice Time  2014-09-06 10:17:00   Blog Garden - All the essay areas original text   http://www.cnblogs ...

7. java Language inserts a number in an array , Still able to sort

package com.llh.demo; import java.util.Scanner; /** * * @author llh * */ public class Demo16 { /* * ...

8. Apple's new programming language Swift Advanced language （ 15、 ... and ）－－ agreement

Protocols define methods that are appropriate for a particular task or function . A blueprint for attributes and other requirements . The protocol itself does not provide the implementation of these requirements , It just describes a blueprint for the implementation of a task or function . Deal with the java The interface definition in the language is similar to , They all describe an implementation that can ...

9. linux environment variable turn

https://www.cnblogs.com/aaronLinux/p/5837702.html export PATH=/home/one/:$PATH export PATH=$PATH:/ho ...

10. luogu P3234 [HNOI2014] Card copying group

Portal nmdwsm See for yourself , I don't want to write. qwq The garbage code is as follows It's totally different from the solution #define LL long long #define uLL unsigned long long #define ...