| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
ROTATION - Quay bánh xe |
Nông dân John có một cái máy gặt đập cũ, máy này yêu cầu một số dây curoa được đặt trên các bánh xe khác nhau để quay các bộ phận. Động cơ sẽ làm quay bánh xe 1 theo chiều kim đồng hồ, bánh xe 1 lại được gắn kèm 1 dây curoa với bánh xe 2. Bánh xe 2 lại được gắn kèm 1 dây curoa với bánh xe 3 , v.v.. và cứ như vậy có tổng cộng N (1 <= N <= 1,000) bánh xe (và N-1 dây curoa).
Hình ở trên minh họa 2 cách đặt dây curoa giữa 2 bánh xe. Trong hình minh họa, dây curoa của bánh xe 1 đã trực tiếp làm bánh xe 2 chuyển động và quay cùng chiều với bánh xe 1 (gọi là dây curoa thẳng - straight belt). Bánh xe 3 quay kéo theo bánh xe 4 cũng quay nhờ vào dây curoa chéo (crossed belt) khiến cho bánh xe 4 chuyển động ngược chiều so với bánh xe 3 => Đảo ngược chiều chuyển động.
Cho danh sách các dạng của curoa nối các bánh xe với nhau. Biết rằng bánh xe 1 được động cơ quay theo chiều kim đồng hồ. Hãy xác định chiều quay của bánh xe N. Mỗi dây curoa được mô tả bởi 3 số nguyên:
- S_i -- bánh xe tác động (nguồn)
- D_i -- bánh xe bị tác động (đích)
- C_i -- dạng của dây curoa (0=dây thẳng, 1=dây chéo)
Thật không may, FJ lại đưa ra danh sách các dây curoa theo 1 thứ tự ngẫu nhiên.
Dưới đây là 1 ví dụ với N=4, bánh xe 1 quay theo chiều kim đồng hồ.
Dây curoa thẳng được nối tới bánh xe 2 và 3 bởi vậy mà chúng cũng chuyển động cùng chiều kim đồng hồ. Còn lại dây curoa chéo đảo ngược chuyển động vì vậy bánh xe 4 (bánh xe N) chuyển động ngược chiều kim đồng hồ.
DỮ LIỆU
- Dòng 1: Một số nguyên duy nhất: N
- Dòng 2..N: Mỗi dòng mô tả 1 dây curoa với 3 số nguyên: S_i, D_i, và C_i
KẾT QUẢ
- Dòng 1: Một số nguyên duy nhất là chiều quay của bánh xe N. (0=cùng chiều kim đồng hồ, 1=ngược chiều kim đồng hồ)
VÍ DỤ
Dữ liệu 4 2 3 0 3 4 1 1 2 0 Kết quả 1
| Được gửi lên bởi: | Jimmy |
| Ngày: | 2008-10-22 |
| Thời gian chạy: | 0.200s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED |
| Nguồn bài: | USACO October 2008 - Qualifying Round |
hide comments
|
||||||||
|
2021-05-27 18:04:08
Tham khảo: https://vnspoj.github.io/problems/ROTATION |
||||||||
|
2021-03-02 19:14:13
#include<iostream> using namespace std; long long N,x,Start,End,Type[1010]; int main() { cin >> N; for (int i = 0 ; i <= N-2 ; i++) { cin >> Start >> End >> Type[i]; if (Type[i] == 1) { x++; } } if (x % 2 == 0) { cout << 0; } else { cout << 1; } return 0; } |
||||||||
|
2020-03-03 04:26:06
xem bn c thooi |
||||||||
|
2019-02-01 12:20:01
Code mẫu tham khảo nè: https://ideone.com/aon6Y0 |
||||||||
|
2017-11-13 09:38:54
//#include <iostream> #include <stdio.h> using namespace std; int main() { int N; scanf("%d",&N); int i,x,y,z,s; s=0; for (i=2; i<=N; i++) { scanf("%d %d %d",&x,&y,&z); s=s+z; } if (s%2==0) printf("0"); else printf("1"); return 0; } 1 đấm ac luôn |
||||||||
|
2017-08-17 07:08:18 Con Bò Huyền Thoại
https://kienthuc24h.com/rotation-spoj-3202-quay-banh-xe/ |
||||||||
|
2017-01-08 12:53:55
bạn Khanh Ninh đang phức tạp hóa vấn đề rồi , thuật toán của bạn CPU2 đúng rồi |
||||||||
|
2016-11-12 09:44:25 Khanh Ninh
Bài này là phải QHD + BIT, dùng suffix array để tiền xử lý, rồi QHD trạng thái thêm 1 lần nữa, cuối cùng DFS trên những trạng thái đó. |
||||||||
|
2016-11-11 15:49:50
Quên xóa tên file input được 30 điểm :v |
||||||||
|
2016-09-07 14:15:27
1 phát AC luôn =)))) |
||||||||
RSS