VMSORT (VOJ)

11780. Sắp xếp

Mã bài: VMSORT

Kì thi VM đang dần đi đến những vòng thi cuối cùng. Trong khi các thí sinh hăng say với những bài tập hóc búa, mang đậm tính chất Marathon thì các admin VNOI cũng phải đối mặt với những vấn đề rất nan giải, chẳng hạn như thống kê số lượng thí sinh, số lượng thí sinh giải được từng bài tập...

Trong không khí căng thẳng của cuộc đua, ban tổ chức đã quyết định tặng một món quà đặc biệt cho các bạn. Và món quà đó chính là bài tập này!

Bạn sẽ phải giúp các admin làm một nhiệm vụ sau: Cho dữ liệu mô tả các thí sinh tham gia mỗi một trong K vòng của cuộc thi VNOI Marathone 20xx, hãy tính xem có bao nhiêu thí sinh tham gia ít nhất một vòng thi.

Input

• Dòng 1: Ghi số nguyên dương K (1 ≤ K ≤ 5).
• K nhóm dòng sau: Mỗi nhóm thể hiện dữ liệu của một vòng thi: Dòng đầu ghi số nguyên N (1 ≤ N ≤ 200) là số lượng thí sinh tham gia vòng thi đó. N dòng sau, mỗi dòng ghi một nick của thí sinh, dưới dạng một xâu khác rỗng, độ dài không quá 20 kí tự (đảm bảo xâu không chứa khoảng trống). Trong mỗi nhóm dòng mô tả một vòng thi, không có tên thí sinh nào được lặp lại hai lần.

Output

• Ghi ra một số nguyên duy nhất là số thí sinh tham gia ít nhất một vòng thi.

Example

Input:
3

4

flashmt

ll931110

technolt

tuananhnb93

3

mr_invincible

conankudo

ll931110

3

khanhptnk

hphong

technolt

Output:
8

Solution:

#include<map>
#include<vector>
#include<iostream>
#include<string>
#include<set>
#include<cstdio>
using namespace std;
set<string> S;
int main()
{
/* freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);
*/
int K,N;
char t[21];
cin >> K;
for(int i=0;i<K;i++){
scanf("%d",&N);
for(int j=0;j<N;j++){
scanf("%s",t);
string tt(t);
if(S.find(tt)==S.end())
S.insert(t);
}
}
cout << (int)S.size();
return 0;
}

Lâu đài cát (VOJ)

Link:http://vn.spoj.pl/problems/CTNEWS/

CTN vừa xây xong 1 lâu đài bằng cát !Cũng giống như tất cả các lâu đài khác,

trên đỉnh những bức tường , sẽ có những lỗ trống ( để đặt đại bác cho việc

phòng thù chẳng hạn) , và về hai phía của lỗ trống- tất nhiên sẽ có 2 vùng cao hơn (xem hình vẽ).

Tạm gọi các vùng cao hơn này là Merlons.Lâu đài có N (1<=n<=25000) Merlons,

để thuận tiện ta đánh số chúng từ 1->N;

Merlon thứ I có chiều cao M_i (1<=M_i<=100 000);

Ngài CTN muốn sửa chữa lâu đài thành một mẫu mới , anh ta đã làm một danh sách

N số nguyên B_1…B_N (1<=B_i<=100000) , và anh muốn thay đổi chiều

cao của các Merlon từ (A1…An) thành (B1..Bn) theo một thứ tự nào đó.

Để làm được điều này, anh ta đã thuê một số kỹ sư để thiết kế những

Merlon theo ý muốn của mình.Tất nhiên chi phí cho việc này là rất đắt đỏ.Theo tính toán sơ bộ thì

chi phí để tăng chiều cao của một đơn vị  là X $$

-  Chi phí để giảm chiều cao của một đơn vị là Y $$

Hãy giúp CTN tìm ra phương án để có được bức tường mới mà giá phải

trả là nhỏ nhất !

Input

Dòng đầu :3 số N,X,Y cách nhau ít nhất 1 dấu cách

Dòng 2..N+1 :mỗi dòng là 2 số Ai, Bi cách nhau ít nhất 1 dấu cách

Output

Gồm 1 dòng duy nhất là kết quả.

Example

Input:
3 6 5
3 1
1 2
1 2
Output:
11

Có 40 % số test với n<=9; 60 % số test với n<=18.

Solution:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int N,X,Y;
int a[25001],b[25001];
long long int res=0;

int main()
{
 
 freopen("TEST.INP","r",stdin);
 freopen("TEST.OUT","w",stdout);
 
 cin >> N >> X >> Y; 
 
 for(int i=0;i<N;i++)
  scanf("%d %d",&a[i],&b[i]);
 /*
 for(int i=0;i<N;i++)
  cout << a[i] << ",";
 */ 
 sort(a,a+N);
 sort(b,b+N);
 /*
 for(int i=0;i<N;i++)
  cout << a[i] << ",";
 */
 for(int i=0;i<N;i++)
  if(a[i]<b[i])
   res+=(b[i]-a[i])*X;
  else
   res+=(a[i]-b[i])*Y;
 cout << res;

 return 0; 
}

NKTABLE

11953. NKTable

Mã bài: NKTABLE

Cho bảng m*n ô, mỗi ô có 1 trong 3 số: 0, 1, 2:

0, 1: ô được phép đi vào.

2: ô cấm, không được đi vào.

            Yêu cầu: Xuất phát từ ô (1; 1), chỉ dùng các phép di chuyển sang phải hoặc xuống dưới ô kề cạnh, hãy di chuyển đến ô (m; n) sao cho dãy nhị phân tạo thành từ các ô trên đường đi là số lớn nhất có thể (trong hệ thập phân).

            Dữ liệu đảm bảo luôn tìm được đường đi.

            Giới hạn:       2 <= m, n <= 500

            Input:

