ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА Ямбо

ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА
Ямбол, 13 юни 2009 г.
Група А (11-12 клас)

Задача A2. ИГРА
Юни месец е, дните са дълги, нощите топли и ароматни. Като всяка друга млада
влюбена двойка, Ели и приятелят й прекарват часове наред заедно, попаднали в
обятията на ... компютърните игри. Превъртяли WоW, стигнали 100-тно ниво на Diablo
и изиграли всяка random карта на Heroes, сега те са се захванали с малко по-
нестандартна игра. Всяко ниво от играта може да се представи като неориентиран граф,
всеки връх на който е оцветен в бяло или черно. „Съюз” на върха v е множеството,
съдържащо v и всички върхове с неговия цвят, които могат да бъдат достигнати от v,
през върхове със същия цвят. Операцията „смяна на съюза на v” се състои в смяна на
цвета на всички върхове в съюза на v. На фигурата е показан графи, преди и след
прилагане на операцията върху върха, означен с Х.




Целта на играта за всяко ниво е да се направят всички върхове бели или черни (в
зависимост от нивото). Очевидно това винаги е възможно; за съжаление смяната на
съюза на един връх отнема известно време (на по-сложните нива отнема повече време).
Например, ако за графа вляво на фигурата една смяна на съюза отнема 14 единици
време и искаме да направим целия граф бял, то минималното време за цялото ниво ще е
3 * 14 = 42 единици време. Оптималната игра изисква използване на операцията два
последователни пъти върху бял в началото връх (например, единствения връх с един
съсед) и после използване на операцията върху изолирания черен връх.
Елеонора и приятелят й играят едновременно, като могат да си поделят нивата по
произволен начин (и двамата са еднакво добри), но всяко ниво трябва да се изиграе от
точно един от двамата. Редът, в който играят нивата е без значение.
От вас се иска да напишете програма gaming, която намира минималното време, за
което двамата могат да изиграят всички нива.
Вход
На първия ред на стандартния вход е зададен броят нива L на играта. На следващите
няколко реда е описано първото ниво, после второто и така нататък. Всяко ниво
започва с ред, съдържащ целите числа Ni, Mi, Ci и Ti – броя на върхове в i-тия граф, броя
на ребрата в същия граф, цвета, в който трябва да бъде оцветен целия граф за да се
премине нивото (0 за бяло и 1 за черно) и времето, което отнема всяка операция.
Следва ред с Ni числа (0 или 1), разделени с по един интервал, задаващи началните
цветове на всеки от връховете. След тях са зададени Mi реда с по една двойка числа x и
y, краищата на неориентирано ребро между върхове с индекси x и y (номерацията на
върховете е от 0 до Ni – 1). С това описанието на i-тото ниво завършва и започва
описанието на следващото (ако има такова). Преди описанието на всяко ниво ще има по
един празен ред (вижте примерния вход).

------------------------- Converted by Unregistered Simpo PDF Converter -------------------------
ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА
Ямбол, 13 юни 2009 г.
Група А (11-12 клас)
Изход
На един ред на стандартния изход програмата трябва да изведе минималното време,
необходимо за завършването на играта (играта е занършена, когато всяко ниво е
изитрано от един от двамата).
Ограничения: Брой нива: 1 ≤ L ≤ 30. Брой върхове в ниво: 1 ≤ N ≤ 50. Брой ребра в
ниво: 0 ≤ М ≤ 2500. Цвят за завършване: C = 0 или C = 1. Време за смяна на съюза: 0 ≤ T
≤ 500 000. Индекси на върховете: 0 ≤ x, y ≤ N – 1. В 60% от тестовете всички Ni ще са не
по-големи от 12.
ПРИМЕР
Вход Изход
3 16

3 209
0 10
0 1
1 2

7 705
1 100101
2 0
1 2
0 3
2 3
3 4
4 5
6 5

2117
10
01


Пояснение: Първо и трето ниво могат да се преминат с по един ход: в първо ниво –
като сменим цвета на връх 1 от черен в бял; в трето – на връх 1 от бял в черен. Второ
ниво може да се премине с най-малко 3 хода. Като сменим първо цвета на връх 2 от бял
в черен, а после от черен в бял, ще оцветим всички върхове без връх 6 в бяло. С третия
ход сменяме цвета на връх 6 от черен в бял. Времената, необходими за преминаване на
трите нива, са съответно 9*1 = 9, 3*5 = 15 и 7 * 1 = 7. Оптимално разпределение на
нивата между двамата играчи е: първо и трето ниво за единия, а второ – за другия.
Минималното необходимо време е max(9 + 7, 15) = 16.

