[Solved] Bộ đề Leon sưu tầm

[Leon88]

Tớ lập ra topic này để chia sẻ các bài tập mà tớ sưu tầm được. Hy vọng các bạn ủng hộ làm tiếp tớ với .
Bai 1. Đổi vé (trích từ đề thi Olympic Tin học sinh viên toàn quốc năm 2001)
Trong ngày hội thể thao văn hoá tại sân vận động trung tâm thành phố sẽ có một trận đấu bóng đá của đội CHAMPION gặp đội ngôi sao của thành phố và một buổi biểu diễn của dàn nhạc nổi tiếng OLYMPIAD. Vé vào xem sẽ được phát cho từng cá nhân của các tập thể có nhiều thành tích trong phong trào thể thao văn hoá, mỗi tập thể được phát một loại vé, trên vé có ghi tên cụ thể người để phục vụ cho việc giữ gìn an ninh trật tự.
Tập thẻ sinh viên của một trường gồm N người nhận vé xem bóng đá, nhưng tất cả lại đều muốn đi xem ca nhạc. Rất may là ban tổ chức cho phép tập thể đổi vé theo hình thức sau: những người có vé vào sân vận động phải tham gia một số công việc phục vụ cho việc chuẩn bị, mỗi công việc cần đúng M người thực hiện. Sau khi hoàn thành công việc, ai có vé xem bóng đá được đổi thành vé vào xem ca nhạc và ngược lại, ai có vé xem ca nhạc được đổi thành vé xem bóng đá. Trưởng đoàn sinh viên quyết định tổ chức cho các bạn đi lao động để đổi vé. Trưởng đoàn chỉ định M bạn đi lao động và đổi vé. Sau khi các bạn đó về lại tổ chức nhóm khác đi đổi. Một người có thể tham gia đổi vé nhiều lần nếu cần, nhưng không được đi đổi vé hộ người khác.
Yêu cầu : Hãy xác định tối thiểu phải tổ chức bao nhiêu nhóm đi lao động đỗi vé để tất cả N thành viên của tập thể đều đổi được vé đi xem ca nhạc hoặc cho biết không có cách thực hiện được điều đó.
Dữ liệu : Vào file văn bản Ticket.inp, bao gồm nhiều dòng mỗi dòng 2 số nguyên N, M cách nhau ít nhất một dấu cách, mỗi dòng ứng với một trường hợp cần xử lý. 1<=N<=2000, 1<=M<=200
Kết quả : Đưa ra file văn bản Ticket.out, mỗi dòng một số nguyên K - số lần đi đổi vé ứng với một cặp N, M của dự liệu vào. K=-1 trong trường hợp không có cách đổi vé cho tất cả mọi người.
EX :
Ticket.inp
15 10
23 7


Ticket.out
-1
5

Thêm vài ví dụ :
Có 30 vé xem bóng đá. (N=30)
Cần 4 người để làm việc (M=4)
Sau 9 lần làm việc thì mới đổi dc vé xem bóng đá ra vé xem ca nhạc hết.

Có 1000 vé xem bóng đá. (N=1000)
Cần 35 người để làm việc (M=35)
Sau 30 lần làm việc thì mới đổi dc vé xem bóng đá ra vé xem ca nhạc hết.


Có 333 vé xem bóng đá. (N=333)
Cần 50 người để làm việc (M=50)
-1 Không thể đổi dc

[rox_rook]

Mình chưa hiễu rõ cái đề lắm , Leon có thể cho thêm vài cái test ví dụ được không ? Cám ơn Leon trước nhé ! Thân !

[kidkid]

À hiểu thì tớ có hiểu thế này:
Ví dụ như với N =5, M=4 thì đề sẽ dịch xuôi như thế này:

Đoàn có 5 người muốn đổi vé từ vé xem bóng đá sang xem ca nhạc. Muốn đổi thì phải đi lao động . Do đó trưởng đoàn quyết định tổ chức các nhóm đi lao động để đổi số vé này:
Nhóm chỉ có thể đi 4 người nên lần thứ nhất có 4 người đổi được vé 1 người ko đổi được. Cứ thế cậu sẽ tìm cách như thế nào đấy để đổi cho được hết tất cả số vé cần thiết. Hãy nhớ đến điều này : Cứ mỗi lần đi lao động thì vé bóng đá sẽ đổi thành vé ca nhạc. có nghĩa là cứ số lần đi lao động là chẵn thì anh đó nắm vé bóng đá, còn là lẻ thì đang có vé ca nhạc.