-         Dòng đầu tiên gồm 2 số m,  n.

-         m dòng tiếp theo, mỗi dòng gồm n số thuộc tập {0; 1; 2}. Số thứ j ở dòng i biểu diễn ô (i;j) trên bảng.

-         Các số cùng dòng trong input cách nhau một hoặc nhiều dấu cách.

            Output:

-         Một dòng duy nhất là chuỗi nhị phân có giá trị số ở hệ thập phân lớn nhất tìm được (các số in liền).

Ví dụ:

Input:	Output:
3 5                                                                                                                                                                                                                            0 1 2 0 2 0 1 0 0 1 1 2 1 2 1	0110011

Solution:
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;

int M,N;
string s[501][501];
int a[501][501];
string oo;
int main()
{
oo=string("00");
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);
cin >> M >> N;
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
scanf("%d",&a[i][j]);


// cout << s[1][1];
/*
s[1][2]=string("01001");
s[1][3]=string("0010");
cout << "s12=" << s[1][2]<<endl;
cout << "s13=" << s[1][3]<<endl;
if(s[1][2]<s[1][3])
printf("Nho");
else
printf("Khong nho");
*/
string temp;
s[1][1]=a[1][1]+'0';
// cout << s[1][1];
for(int j=2;j<=N;j++)
if(a[1][j-1]!=2&&a[1][j]!=2)
{
temp=(a[1][j]+'0');
s[1][j]=s[1][j-1]+temp;
}
else
s[1][j]=oo;

for(int i=2;i<=M;i++)
if(a[i-1][1]!=2&&a[i][1]!=2)
{
temp =(a[i][1]+'0');
s[i][1]=s[i-1][1]+temp;
}
else
s[i][1]=oo;

for(int i=2;i<=M;i++)
for(int j=2;j<=N;j++)
{
temp=a[i][j]+'0';
if(a[i][j]==2)
s[i][j]=oo;
else
s[i][j]=max(s[i-1][j],s[i][j-1])+temp;
}

/*
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
cout << s[i][j] << ", ";
cout << endl;
}
*/
cout << s[M][N];
return 0;
}

bool operator<(string ss,string tt)
{
return ss<tt;
}

Chia nhóm

2861. Chia nhóm

Mã bài: BCDIV

Một hôm trời nắng nóng bức, Chí Phèo nhà ta lại đến nhà Bá kiến đòi tiền mua rượu. Oái oăm thay, tên Bá Kiến keo kiệt hôm nay lại dở chứng bắt Chí phải thực hiện yêu cầu của mình rồi mới cho tiền. Chí tức tối lắm nhưng vì quá ghiền rượu nên hắn đành phải chấp nhận điều kiện mà cụ thể là giải 1 bài toán.

Bài toán có nội dung như sau :
Cho n phần tử khác nhau, hỏi có bao nhiêu cách chia n phần tử đó thành k nhóm mà mỗi nhóm có ít nhất 1 phần tử (các hoán vị của các nhóm được xem là 1 cách).

Vì thất học nên Chí nghĩ mãi không ra, các bạn giúp Chí 1 tay nhé, không thì hắn ta chết vì thèm rượu mất ^^

Dữ liệu vào :
Dòng đầu tiên chứa số T là số test.
T dòng tiếp theo mỗi dòng chứa 2 số N và K, với 1<=K<=N<=25
Dữ liệu ra :
T dòng, mỗi dòng là số cách với test tương ứng.

Input:
1
4 2

Output:
7

Giải thích : 7 cách chia đó là (ABC)(D) , (ABD)(C) , (ADC)(B) , (DBC)(A) , (AB)(CD) , (AC)(BD) , (BC)(AD)

Link: http://vn.spoj.pl/problems/BCDIV/

Solution:

DevC:

#include<iostream>

using namespace std;

int N,K;

int T;

unsigned long long int qh[26][26];

unsigned long long int kq[1001];

void XuLi();

void Ghi();

int main(){

    scanf("%d",&T);

    int i;

    XuLi();

    for(i=0;i<T;i++){

         scanf("%d%d",&N,&K);

         printf("%llu\n",qh[N][K]);

    }

    return 0;

}

void XuLi(){

     int i,j;

// neu co mot nhom thi luon co mot cach chia

   for(i=1;i<=25;i++) qh[i][1]=1;

// neu co tu 2 nhom tro len

   for(i=2;i<=25;i++)

   for(j=2;j<=i;j++)

                    if(i==j) qh[i][j]=1;

                    else qh[i][j]=j*qh[i-1][j]+qh[i-1][j-1];

}

Cơ số H

2892. Cơ số H

Mã bài: BASEH

Cho một dãy số a[1],a[2],a[3],...,a[n] và hai số K,H được xác định như sau:

• a[1]=1;
• Nếu K chẵn thì a[K]=H*a[K/2].
• Nếu K lẻ thì a[K]=H*a[(K-1)/2]+1.

Các bạn hãy lập trình tính số thứ K của dãy viết trong hệ cơ số H.

Input

• Gồm một dòng duy nhất chứa 2 số K,H.

Output

• In ra số duy nhất là kết quả bài toán.

Giới hạn

• 0< K <=1000000000.
• 0=< H <=2008.

Ví dụ

Input
7 110
Output
111

Link: http://vn.spoj.pl/problems/BASEH/

Solution:
DevC:

#include<stdio.h>
//#include<conio.h>



long int k;
int h;


void Doc();

void DeQuy(long int x);


int main()
{
    Doc();
    DeQuy(k);
 //   getch();
    return 0;  
}
void Doc()
{
 scanf("%d",&k);
 scanf("%d",&h);
}

