Editorial for Tổng bộ phận


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
const fi='';
      maxn=100100;
var n,z,k,re,num:longint;
    a:array[0..maxn*2] of longint;
    b,c,d:array[0..maxn] of longint;

procedure rf;
var x,i:longint;
begin
     read(n,k,z);
     re:=z-1;
     for i:=1 to n do
     begin
          read(x);
          x:=x mod z;
          if x>=k then re:=min(re,x);
          a[i]:=(a[i-1]+x) mod z;
          d[i]:=i;
     end;
end;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; y:=d[(j+i) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (d[i]<y)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (d[j]>y)) do j:=j-1;
           if i<=j then
           begin
               t:=a[i]; a[i]:=a[j]; a[j]:=t;
               t:=d[i]; d[i]:=d[j]; d[j]:=t;
               i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function bs(val,l:longint):longint;
var r,m,i:longint;
begin
     r:=l+num;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if a[m]<val then l:=m+1
          else r:=m-1;
     end;
     for i:=m-1 to m+1 do
         if (i>=0) and (i<=num*2+1) and (a[i]>=val) then exit(i mod (num+1));
end;

procedure pr;
var i,x:longint;
begin
     sort(0,n);
     num:=0;
     for i:=1 to n do
         if a[i]>a[num] then
         begin
              num:=num+1;
              a[num]:=a[i];
              b[num]:=d[i];
              c[num-1]:=d[i-1];
         end;
     c[num]:=d[n];
     for i:=0 to num do a[num+1+i]:=a[i]+z;
     for i:=0 to num do
     begin
          x:=bs(a[i]+k,i);
          while ((a[x]-a[i]+z) mod z<re) do
          begin
               if b[i]<c[x] then
               begin
                    re:=(a[x]-a[i]+z) mod z;
                    break;
               end;
               x:=(x+1) mod (num+1);
          end;
          if re=k then break;
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;

void print(set<int> s) {
    for(set<int>::iterator it = s.begin(); it != s.end(); ++it)
        printf("%d ", *it);
    printf("\n");
}

int main() {
    set<int> s;
    int n, p, k, sum = 0;
    scanf("%d%d%d", &n, &k, &p);
    int res = p;
    for(int i = 0; i < n; ++i) {
        int x; scanf("%d", &x);
        sum = (sum + x) % p;
        set<int>::iterator it = s.upper_bound(((sum - k) % p + p) % p);
        if(it != s.begin())
            res = min(res, ((sum - *(--it)) % p + p) % p);
        s.insert(sum);
    }
    printf("%d\n", res);
    return 0;
}

Code mẫu của RR

uses math;
const
  FINP='';
  FOUT='';
  MAXN=1000111;
var
  c,ln,a,sum:array[0..MAXN] of int64;
  best,sl,n,p,k:int64;
  test:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n,k,p);
  fillchar(a,sizeof(a),0);
  fillchar(sum,sizeof(sum),0);
  fillchar(ln,sizeof(ln),0);
  fillchar(c,sizeof(c),0);
  for i:=1 to n do read(f1,a[i]);
  for i:=1 to n do sum[i]:=(sum[i-1]+a[i]) mod p;
  sum[n+1]:=0;
end;
procedure swap(var a,b:int64); inline;
var
  temp:int64;
begin
  temp:=a; a:=b; b:=temp;
end;
var
  mid:int64;
procedure sort(l,r:int64); inline;
var
  i,j:int64;
