VPARTSUM - Tổng bộ phận
Tác giả: hieult
Ngôn ngữ: C++
#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();
}