void DeQuy(long int x)
{
 if(x==1) printf("%d",1);
 else if(x%2==0)   // x la so chan
      {
       DeQuy(x/2);        
       printf("%d",0);
      }
      else    // x la so le
      {
       DeQuy((x-1)/2);        
       printf("%d",1);    
      }
}

Barica

4255. BARICA

Mã bài: BARICAVN

Barica là một con cóc không bình thường. Barica sống trong một cái ao, nơi có N lá sen bềnh bồng trên mặt nước. Những lá sen được đánh số từ 1 đến N. Nhìn từ trên xuống, mỗi lá sen đc xem như một điểm trên hệ trục tọa độ Oxy. Barica có thể nhảy từ lá sen có tọa độ (x1;y1) đến tọa độ (x2,y2) nếu:

_ x2 > x1 và y1 = y2 hoặc
_ y2 > y1 và x1 = x2

Với mỗi lá sen, chúng ta biết được số lượng ruồi gần đó. Barica có thể dùng lưỡi tóm gọn tất cả những con ruồi gần lá sen mà nó đang đứng.

Barica thu được một đơn vị năng lượng với mỗi con ruồi mà nó bắt được và mất K đơn vị năng lượng cho mỗi bước nhảy từ lá sen này sang lá sen khác. Barica không thể thực hiện cú nhảy nếu năng lượng hiện tại của nó nhỏ hơn K.

Barica muốn đi từ lá sen 1 đến lá sen N và tích trữ được nhiều năng lượng nhất có thể khi đang ở lá sen N. Năng lượng của Barica ban đầu bằng 0 và dĩ nhiên nó phải lấy năng lượng từ lá sen 1 để thực hiện cú nhảy.
Hãy tìm năng lượng lớn nhất mà Barica có thể có được tại lá sen N.

Input

_ Dòng đầu là số N và K (N<=300 000; K<=1000) cách nhau bởi khoảng trắng
_ N dòng sau mỗi dòng chứa 3 số x_i, y_i, F_i với x_i và y_i là tọa độ lá sen thứ i và F_i là số ruồi ở lá sen i. (0 <= x_i, y_i <= 100 000; 0 <= F_i <=1000)
Lưu ý: không có hai lá sen nào trùng tọa độ và luôn tồn tại ít nhất một đường đi từ 1 tới N.

Output

_ Một dòng duy nhất là năng lượng cao nhất mà Barica có thể có được khi kết thúc ở lá sen thứ N.

Example

Input:
6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5


Output:
5

Link: http://vn.spoj.pl/problems/BARICAVN/

Solution:

DevC:

#include<iostream>
#include<algorithm>
#include<cstring>
#define maxN 300005
#define maxCost ((1<<31)-1)

using namespace std;

struct Point{
       int x;
       int y;
       int cost;
       Point(){}
       Point(int xx,int yy,int c):x(xx),y(yy),cost(c){}       
};
int N,K;
Point P[maxN];
int order[maxN];
int X[maxN];
int Y[maxN];
int F[maxN];

bool mycmp(int i,int j);
void Test();
void Solve();

int main(){
    scanf("%d%d",&N,&K);
    int i,x,y,c;
    Point p;
    for(i=1;i<=N;i++){
           scanf("%d%d%d",&x,&y,&c); 
           order[i-1]=i;
           P[i]=Point(x,y,c);                            
    }
    
    sort(order,order+N,mycmp);
    memset(X,0,sizeof(X));
    memset(Y,0,sizeof(Y));
    F[0]=-maxCost;
    Solve();
    cout << F[N];
//    Test();
//    system("pause");
    return 0;    
}
bool mycmp(int i,int j){
     if(P[i].x!=P[j].x) return P[i].x<P[j].x;
     return P[i].y<P[j].y;  
}
void Test(){
     int i;
     for(i=1;i<=N;i++) cout << P[i].x << "," << P[i].y << "," << P[i].cost << endl;
     for(i=0;i<N;i++) cout << order[i] << "  ";    
}
void Solve(){
     int i;
     for(i=0;i<N;i++){
           int ord=order[i];
           F[ord]=-maxCost;
           if(ord==1) F[ord]=P[ord].cost;
           int &xx=X[P[ord].x];
           int &yy=Y[P[ord].y];
           if((F[xx]>=K)&&(F[ord]<F[xx]+P[ord].cost-K)) F[ord]=F[xx]+P[ord].cost-K;
           if((F[yy]>=K)&&(F[ord]<F[yy]+P[ord].cost-K)) F[ord]=F[yy]+P[ord].cost-K;
           if(F[ord]>F[xx]) xx=ord;
           if(F[ord]>F[yy]) yy=ord; 
     }     
}

Bò Ba-ri

3720. Bò Ba-ri

Mã bài: BARIC

Học theo những gì đọc được từ một bài báo viết về việc tăng sản lượng sữa, Bessie đã biến mình trở thành một con bò Ba-ri bằng cách tìm hiểu về áp suất không khí để lấy lòng Farmer John.

Cô ta đã làm N phép đo (1 <= N <= 100) trong ngày. Để thuận tiện, chúng lần lượt được gọi là M_1, M_2, ..., M_N (M_i <= 1 000 000). Các phép đo được đánh số theo thứ tự Bessie thực hiện chúng.

Để thể hiện được những phân tích về áp suất khí quyển trong ngày, Bessie đang để tâm đến việc tìm một tập hợp con của các phép đo, biểu thị bởi K (1 <= K <= N) chỉ số s_j (trong đó 1 <= s_1 <= s_2 <= ... <= s_K <= N), thể hiện chính xác được toàn bộ các phép đo, tức là, giới hạn sai số trong khoảng cho phép.

