• Lớp Học
  • Tin Học
  • Mới nhất

SH08-200 Tom and Jerry Tom và Jerry đang chơi một trò chơi để phân định, ai thắng sẽ được lấy miếng phô mai cuối cùng trong tủ lạnh. Trò chơi như sau: Cho 1 số nguyên dương N, Tom và Jerry chơi luân phiên, Tom sẽ được đi trước. Ai tới lần chơi sẽ phải tìm một số nguyên A (A<N) là ước của N, sau đó N sẽ bị trừ đi A. Ai không tìm được số A nữa sẽ thua cuộc. Cho biết số nguyên N hãy xác định Tom hay Jerry thắng Mô tả đầu vào Dòng 1 ghi số nguyên T là số bộ Test T dòng tiếp theo, mỗi dòng ghi số nguyên N Ràng buộc 1\leq T \leq 100; 1\leq N \leq 10^61≤T≤100;1≤N≤10 6 Mô tả đầu ra T dòng ghi số: 1: Nếu Tom thắng 0: Nếu Jerry thắng Hướng dẫn: • Nếu N=1 => Người chơi đầu thua • Nếu N=2 => Người chơi đầu thắng • Giả sử: N ban đầu chẵn => Người chơi đầu có thể chọn 1 trong 2 cách sau o Trừ N đi 1 vì 1 là ước của N o Trừ đi bất kì ước nào của N ( ngoài ước 1 và N)  Nếu chọn cách trừ 1 => N-1 là số lẻ => ước của (n-1) luôn là số lẻ => Người chơi 2 chọn bất kì ước nào đi nữa thì sau khi người 2 chơi đều cho 1 số N mới là một số chẵn (vì (n-1) lẻ - 1 số lẻ => cho kq chẵn)  Từ đây => Nếu N ban đầu chẵn thì người đi đầu luôn thắng. • Nếu N lẻ với tư tưởng trên bạn biết người nào chiến thắng rồi đấy • Nói dài dòng tóm lại là gì? Kết quả bài toán phụ thuộc vào n-1 là số chẵn hay lẻ???? (Vì sao) Test case mẫu Đầu vào mẫu 1 2 2 4 Đầu ra mẫu 1 1 1 C++ nha

1 đáp án
35 lượt xem

SH07-200 Mices Có N con chuột trong 1 đương hầm thẳng hẹp ( Chỉ cho phép 1 con chuột đứng ở một chỗ tại một thời điểm). Có N cái ổ chuột nằm dọc theo đường hầm, một con chuột có thể ở nguyên vị trí của nó hoặc di chuyển một bước sang phải từ vị trí x sang x+1 hoặc một bước sang vị trí x-1. Mỗi bước di chuyển tiêu tốn 1 phút . Giả sử đường hầm là trục số nguyên Ox, biết vị trí N con chuột và N ổ chuột, hãy tính số phút tối thiểu để con chuột cuối cùng chui được vào ổ? Mô tả đầu vào Dòng 1 ghi số nguyên T là số bộ test cần kiểm tra Mỗi bộ test gồm: Dòng đầu: Chứa số nguyên N Dòng thứ 2: Chứa N số nguyên khác nhau cho biết vị trí của N con chuột Dòng thứ 3: Chứa N số nguyên khác nhau cho biết vị trí của N tổ chuột Ràng buộc 1\leq T \leq 100; 1\leq N \leq 10^41≤T≤100;1≤N≤10 4 Vị trí của các con chuột và tổ chuột là số nguyên có giá trị tuyệt đối không quá 10^710 7 Mô tả đầu ra Ứng với mỗi bộ test in ra số giây tối thiểu để con chuột cuối cùng chui vào ổ của nó Hướng dẫn: • Ở đây đều là những chú chuột thông minh thì chắc chắn sẽ chui vào hang gần nó nhất nhé. • Vậy bài này có thuật toán (cách giải) đơn giản là: o Sort lại vị trí đang đứng của con chuột o Sort lại vị trí của hang o Phút 1: Những con đứng đúng vị trí hang vào hang, những con gần hang tiến lại hang của nó 1 bước.... cứ như thế phút thứ k thì con chuột cuối cùng sẽ chui vào hang => đi tìm k và lúc này k chính là số bước để con chuột xa hang của nó nhất về đúng hang đó, hay k=max(∣ai−bi∣) Test case mẫu Đầu vào mẫu 1 1 3 4 -4 2 4 0 5 Đầu ra mẫu 1 4 C++ nha

1 đáp án
39 lượt xem
1 đáp án
32 lượt xem
2 đáp án
32 lượt xem
2 đáp án
37 lượt xem
2 đáp án
61 lượt xem
2 đáp án
40 lượt xem
2 đáp án
44 lượt xem