Codeforces #402

Codeforces 779A Pupils Redistribution

link :http://codeforces.com/contest/779/problem/A

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

link :http://codeforces.com/contest/779/problem/B

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

link :http://codeforces.com/contest/779/problem/C

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

link :http://codeforces.com/contest/779/problem/D

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 ...