Trong bất kì tập hợp các phép đo nào, một lỗi xuất hiện ở mỗi phép đo có vị trí:

1. trước phép đo đầu tiên trong tập hợp;
2. giữa hai phép đo liên tiếp trong tập hợp;
3. sau phép đo cuối cùng trong tập hợp.

Tổng sai số của tập hợp đó được tính bằng tổng các lỗi trong các phép đo.

Cụ thể, với mỗi phép đó có chỉ số i mà không nằm trong tập hợp các phép đo đang xét:

• Nếu i < s_1 , sai số được tính như sau: 2 * | M_i - M_(s_1) |
• Nếu s_j < i < s_(j+1), sai số được tính như sau: | 2 * M_i - Sum(s_j, s_(j+1)) |
trong đó Sum(x,y) = M_x + M_y
• Nếu s_K > i, sai số được tính như sau: 2 * | M_i - M_(s_K) |

Cho biết sai số tối đa là E (E <= 1 000 000), xác định số phần tử của tập hợp nhỏ nhất tạo ra sai số không vượt quá E.

Dữ liệu

Dòng 1: Chứa hai số nguyên cách nhau bởi khoảng trắng: N và E

Dòng 2..N+1: Dòng i+1 chứa số nguyên M_i

Dữ liệu mẫu
4 20
10
3
20
40

Giải thích

Bessie tiến hành 4 phép đo; sai số tối đa cho phép là 20. 
Giá trị các phép đo lần lượt là: 10,3,20,40

Kết quả

Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: số phần tử của tập hợp các phép đo nhỏ nhất tạo ra sai số không vượt quá E và sai số tập hợp đó tạo ra.

Kết quả mẫu
2 17

Giải thích
Chọn phép đo thứ hai và thứ tự là giải pháp tốt nhất, cho sai số là 17. 
Sai số trong phép đo thứ nhất là 2*|10-3|=14; 
sai số trong phép đo thứ hai là |2*20-(3+40)|=3.

Link: http://vn.spoj.pl/problems/BARIC/

Solution:
DevC:

#include<stdio.h>
// #include<conio.h>

//  const char *INP="TEST.INP"; 
const int vc=1000005;

int n;
long int E;
long int M[102],tr[102],sau[102],giua[102][102],b[102][102];
int kq;
long int kq1;

long int ABS(long int x,long int y);
long int Sum(long int x,long int y);
long int Min(long int x,long int y);

int main()
{
  //  FILE *f;
  //  f=fopen(INP,"rb");
  //  fscanf(f,"%d%ld",&n,&E);
    scanf("%d%ld",&n,&E);
    kq=n;
    int i,j,k;
    for(i=0;i<n;i++) 
                  //  fscanf(f,"%ld",&M[i]);
    scanf("%ld",&M[i]);
   // fclose(f);
    // Init
    long int sum;
    for(i=0;i<n;i++)
    {
     sum=0;
     for(j=0;j<i;j++) sum+=2*ABS(M[i],M[j]);
     tr[i]=sum;
     
     sum=0;
     for(j=i+1;j<n;j++) sum+=2*ABS(M[i],M[j]);
     sau[i]=sum;
     
     for(j=i+1;j<n;j++) 
     {
      sum=0;
      for(k=i+1;k<j;k++) sum+=ABS(2*M[k],Sum(M[i],M[j]));
      giua[i][j]=sum;                    
     }
    }
    
    for(i=0;i<n;i++)
    for(j=0;j<n+1;j++) b[i][j]=vc;
    
    for(i=0;i<n;i++) b[i][1]=tr[i];
    
    for(j=2;j<n+1;j++)
    for(i=j-1;i<n;i++)
    {
     for(k=0;k<i;k++) b[i][j]=Min(b[i][j],b[k][j-1]+giua[k][i]);                   
    }
    //get answer
    kq=n+1;
    kq1=vc;
    long int tam;
    for(j=1;j<n+1;j++)
    for(i=0;i<n;i++)
    {
                 tam=b[i][j]+sau[i];
                 if(tam<=E&&(j<kq||(j==kq&&tam<kq1)))    
                 {
                  kq=j;
                  kq1=tam;                                   
                 } 
    }
    
    printf("%d%s%ld",kq," ",kq1);
   // getch();
    return 0;    
}
long int Min(long int x,long int y)
{
 if(x<y) return x;
 return y;     
}
long int ABS(long int x,long int y)
{
 if(x>=y)return x-y;
 return y-x;     
}
long int Sum(long int x,long int y)
{
 return x+y;
}

Going Once, Going Twice, Gone!

3337. Going Once, Going Twice, Gone!

Mã bài: AUCTION

Chế độ ăn kiêng của đàn bò khiến cho nông trang của nông dân John dôi ra 1 số lượng cỏ khô, vì vậy anh ta muốn bán đấu giá số cỏ khô này để trang trải phần nào chi phí chăn nuôi. Anh ta có N (1 <= N <= 1,000) bó cỏ khô giống nhau; khách hàng sẽ đấu giá để mua đống cỏ này là M (1 <= M <= 1,000) nông dân khác sống gần đó.

Mỗi một nông dân i sẽ cho nông dân John biết anh ta sẵn sàng trả P_i (1 <= P_i <= 1,000,000) đồng cho 1 bó cỏ khô. Mỗi một nông dân chỉ muốn mua 1 bó cỏ khô mà thôi.

Để đảm bảo các nông dân không ghen tị với nhau, nông dân John sẽ đưa ra 1 mức giá cố định cho tất cả người đến mua và bán các bó cỏ khô cho những ai trả giá >= mức giá đó, những người còn lại sẽ bị từ chối giao dịch.