------------------------- Converted by Unregistered Simpo PDF Converter -------------------------

Kết quả (Việt) 1:

GIẢI ĐẤU MÙA XUÂN TIN HỌC Yambol, 13 tháng 6 năm 2009. Nhóm (11-12) Nhiệm vụ A2. TRÒ CHƠITháng sáu là một tháng, những ngày là dài, đêm ấm áp và thơm. Giống như bất kỳ trẻ khácCặp vợ chồng trong tình yêu, Ellie và bạn trai của cô dành giờ với nhau, đánh bắt lên trongcánh tay của... trò chơi máy tính. Fucked trong WoW, đạt 100 cấp tandard Diablovà chơi mỗi bản đồ ngẫu nhiên của anh hùng, họ đang làm với nhiều hơn một chúttrò chơi phi tiêu chuẩn. Mỗi cấp độ của trò chơi có thể được biểu diễn như một số không có bánh lái,mỗi đỉnh màu trắng hoặc màu đen. "Liên minh" ở đầu là thiết lập v,có v và tất cả các đỉnh núi với màu sắc của nó, mà có thể được đạt đến từ v,trong các đỉnh núi của cùng một màu sắc. "Thay đổi hoạt động của v Union" bao gồm thay thế cácmàu sắc của các đỉnh núi tất cả trong các công đoàn của v. con số cho thấy cột trước và sau khiCác ứng dụng hoạt động trên đầu trang, được đánh dấu với x.Mục tiêu của trò chơi cho mỗi cấp độ là để làm cho tất cả các đỉnh núi (trong màu trắng hoặc đenTùy thuộc vào mức độ). Rõ ràng là điều này luôn luôn có thể; Thật không may, sự thay đổi củaLiên minh của một đỉnh mất một thời gian (các đơn vị phức tạp hơn mất thêm thời gian).Ví dụ, nếu cột bên trái của con số một trong những thay đổi của các công đoàn có 14 đơn vịthời gian và muốn làm cho toàn bộ số lượng màu trắng, sau đó thời gian tối thiểu cho cấp độ toàn bộ sẽ3 * 14 = 42 đơn vị thời gian. Trò chơi tối ưu đòi hỏi việc sử dụng hai hoạt độnglần liên tiếp trên đỉnh núi trắng trong đầu (ví dụ, có đỉnh chỉ với mộthàng xóm) và sau đó sử dụng các hoạt động đen trên bị cô lập.Eleonora và bạn trai của cô chơi cùng một lúc, như có thể chia sẻ các cấpbất kỳ cách nào (cả hai đều bằng nhau tốt), nhưng mỗi cấp phải được chơi bởi cácchính xác một trong hai. Thứ tự trong đó mức độ chơi là không thích hợp.Bạn sẽ được yêu cầu để viết một chương trình tìm thấy thời gian tối thiểu chơi GameCả hai chúng tôi có thể chơi tất cả các cấp.Đăng nhậpDòng đầu tiên của các đầu vào tiêu chuẩn được thiết lập để số lượng các cấp độ của trò chơi L. Tiếp theomột vài dòng mô tả mức độ đầu tiên, sau đó thứ hai và vân vân. Mỗi cấp độbắt đầu với các dòng có chứa số nguyên Ni, Ti, Mi và Ci-số đỉnh trong Graf i-th, sốCác xương sườn trong số tương tự, trong đó màu sắc nên được tô màu tất cả các tính đểvượt qua mức độ (0 cho màu đen trắng và 1) và thời gian hoạt động mỗi.Sau một hàng với số Ni (0 hay 1), cách nhau bằng một không gian, trên ban đầumàu sắc của mỗi của vr″hovete. Sau khi họ được thiết lập phù hợp với Mi một cặp số x vày, các cạnh của các xương sườn neorientirano giữa các đỉnh núi với chỉ số x và y (cách đánh số củađỉnh có từ 0 tới Ni-1). Với này mô tả của i-thứ cấp kết thúc và bắt đầutrò chơi mô tả tiếp theo (nếu có). Trước khi mô tả của mỗi cấp độ sẽ có mộtmột dòng trống (xem ví dụ đầu vào).---Chuyển đổi bởi chưa Simpo PDF Converter--- GIẢI ĐẤU MÙA XUÂN TIN HỌC Yambol, 13 tháng 6 năm 2009. Nhóm (11-12)Lối raMột dòng trên đầu ra tiêu chuẩn chương trình nên đầu ra thời gian tối thiểu,cần thiết để hoàn thành trò chơi (các trò chơi là zan″ršena, nơi mà mỗi cấpizitrano từ một trong hai).Hạn chế: số lượng cấp: 1 ≤ L ≤ 30. Số lượng các đỉnh núi ở cấp độ: 1 ≤ N ≤ 50. Số lượng xương sườn trongmức độ: 0 ≤ m ≤ 2500. Hoàn thành màu: C = 0 hay C = 1. Thời gian để thay đổi liên minh: 0 ≤ T≤ 500 000. Các chỉ số của đỉnh: 0 ≤ x ≤ y, N-1. 60% của tất cả các bài kiểm tra sẽ không có Nilớn tuổi hơn 12.VÍ DỤĐầu vào đầu ra3 163 2090 100 11 27 7051 1001012 01 20 32 33 44 56 521171001Làm rõ: mức độ đầu tiên và thứ ba có thể chuyển đổi với một di chuyển: ở cấp độ đầu tiên-Khi chúng tôi thay đổi màu sắc của đỉnh 1 từ đen trắng; Thứ ba — đầu 1 trắng đen. Thứ haicó thể di chuyển cấp với ít nhất 3 di chuyển. Khi chúng tôi thay đổi màu sắc đầu tiên của đầu 2 trắngmàu đen, và sau đó màu đen trong màu trắng ngọn sẽ tất cả mà không cần đầu 6 trong trắng. Với thứ bakhóa học thay đổi màu sắc của top 6 từ đen sang màu trắng. Thời gian cần thiết cho các đoạn văn củaCác đơn vị chính là 9 * 1 = 9, 3 * 5 = 15 và 7 * 1 = 7. Phân bổ tối ưumức độ giữa hai người chơi là: mức độ đầu tiên và thứ ba đối với một, và thứ nhì, cho người khác.Thời gian tối thiểu cần thiết là tối đa (9 + 7, 15) = 16.---Chuyển đổi bởi chưa Simpo PDF Converter---