begin
  mid:=c[l+random(r-l+1)]; i:=l; j:=r;
  repeat
    while c[i]<mid do inc(i);
    while c[j]>mid do dec(j);
    if i<=j then
      begin
        swap(c[i],c[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure init;
var
  i:longint;
begin
  for i:=1 to n+1 do c[i]:=sum[i];
  sort(1,n+1);
  sl:=1;
  for i:=2 to n+1 do
    if c[i]>c[sl] then
      begin
        inc(sl);
        c[sl]:=c[i];
      end;
end;
function get(u:int64):int64; inline;
var
  kq,v:int64;
begin
  if u<=0 then exit(0);
  kq:=ln[u];
  v:=u-u and (-u);
  if v>0 then kq:=max(kq,get(v));
  exit(kq);
end;
procedure update(u,k:int64); inline;
var
  v:int64;
begin
  ln[u]:=max(ln[u],k);
  v:=u+u and (-u);
  if v<=sl then update(v,k);
end;
function find(x:int64):int64; inline;
var
  l,r,kq:int64;
begin
  l:=1; r:=sl; kq:=0;
  repeat
    mid:=(l+r)>>1;
    if c[mid]<=x then
      begin kq:=mid; l:=mid+1; end
    else r:=mid-1;
  until l>r;
  exit(kq);
end;
procedure solve;
var
  u,temp:int64;
  i:longint;
begin
  best:=maxlongint;
  for i:=1 to n do
    begin
      if sum[i]>=k then
        begin
          u:=find(sum[i]-k);
          best:=min(best,sum[i]-get(u));
        end;
      u:=find(sum[i]+p-k);
      temp:=get(u);
      if temp>sum[i] then best:=min(best,sum[i]-temp+p);
      u:=find(sum[i]);
      update(u,sum[i]);
    end;
end;
procedure ans;
begin
  writeln(f2,best);
end;
begin
  openF;
//  readln(f1,test);
  test:=1;
  for test:=1 to test do
    begin
      inp;
      init;
      solve;
      ans;
    end;
  closeF;
end.

Code mẫu của hieult

#include <iostream>
#include <cstdio>
//#include <conio.h>
//#include <algorithm>
//#include <alloc.h>

using namespace std;


class Node
{
    public:
    int info;
    Node* left;
    Node* right;
    Node (int x)
    {
        info = x; left = right = NULL;
    }
};

class BSTree
{

    public:
    Node* root;
    BSTree() {root=NULL;}
    bool isEmpty(){return(root==NULL);}
    void clear(){ root = NULL;}
    void visit(Node p)
    {
        //System.out.println(p.info);
    };

    void setRoot(int x)
    {
        root = new Node(x);

    }
    int max(int a,int b)
    {
        if(a>b) return a;
        return b;
    }
    /*
    Node search(Node* p,int x)
    {
        if( p == NULL || p->info ==x ) return p;
        if(x<p->info) return search(p->left,x);
        else return search(p->right,x);
    }
    */
    int Search(int x)
    {
        int k = tim(root,x);
        return k;
    }

    int tim(Node* p,int x)
    {
        if(p==NULL)
            return 0;
        if(p->info==x)
            return x;
        if(x<p->info)
            return tim(p->left,x);
        else return max(p->info,tim(p->right,x));
    }
    /*
    void insert(int x)
    {
        Node q = new Node(x);
        if(isEmpty()){root = q; return;}
        Node f,p; f= null; p=root;
        while(p!=null)
        {
             {if(p.info==x) {System.out.println(" The key already exists"); return;}
              f = p;
              if(x<p.info) p=p.left; else p=p.right;
             }
            if(x<f.info) f.left=q; else f.right=q;
        }
    }

     */
  void insert(int x)
   {Node* q = new Node(x);
    if(isEmpty()) {root=q;return;}
    Node *f,*p;f=NULL;p=root;
    while(p!=NULL)
     {if(p->info==x) {//System.out.println(" The key already exists");
          return;}
      f = p;
      if(x<p->info) p=p->left; else p=p->right;
     }
    if(x<f->info) f->left=q; else f->right=q;
   }
  /*
    void preOrder(Node p)
    {
        if(p==null) return;
        visit(p);
        preOrder(p.left);
        preOrder(p.right);
    }
    void inOrder(Node p)
   {
    if(p==null) return;
    inOrder(p.left);
    visit(p);
    inOrder(p.right);
   }
    void postOrder(Node p)
   {if(p==null) return;
    postOrder(p.left);
    postOrder(p.right);
    visit(p);
   }
    void breadthTraverse()
    {
        MyQueue q = new MyQueue();
        q.enqueue(root);
        Node p;
        while(!q.isEmpty())
        {
            p = (Node) q.dequeue();
            visit(p);
            if(p.left!=null) q.enqueue(p.left);
            if(p.right!=null) q.enqueue(p.right);
        }
    }
    void dele(int x)
    {
        Node f,p; f=null; p=root;
        while(p!=null)
        {
            if(p.info == x) break;
            f=p;
            if(x<p.info) p=p.left; else p = p.right;
        }
        if (p==null){ System.out.println("...");}
        if(p.left == null && p.right == null)
        {
            if(f==null ){root=null;return;}
            if(f.left==p)f.left=null; else f.right = null;
        }

        if(p.left !=null &&p.right==null)
        {
            if(f==null ){root=p.left;return;}
            if(f.left==p)f.left=p.left; else f.right = p.left;

        }
        if(p.left ==null &&p.right!=null)
        {
            if(f==null ){root=p.right;return;}
            if(f.left==p)f.left=p.right; else f.right = p.right;

        }
        if(p.left !=null &&p.right!=null)
        {
            Node rp ,frp;
            frp = p;rp =p.left;
            while(rp.right!=null)
            {
                frp = rp;rp=rp.right;
            }
            p.info = rp.info;
            frp.right=rp.left;
        }
    }
    void delebyMerging(int x)
    {
        Node f,p; f=null; p=root;
        while(p!=null)
        {
            if(p.info == x) break;
            f=p;
            if(x<p.info) p=p.left; else p = p.right;
        }
        if (p==null){} //System.out.println("...");}
        if(p.left == null && p.right == null)
        {
            if(f==null ){root=null;return;}
            if(f.left==p)f.left=null; else f.right = null;
        }

        if(p.left !=null &&p.right==null)
        {
            if(f==null ){root=p.left;return;}
            if(f.left==p)f.left=p.left; else f.right = p.left;

        }
        if(p.left ==null &&p.right!=null)
        {
            if(f==null ){root=p.right;return;}
            if(f.left==p)f.left=p.right; else f.right = p.right;

        }
        if(p.left !=null &&p.right!=null)
        {
            Node q=p.right;
            p.right=null;
            Node lp = p.left;
            if(f.left==p) f.left = lp; else f.right=lp;
            Node rp ;
            rp = lp;
            rp =p.left;
            while(rp.right!=null)
            {
                rp=rp.right;
            }
            rp.right=q;
        }
    }
    void addMany(int [] a)
    {
        for(int i=0;i<a.length;i++)
            insert(a[i]);
    }
*/ 
};

int main()
{
     //freopen("VPARTSUM.in","r",stdin);
     int n,k,p,a;
     int tong = 0;
     BSTree t;
     scanf("%d %d %d",&n,&k,&p);
     int KQ = p;
     for(int i = 1;i<=n;i++)
        {
            scanf("%d",&a);
            tong = (tong + a)%p;
            int x = tong-k,y;
            if(x<0) x+=p;
            y = t.Search(x);
            //(tong+" "+x+" "+y);
            y = tong - y;
            if(y<0) y+=p;
            if(y<KQ) KQ = y;
            t.insert(tong);
        }
        printf("%d",KQ);
        //getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define INF 2000000001
typedef long long ll;
using namespace std;

set<int> s;
int n,k,p;
int a[100010];

int main()
{
//    freopen("part.in","r",stdin);
//    freopen("part.ou","w",stdout);
    scanf("%d %d %d", &n, &k, &p);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int ret = INF;
    s.insert(-1);  s.insert(INF);  s.insert(0);  int sum = 0;
    for (int i = 0; i < n; i++)
    {
        set<int>::iterator iter;
        sum = (sum + a[i]) % p;
        if (sum >= k)
        {
          iter = s.upper_bound(sum - k);  iter--;
          if (*iter != -1) ret = min(ret,sum - *iter);
        };
        iter = s.upper_bound(sum + p - k);  iter--;
        if (*iter >= sum) ret = min(ret,sum + p - *iter);
        s.insert(sum);
    };
    printf("%d\n", ret);
};

Code mẫu của skyvn97

#include<stdio.h>
#include<set>
#define MAX   100100
using namespace std;
typedef set<int> si;
si st;
int a[MAX];
int s[MAX];
int n,k,p;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    scanf("%d",&p);
    int i;
    s[0]=0;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&a[i]);
        s[i]=(s[i-1]+a[i])%p;
    }
    k=k%p;
}
void process(void) {
    int b=p;
    int i,t;
    si::iterator it;
    for (i=n-1;i>=1;i=i-1) {
        if (st.find(s[i+1])==st.end()) st.insert(s[i+1]);
        it=st.end();
        it--;
        if (*it>=s[i]+k) {
            t=*(st.lower_bound(s[i]+k));
            if (t-s[i]<b) b=t-s[i];
        }
        if (*it>=s[i]+k-p) {
            t=*(st.lower_bound(s[i]+k-p));
            if (t-s[i]+p<b) b=t-s[i]+p;
        }
    }
    printf("%d",b);
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <cstdio>
#include <set> 
using namespace std; 
int n, k, p, x;
int sum[100010]; 
int main() {
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;++i) { 
        scanf("%d",&x);
        sum[i] = (sum[i-1] + x) % p;
    }
    set<int> se;
    se.insert(0);       
    int res = p+1;      
    for(int i=1;i<=n;++i) {         
        set<int>::iterator si = se.lower_bound((sum[i]-k+1+p) % p);         
        if(si!=se.begin()) --si;            
        else {              
            si = se.end();              
            --si;           
        }
        if((sum[i]-*si+p)%p>=k) 
            res <?= (sum[i]-*si+p)%p;           
        se.insert(sum[i]);      
    }       
    printf("%d\n",res); 
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.