Hãy giúp nông dân John tính xem đặt mức giá nhỏ nhất là bao nhiêu để thu được nhiều tiền nhất có thể.

Dữ liệu

* Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và M

* Dòng 2..M+1: Dòng i+1 chứa 1 số nguyên duy nhất: P_i

Kết quả

* Dòng 1: 2 số nguyên cách nhau bởi dấu cách: giá bán của John và số tiền mà John thu được

Ví dụ

Dữ liệu:
5 4
2
8
10
7

Kết quả:
7 21

Link: http://vn.spoj.pl/problems/AUCTION/

Solution:

DevC:

#include<stdio.h>

int n,m;
long int a[1001]; 
long int kq=0,gia=0;

void Doc();
void Sort(int l,int r);
void XuLi();
void Ghi();

int main()
{
    Doc();
    XuLi();
    Ghi();
    return 0;    
}
void Sort(int l,int r)
{
      int t,p,g,mid,tam;
      t=l;
      p=r;
      g=(t+p)/2;
      mid=a[g];
      while(t<=p)
      {
       while(a[t]<mid) t++;
       while(a[p]>mid) p--;
       if(t<=p)
       {
        tam=a[t];
        a[t]=a[p];        
        a[p]=tam;
        t++;
        p--;
       }                
      }
     if(l<p)Sort(l,p);
     if(t<r)Sort(t,r);
}
void Doc()
{
 
 scanf("%d",&n);
 scanf("%d",&m);
 int i;
 for(i=1;i<=m;i++) scanf("%d",&a[i]);   
}
void XuLi()
{
 int i;
 Sort(1,m);     
 for(i=1;i<=m;i++)
  if((a[i]*(m-i+1)>kq)&&(m-i+1)<=n)
  {
   gia=a[i];
   kq=a[i]*(m-i+1);                                  
  }                 
}
void Ghi()
{
 
 printf("%d%s%d",gia," ",kq);

}

Phân công hoàn thành sớm nhất

970. Phân công hoàn thành sớm nhất

Mã bài: ASSIGN1

Có n người, n việc (1 < n ≤ 200). Người thứ i thực hiện công viêc j mất C[i,j] đơn vị thời gian. Giả sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi công việc cho mỗi người sao cho thời điểm hoàn thành công việc là sớm nhất có thể.

Input

- Dòng đầu: N
- Tiếp theo là ma trận C[i,j]. (thuộc kiểu Integer)

Output

- Ghi thời điểm sớm nhất hoàn thành.

Example

Input:
4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10
Output:
5

Link: http://vn.spoj.pl/problems/ASSIGN1/

Solution:

DevC:

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<set>

#define maxC 1000
#define maxN 1005
#define INF 10000005
#define DBG true


using namespace std;



int M,N,K;
int Fx[maxN],Fy[maxN];
int matchX[maxN],matchY[maxN];
int a[maxN][maxN];
int trace[maxN];
int start,finish;
int res=0;
int mid;

int getCost(int x,int y);
void findAugmentingPath();
void SubX_AddY();
void Solve();
void printMatch();


int main(){
    /*
    if(DBG){
            freopen("G_TEST.OUT","r",stdin);
            freopen("TEST.OUT","w",stdout);
    }
    */
    // read input
    scanf("%d",&M);
//    M=max(M,N);
    int x_,y_,c;
    
//    for(int i=1;i<=M;i++)
//    for(int j=1;j<=M;j++) a[i][j]=INF;
    
    for(int i=1;i<=M;i++)
    for(int j=1;j<=M;j++){
       scanf("%d",&c);     
       a[i][j]=c;
    }    
    Solve();
//    system("pause");
    return 0;    
}
int getCost(int x,int y){
    return a[x][y]-Fx[x]-Fy[y];
}
// find path begin vertex X-dinh start
void findAugmentingPath(){
     queue<int> Q;
     memset(trace,0,sizeof(trace));
     Q.push(start);
     while(!Q.empty()){
         int x=Q.front();
         Q.pop();
         // Xet nhung Y-dinh chua tham va la 0-canh
         for(int i=1;i<=M;i++)
             if(trace[i]==0 && a[x][i]<=mid){
                 trace[i]=x;
                 if(matchY[i]==0){ 
                     finish=i;
                     return;
                 }
                 Q.push(matchY[i]);
             }   
     }  
}
//
void SubX_AddY(){
     set<int> VisitedX;
     set<int> VisitedY;
     VisitedX.insert(start);
     for(int i=1;i<=M;i++){
         if(trace[i]!=0){
             VisitedX.insert(matchY[i]);
             VisitedY.insert(i);
         }
     }
     int delta=INF;
     for(int i=1;i<=M;i++)
         if(VisitedX.find(i)!= VisitedX.end())
             for(int j=1;j<=M;j++)
                if(VisitedY.find(j)==VisitedY.end()&& getCost(i,j)<delta){
                    delta=getCost(i,j);
                }
//     printf("delta=%d\n",delta);
     //  
     for(int i=1;i<=M;i++){
        if(VisitedX.find(i)!=VisitedX.end()) Fx[i]+=delta;
        if(VisitedY.find(i)!=VisitedY.end()) Fy[i]-=delta;
     }
}
// Mo rong cap ghep tai Y-dinh finish 
void Enlarge(){
     int next;
     int x;
     while(finish!=0){
         x=trace[finish];
         next=matchX[x];
         matchX[x]=finish;
         matchY[finish]=x;
         finish=next;
     }
}
//
void Solve(){
     int min_=1;
     int max_=(1<<31)-1;
     while(min_<max_){
         mid=((min_+max_)>>1);
         res=0;
         memset(matchX,0,sizeof(matchX));
         memset(matchY,0,sizeof(matchY));
         for(int i=1;i<=M;i++){
             start=i;
             finish=0;
             findAugmentingPath();
             if(finish==0) break;
             res++;
             Enlarge();
         }
         if(res==M) max_=mid;
         else min_=mid+1; 
     }
     printf("%d",min_);
}