Kết quả (Việt) 2:

SPRING TOURNAMENT IN TIN
Yambol, 13 Tháng sáu 2009
Nhóm A (11-12 lớp) Nhiệm vụ A2. Game tháng sáu tháng, những ngày dài, những đêm ấm áp và thơm. Giống như bất kỳ thanh niên khác cặp vợ chồng trong tình yêu, Ellie và bạn trai của cô đã dành hàng giờ với nhau, bị cuốn vào vòng tay của ... trò chơi máy tính. WoW đặt cược, họ đạt đến 100 độ lại của Diablo và đóng tất cả các bản đồ ngẫu nhiên của anh hùng, bây giờ họ đã tham gia vào một hơi trò chơi bất thường. Mỗi cấp độ của trò chơi có thể được biểu diễn như là đồ thị vô hướng, mỗi đỉnh trong số đó là màu trắng hoặc đen. "Liên minh" trên v đầu là tập chứa tất cả các đỉnh v và với màu sắc của nó, mà có thể đạt được từ v, thông qua các đỉnh núi của cùng một màu sắc. "Chiến dịch đổi đoàn v" là để thay đổi màu sắc của tất cả các đỉnh núi trong các công đoàn của v. Hình minh họa cho thấy đồ thị trước và sau khi sử dụng các hoạt động trên mũi, biểu hiện bằng X. Các trò chơi Mục tiêu của mỗi cấp là để làm cho tất cả các đỉnh núi trắng hoặc đen (trong sự phụ thuộc vào mức độ). Rõ ràng là nó luôn luôn là có thể; Thật không may là sự thay đổi của các công đoàn của một đỉnh mất một thời gian (mức phức tạp hơn sẽ dài hơn). Ví dụ, nếu một cột bên trái của hình thay người của Liên minh có 14 đơn vị của thời gian và muốn làm toàn bộ số lượng bạch, thời gian tối thiểu tất cả các cấp độ sẽ là 3 * 14 = 42 đơn vị thời gian. Trò chơi tối ưu đòi hỏi việc sử dụng phẫu thuật hai lần liên tiếp trên đỉnh đầu màu trắng (ví dụ, chỉ có đỉnh cao với một người hàng xóm) và sau đó sử dụng các hoạt động trên mũi đen bị cô lập. Eleanor và bạn bè của cô chơi cùng một lúc, họ có thể chia sẻ mức độ trong một cách tuỳ tiện ( cả hai đều tốt như nhau), nhưng mỗi cấp phải được chơi bởi chỉ một trong số họ. Thứ tự mà các sân chơi là không thích hợp. Bạn được yêu cầu viết một game chương trình, đó là thời gian tối thiểu để mà họ có thể chơi tất cả các cấp. Đăng nhập Dòng đầu tiên của cấp độ đầu vào thiết lập số L của trò chơi. Trong kế tiếp vài dòng mô tả mức độ đầu tiên, sau đó thứ hai và như vậy. Mỗi cấp độ bắt đầu bằng một dòng chứa số nguyên Ni, Mi, Ci và Ti - số đỉnh của i-Đếm số lượng của xương sườn trong cùng một đồ thị, màu sắc, mà nên được sơn xung quanh Count để vượt qua mức (0 cho màu trắng và một màu đen) và thời gian cần mỗi hoạt động. chèo số Ni (0 hoặc 1), cách nhau bởi một dấu cách, gây ra một đầu màu sắc của mỗi đỉnh. Một khi chúng được thiết lập đường dây Mi với một cặp số x và y, tất cả các xương sườn bị mất phương hướng giữa đỉnh chỉ số của x và y (đánh số các ngọn từ 0 đến Ni - 1). Với mô tả của các cấp độ thứ i kết thúc và bắt đầu mô tả của các tiếp theo (nếu có). Trước khi mô tả của mỗi cấp sẽ có một dòng trống (xem mẫu đầu vào). ------------------------- Chuyển Đổi bởi Khách Simpo PDF Converter - ----------------------- SPRING TOURNAMENT IN TIN Yambol, 13 Tháng sáu 2009 Nhóm A (11-12 lớp) Output Trên một dòng duy nhất của chuẩn đầu ra nên đã đặt thời gian tối thiểu cần thiết để hoàn thành trò chơi (trò chơi là zanarshena khi mỗi cấp là izitrano của một trong hai). Hạn chế: Số lượng: 1 ≤ L ≤ 30. Số điểm ở mức 1 ≤ N ≤ 50. Số xương sườn ở mức 0 ≤ M ≤ 2500. Màu hoàn thành: C = 0 hoặc C = 1. Thời gian để thay đổi các đoàn: 0 T ≤ ≤ 500 000 Chỉ số ngọn: 0 ≤ x, y ≤ N - 1. Trong 60% của tất cả các bài kiểm tra không Ni để lớn hơn 12. VÍ DỤ Input Output 3 16 3 209 0 10 0 1 1 2 7 705 1 100 101 2 0 1 2 0 3 2 3 3 4 4 5 6 5 2117 10 01 Giải thích : Đầu tiên và mức độ thứ ba có thể đi với một thái: ở cấp độ đầu tiên - như thay đổi màu sắc của các tip của một màu đen trắng; ở một phần ba - một trong những đỉnh cao trong màu trắng đen. Thứ hai cấp độ có thể được thông qua bằng ít nhất ba nét. Bằng cách thay đổi màu sắc của các đỉnh cao đầu tiên 2 từ màu trắng sang màu đen và sau đó màu đen trắng, sẽ tô màu các đỉnh của tất cả các đỉnh núi mà không có sáu màu trắng. Vào thứ ba tất nhiên thay đổi màu sắc của các tip 6 từ màu đen sang màu trắng. Thời gian cần thiết để thông qua ba cấp độ tương ứng là 9 * 1 = 9, 3 * 5 = 15 7 * 1 = 7 phân phối tối ưu của các cấp giữa hai cầu thủ là: đầu tiên và mức độ thứ ba trong một, và thứ hai - cho khác . Thời gian tối thiểu cần thiết là max (9 + 7, 15) = 16. ------------------------- Chuyển Đổi bởi Khách Simpo PDF Converter --- ----------------------