Thử nhé.

[rox_rook]

Bài này mình có cách giải như sau, cái đề này nhìn vào thì ghê ghớm chứ thật ra bản chất là Toán thui.
- Trường hợp N chia hết cho M thì N/M là số cách tối thiểu luôn.
- Trường hợp N chia M dư k :
+ Nếu k lẻ không có cách.
+ Nếu k chẵn, số cách tối thiểu là N/M + 2.

Còn CM mấy cái trên thì có lẽ lấy toán CM thôi cũng không khó lắm. Nhưng chỉ là suy nghĩ chủ quan của mình thôi, đành chờ tác giả trả lời vậy ! Thân !

#include <iostream>
#include <iomanip>

int N;
int M;


int main()
{
      cout << "Enter the number of student : ";
      cin >> N;
      cout << "How many student can go per turn: [M < N] ";
      cin >> M;
        
      if ( (N%M)%2 == 0 )
      {         
            cout << "The minimum turn is : ";
            cout << N/M + 2; 
      }
      else
      {
            cout << "No way!!!";
      }
        
        return 0;
} 

[Leon88]

Kết quả : của N = 10 , M = 10 ra 3 ... trong khi chỉ cần 1 lần đổi . Bài này làm kiểu này ko đúng rùi.
Thêm VD :
55 và 3 ra 21

[rox_rook]

Uhm srry Leon nhé! Làm ẩu quá. Cái trường hợp 10 10 thì càng tệ hơn ^^ Quên code vào. Để mình suy nghĩ lại ! Cám ơn Leon đã chỉ ra !

[rox_rook]

hì hì ! Leon check thử cái này xem sao nhé !

#include <iostream>
#include <iomanip>

const int maxx = 100;
int G;
int A[maxx][2];


void Initialization()

    {
      cout << "Enter the number of group : ";
      cin >> G;
      
      for ( int i = 1; i <= G; i++ )
      {
            for ( int j = 1; j <= 2; j++ )
            {
                  cout << "Enter N :";
                  cin >> A[i][j];
                  cout << "Enter M :";
            }
            cout << "\n------------------------------------\n";
            cout << "\n----End task group [" << i << "]----\n";
            cout << "\n------------------------------------\n";
            cout << "\n\n\n\n\n";
      }
}


int Process( int N, int M)

    {
      
      if ( N%M == 0 )
      {
            return N/M;
      }
      else
      {
            if ( (M%2) == 0 ) 
            {
                  if ( ((N%M)%2) != 0 ) 
                  {
                        return -1;
                  }
                  else 
                  {
                        return N/M + 2;
                  }
            }
            else 
            {
                  if ( ((N%M)%2) != 0 ) 
                        return N/M + 3;
                  else
                        return N/M + 2;
            }
      }
}

void ReadData()

    {
      
      for ( int i = 1; i <= G; i++ )
      {
            int x = Process ( A[i][1], A[i][2] );
            if ( x == -1 ) 
            {
                  cout << "Sorry, No way for you guys group [" << i  << "]" << endl;
            }
            else
            {
                  cout << "Minimum turn for group [" << i << "] : " << x << endl;
            }
      }      

}

int main()

    {
      Initialization();
      ReadData();
      
     
      return 0;
} 

[Leon88]

Bài của Rox Rook, làm dự trên sự tính toán ra kết quả cũng làm tôi khá ngạc nhiên ... thứ nhất nhờ kiểu này nên chương trình tính rất nhanh ... thứ hai kết quả ra chính xác cao... tôi test thì chưa tìm ra dc kết quả nào sai với bài của rox

Bài 2. Cơ số -2
Nhập vào 2 số ở dạng 1 và 0 ( cơ số -2). Đổi cơ số -2 ra cơ số thập phân như sau :
TD : 11010
Ta có : 0 -2 4 -8 16 -32 64 -128 256 ....( tương đương với (-2)^0 , (-2)^1, (-2)^2 ....
X = 1.(-2)^4 + 1.(-2)^3 + 0.(-2)^2 + 1.(-2)^1 + 0.(-2)^0
X = 16 -8 +0 -2 =6
Vậy số 11010(-2) đổi ra thập phân dc 6.
Viết chương trình nhập vào 2 số (cơ số -2) và xuất ra tổng và hiệu 2 số.
VD :
Input :
111
11011
Output :
11110
1100