Kiến

2870. Kiến

Mã bài: ANT

Họ nhà kiến tổ chức một trò chơi như sau để mừng năm mới. Những chú kiến quây thành một vòng tròn. Kiến chúa sẽ đưa ra một con số và gọi nó là số M (Mồi). Bắt đầu, kiến chúa đếm số 1, theo chiều kim đồng hồ, các chú kiến lần lượt đếm số tiếp theo. Đến lượt chú kiến đếm phải số đúng bằng số M thì sẽ phải đi ra khỏi vòng tròn. Việc đếm lại từ 1 bắt đầu từ chú kiến tiếp theo, theo chiều kim đồng hồ.

Trò chơi kết thúc, khi chỉ còn lại một chú kiến. Chú kiến đó sẽ nhận được món qùa đầu năm của họ nhà kiến.

Biết số chú kiến ban đầu trên vòng tròn và số M. Hãy xác định số thứ tự của chú kiến sẽ nhận được phần thưởng may mắn. Các chú kiến được đánh số thứ tự theo chiều kim đồng hồ, bắt đầu từ kiến chúa có số hiệu 1.

Dữ liệu

• Dòng 1: chứa số nguyên dương N, là số chú kiến trên vòng tròn.
• Dòng 2: chứa số nguyên dương M.

Kết qủa

Gồm 1 dòng duy nhất, chứa số thứ tự của chú kiến sẽ nhận được món qùa đầu năm

Giới hạn

• 1 ≤ N ≤ 10¹².3 ≤ M ≤ 10⁶.
• M ≤ N.

Ví dụ

Dữ liệu
7 
3

Kết quả
4

Giải thích
Thứ tự những chú kiến phải ra khỏi vòng tròn lần lượt là: 3 6 2 7 5 1.
Chú kiến 4 là chú kiến may mắn!

Link: http://vn.spoj.pl/problems/ANT/

Solution:

DevC:

#include<cstdio>
// #include<iostream>


using namespace std;

unsigned long long int P,M,N;

int main(){
    scanf("%llu%llu",&N,&M);
    P=N*M;
    while(P>N){
        P=P+(P-N-1)/(M-1)-N;
    }
    printf("%llu",P);
//    system("pause");
    return 0;    
}

Hồ nhân tạo

3607. Hồ nhân tạo

Mã bài: ALAKE

Những ngày hè nóng nực và ngột ngạt đã đến và những chú bò đang bắt đầu kêu ca. Bác John quyết định xây một hồ nước nhân tạo. Hồ nước có thể được mô tả như 1 vùng đất 2 chiều gồm N đoạn (N<=100 000) đánh số từ 1 đến N từ trái sang phải. Đoạn thứ i được mô tả bởi 2 số nguyên W_i (1<=W_i<=1000) và H_i (1<=H_i<=1 000 000 000 lần lượt là độ rộng và chiều cao của đoạn thứ i. Không có 2 đoạn nào có độ cao bằng nhau. 2 bức tường cao vô tận chặn ở 2 đầu trái và phải. Sau đây là 1 ví dụ về hình dạng hồ nước.

        *             *  : 

        *             *  : 

        *             *  8 

        *    ***      *  7 

        *    ***      *  6 

        *    ***      *  5 

        *    **********  4 <- độ cao 

        *    **********  3 

        ***************  2 

        ***************  1 

Đoạn    |  1 |2|  3   | 

Lúc mặt trời mọc, bác John bắt đầu đổ nước vào nơi có độ cao thấp nhất với tốc độ 1 ô vuông 1x1 trên 1 phút. Nước sẽ rơi xuống đến khi nó chạm vào đáy và chảy sang các vùng bên cạnh như thông thường

  Nước              Nước tràn 

  |                       |        

* |          *      *     |      *      *            * 

* V          *      *     V      *      *            * 

*            *      *    ....    *      *~~~~~~~~~~~~* 

*    **      *      *~~~~** :    *      *~~~~**~~~~~~* 

*    **      *      *~~~~** :    *      *~~~~**~~~~~~* 

*    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~* 

*    *********      *~~~~*********      *~~~~********* 

*~~~~*********      *~~~~*********      *~~~~********* 

**************      **************      ************** 

**************      **************      ************** 

 Sau 4 phút         Sau 26 phút         Sau 50 phút 
Đoạn 1 bị phủ       Đoạn 3 bị phủ       Đoạn 2 bị phủ  

Input

Dòng 1: N


Dòng 2..N+1: dòng thứ i+1 gồm 2 số W_i và H_i



Output

Gồm N dòng, dòng thứ i ghi thời điểm mà đoạn thứ i bị mực nước phủ lên với độ cao 1



Example
Input:
3
1 4
1 7
1 2


Output:
6
11
1

Link:

Solution:
DevC:

#include<stdio.h>

// #include<conio.h>

#define MaxN 100005
const long int INF=1000000005;

long long int result[MaxN],total=0;
long int N;
long int W[MaxN];
long int H[MaxN];
long int Next[MaxN],Prev[MaxN];

int main()
{
    long int i;
 
    scanf("%ld",&N);
    i=1;
    long int pos=1;
    while(i<=N)
    {
     scanf("%d%ld",&W[i],&H[i]);
     if(H[i]<H[pos]) pos=i;
     Next[i]=i+1;
     Prev[i]=i-1;
     i++;        
    }
 
    H[0]=INF;
    H[N+1]=INF;
 
    while(H[pos]<INF)
    {
     result[pos]=total+W[pos];
     Next[Prev[pos]]=Next[pos];
     Prev[Next[pos]]=Prev[pos];
     if(H[Prev[pos]]<H[Next[pos]])
     {
      total+=(long long int )(W[pos])*(H[Prev[pos]]-H[pos]);              
      W[Prev[pos]]+=W[pos];
      pos=Prev[pos];
      while(pos>0&&H[Prev[pos]]<H[pos]) pos=Prev[pos];
     }
     else
     {
      total+=(long long int )(W[pos])*(H[Next[pos]]-H[pos]);
      W[Next[pos]]+=W[pos];
      pos=Next[pos];
      while(pos<=N&&H[Next[pos]]<H[pos]) pos=Next[pos];
     }              
    }
 
    i=1;
    while(i<=N)
    {
     printf("%lld\n",result[i]);
     i++;        
    }
 //   printf("%lld",result[i]);
 
//    getch();
    return 0;
}

Quảng cáo (VOJ)

3469. Quảng cáo

Mã bài: ADS

Nhân dịp Tết sắp đến công ty Jelly-for-Kids quyết định tăng cường việc quảng bá sản phẩm đến người tiêu dùng. Vì thế giám đốc marketing, ông Fruit-Jelly muốn gửi đi số lượng nhân viên tối đa có thể, làm nhiệm vụ tiếp thị tại đại lý trong thành phố

Trong thành phố có m con đường, n đại lý bán kẹo (đánh số từ 1 đến n). Mỗi con đường chỉ nối trực tiếp giữa 2 đại lý, và được ký hiệu bằng chỉ số của 2 đại lý mà nó nối. Đồng thời, giữa 2 đại lý bất kỳ có không quá 1 con đường nối chúng

Ông Fruit-Jelly nghĩ rằng, ông ta sẽ quản lý nhân viên dễ hơn nếu xếp mỗi người tiếp thị trên những hành trình có tính chất thứ tự. Tức là những đại lý bán kẹo trên hành trình đó thỏa các điều kiện sau

Có đường nối trực tiếp giữa 2 đại lý liên tiếp nhau trên hành trình

Từ một đại lý bất kỳ trong hành trình có thể đi qua tất cả các đoạn đường trong hành trình đó rồi trở về nơi xuất phát mà không đi qua đoạn đường nào quá một lần

Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị.

Mỗi nhân viên chỉ di chuyển trên hành trình mà anh ta được phân công. Hãy tính số lượng nhân viên tối đa mà ông Fruit-Jelly có thể xếp việc, và hành trình cụ thể mà mỗi người được xếp.

Input

Dòng đầu là 2 số tự nhiên N và M (N<=2000) (M<=5000)

Trong M dòng tiếp theo, mỗi dòng ghi 2 số nguyên mô tả một đoạn đường, mỗi đoạn đường được mô tả bởi chỉ số của 2 đại lý mà nó nối.

Output

Dòng đầu tiên ghi Q là số lượng nhân viên tối đa tìm được

Example

Input:
5 6
1 2
2 4
4 5
3 5
1 3
2 3


Output:
2

Link: http://vn.spoj.pl/problems/ADS/

Solution:

DevC:

#include<stdio.h>

#define MaxN 2005

int N,M; 

int a[MaxN][MaxN];

int free[MaxN];

int queue[MaxN];

int first=0;

int last=-1;

void Push(int x);

int Pop();

void Init_BFS();

void Init(int n);

void BFS(int t);

int Number();

int main()

{

    scanf("%d%d",&N,&M);

    

    Init(N);

    int x,y;

    int i,j;

    

    for(i=1;i<=M;i++){

                       scanf("%d%d",&x,&y);

                       a[x][y]=1;

                       a[y][x]=1;

    }

    

    int K=Number();

    

    printf("%d",M-N+K);

    return 0;    

}

void Init_BFS()

{

 first=0;

 last=-1;

}

void Init(int n)

{

 int i,j;

 for(i=0;i<=n;i++)

 {

  for(j=0;j<=n;j++){ a[i][j]=0;a[j][i]=0;}

  free[i]=1;

 }     

}

void Push(int x)

{

 queue[++last]=x;     

}

int Pop()

{

 return queue[first++];

}

void BFS(int t)

{

     int u,v;

     Init_BFS();

     Push(t);

     free[t]=0;

     

     do

     {

      u=Pop();

      for(v=1;v<=N;v++)

      if(a[u][v]&&free[v]) 

      {

       Push(v);

       free[v]=0;                     

      }         

     }

     while(first<=last);

}

int Number()

{

 int v;

 int temp=0;

 do

 {

        for(v=1;v<=N;v++) if(free[v])

        { 

          BFS(v);

          temp++;

        }

        if(v>N) break;    

 }

 while(1);    

 return temp;

}

Cleaning Up (Usaco) - CTNCLN (vnoi)

Problem 2: Cleaning Up [Paul Christiano, 2007]

In the good old days, Farmer John served a boring cuisine comprising
but a single type of cow food to his N (1 <= N <= 40000) prize dairy
cows. Times change. Today he serves the herd a total of M (1 <= M
<= N) different types of food (conveniently numbered 1..M).

The cows are picky. Cow i has a single food preference P_i (1 <=
P_i <= M) and will eat only that favorite food.

Each day at feeding time FJ converts the barn into a tastefully lit
cafeteria. The cows line up outside to enter the cafeteria in order
of their previously-mentioned convenient index number.

Unfortunately, with so many types of food, cleaning up afterwards
is very time-consuming. If Farmer John is serving K different types
of food, it takes him K*K units of time to clean the barn.

To save time, FJ serves the cows in contiguous groups from the line.
After each group, he cleans up the barn and sets out the food for
the next group (of course, he only sets out food that cows in the
any given group will eat). Determine the minimum amount of total
time FJ must spend cleaning the barn. Each group consists of the
next contiguous group of cows from the line; each cow belongs to
exactly one group; and the barn must be cleaned up after every
group, including the last one.

PROBLEM NAME: cleanup

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains a single integer: P_i

SAMPLE INPUT (file cleanup.in):

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

INPUT DETAILS:

There are four types of food and thirteen cows in line. The first
cow prefers type 1, the second type 2, the third type 1, etc.

OUTPUT FORMAT:

* Line 1: A single integer: the minimum amount of time FJ must spend
        cleaning the  barn.

SAMPLE OUTPUT (file cleanup.out):

11

OUTPUT DETAILS:

The first four groups contain one cow each. The fifth group contains
two cows who prefer food #2 (requiring one unit of time). The sixth
group contains cows preferring foods 3, 4, 3, 4, 3 (and requires
four units of time to clean). The last two groups contain one cow
each. The total time is 11.

vnoi:

Cho N số nguyên dương A1,A2...An. Mỗi số có giá trị không vượt quá N .

Yêu cầu :

Hãy chia N số này thành một số nhóm sao cho:

-Mỗi nhóm là một dãy các số liên tiếp.

-Trọng số của mỗi nhóm được tính theo công thức : Bình phương của số giá trị khác nhau trong nhóm đó.

        VD + 1 2 3 -> số giá trị khác nhau bằng 3 .

             + 1 2 1  -> số giá trị khác nhau bằng 2.

             + 1 1 1  -> số giá trị khác nhau bằng 1.

+Trọng số của dãy số bằng Tổng trọng số của tất cả các nhóm . Hãy tìm cách chia sao cho Tổng trọng số đạt giátrị nhỏ nhất.

Input

Dòng 1 : Gồm 2 số N và M - Số lượng số và số giá trị khác nhau trong dãy.

Dòng 2..N+1 : Mỗi dòng chứa một ố nguyên .

Output

Trọng số nhỏ nhất của dãy số.

Example

Input:

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
Output:
 11

Giải thích : Chúng ta sẽ chia dãy ố thành 8 nhóm 
+ 4 nhóm đầu tiên mỗi nhóm chứa một số duy nhất.
+ nhóm thứ 5 chứa hai số nguyên đều có giá trị là 2.
+ nhóm thứ 6 gồm các số từ 7->12 : (3, 4, 3, 4, 3)
+ 2 nhóm cuối cùng mỗi nhóm gồm 1 số duy nhất.

Kết quả là 1^2 + 1^2 + 1^2  + 1^2 + 1^2 + 2^2 + 1^2  + 1^2= 11.

Giới hạn: N<=40000.




Analysis:

USACO MAR09 Problem 'cleanup' Analysis

by Jaehyun Park

This is a one-dimensional DP problem. Let D[i] be the minimum amount of time needed to serve cows from 1 to i. Then D[i] is equal to the minimum value of D[k]+t(k+1, i)², for every k such that 0 <= k < i, where t(s, e) denotes the number of different types of food in the interval from s through e, inclusive. The time complexity of the algorithm is O(N²), which is too slow for the given problem.
The most important observation is that the number of different types of food within a single interval can be at most sqrt(N). If the number of different types exceeds sqrt(N), the minimum amount of time needed is at least N, but we can always get a solution of N unit times by diving the whole into groups of one.
Another minor point is that if two intervals with same end point have the same number of different types, it is always advantageous to use the longer interval, since D[i] increases as i increases.
These two observations enable us to consider only sqrt(N) different maximal intervals to calculate the value of D[i] for each i. To do so, we maintain another array of size sqrt(N) to store the minimum indices that is reachable from i with a given number of different types of food. By using the previous information, it is possible to update this array in O(sqrt(N)) time. Then the time complexity of the program is O(N^1.5), which is a huge improvement. For more detail, refer to the sample solution below.
The Korean version of the analysis is here.

//cleanup by Jaehyun Park

#include <stdio.h>
#define PROBNAME "cleanup"
#define min(a, b) (((a)<(b))?(a):(b))
#define sqr(x) ((x)*(x))
int N, M;
int P[40001];
int last_occurrence[40001];
int min_index[201], min_index_size;
int d[40001];
FILE *ifp=fopen(PROBNAME".in", "r");
FILE *ofp=fopen(PROBNAME".out", "w");

void INPUT() {
    int i;
    fscanf (ifp, "%d%d", &N, &M);
    for (i = 1; i <= N; i++)
        fscanf (ifp, "%d", &P[i]);
    P[0] = -1;
}

void PROCESS() {
    int i, j, k;
    for (i = 1; i <= M; i++)
        last_occurrence[i] = -1;
    for (min_index_size=1; sqr(min_index_size) <= N; min_index_size++);
    min_index_size--;
    min_index[0]=1;
    for(i=1;i<=N;i++) {
        k = last_occurrence[P[i]];
        for (j = 0; j <= min_index_size && min_index[j]-1 != k; j++)
            ;
        for(j--; j >= 0; j--)
            min_index[j+1]=min_index[j];
        min_index[0] = i + 1;
        d[i] = i;
        for (j = 1; j <= min_index_size; j++)
            d[i] = min(d[i], d[min_index[j]-1] + sqr (j));
        last_occurrence[P[i]] = i;
    }
}

void OUTPUT() {
    fprintf (ofp, "%d\n", d[N]);
}

void CLOSE_FILES() {
    fclose(ifp);
    fclose(ofp);
}

int main() {
    INPUT ();
    PROCESS ();
    OUTPUT ();
    CLOSE_FILES ();
    return 0;
}

http://ace.delos.com/MAR09.htm