International Olympiad in Informatics 2017 July 28 August 4, 2017
Yüklə 19,03 Kb. Pdf görüntüsü
|
| International Olympiad in Informatics 2017 July 28 – August 4, 2017 Tehran, Iran Day 2 Tasks simurgh Azerbaijani (AZE) Simurq "Şahnamə"də nəql olunan Qədim Fars mifologiyasına əsasən, əfsanəvi qəhrəman Zal, Kabil şəhzadəsi Rüdabəyə dəlicəsinə aşiqdir. Zal onunla evlənmək istədikdə, Rüdabənin atası Zalı sınağa çəkmək qərarına gəlir. İranda -dan -ə qədər nömrələnmiş sayda şəhər və -dan -ə qədər nömrələnmiş sayda ikitərəfli yol var. Hər bir yol iki müxtəlif şəhəri birləşdirir. İstənilən iki şəhər ən çoxu bir yol vasitəsi ilə birləşir. Bəzi yollar şah yollarıdır, və yalnız şah ailəsi tərəfindən istifadə olunduğuna görə gizli saxlanılır. Zalın tapşırığı şah yollarını tapmaqdır. Zalda İranın bütün şəhərləri və yolları olan xəritə var. O, bu yollardan hansılarının şah yolları olduğunu bilmir, amma Zalın qoruyucusu olan xeyirxah əfsanəvi Simurq quşu ona kömək edə bilər. Ancaq Simurq şah yollarını birbaşa açıqlamaq istəmir. Bunun əvəzinə, o, Zala şah yolları çoxluğunun qızıl çoxluq olduğunu deyir. Yollar çoxluğu yalnız və yalnız o zaman qızıl çoxluq olur ki, onun tərkibində sayda yol olsun və yalnız bu çoxluğun yollarından istifadə etməklə istənilən şəhərdən digərinə getmək olar. Bundan əlavə, Zal Simurqa bir neçə sual verə bilər. Hər sual üçün: 1. Zal yolların qızıl çoxluğunu seçir, və daha sonra 2. Simurq Zala seçilmiş qızıl çoxluqda olan yolların neçəsinin şah yolu olduğunu söyləyir. Sizin proqramınız Simurqa ən çoxu sual verməklə, Zalın şah yolları çoxluğunu tapmasına yardım etməlidir. Yoxlayıcı sistem Simurq rolunu oynayır. Gerçəkləşdirmə detalları Aşağıdakı proseduru gerçəkləşdirməlisiniz: int[] find_roads(int n, int[] u, int[] v) : şəhərlərin sayıdır, və : ölçülü massivlərdir. Hər bir üçün, yolu vasitəsi ilə və
şəhərləri birləşir. olan, şah yollarının nömrələrini saxlayan (istənilən ardıcıllıqla) massiv qaytarmalıdır. Sizin həlliniz aşağıdakı yoxlayıcı sistem prosedurunu ən çoxu dəfə çağıra bilər: Simurgh (1 of 3) int count_common_roads(int[] r) : ölçüsü olan, qızıl çoxluğun yollarının nömrələrini saxlayan (istənilən ardıcıllıqla) massivdir. Bu prosedur massivində olan şah yollarının sayını qaytarır. Nümunə
find_roads(4, [0, 0, 0, 1, 1, 2], [1, 2, 3, 2, 3, 3]) Bu nümunədə şəhər və yol var. vasitəsilə və şəhərlərini birləşdirən yol göstərilir. Yollar -dan -ə qədər növbəti ardıcıllıqda nömrələnmişdir: , ,
, , and
. Hər bir qızıl çoxluq yoldan ibarətdir. Tutaq ki, , və nömrəli yollar, yəni , , və
, şah yollarıdır. Onda: count_common_roads([0, 1, 2]) nəticəsi olacaq. Bu sorğu , və nömrəli yollar, yəni
, və
yolları barədədir. Bunlardan ikisi şah yoludur. count_common_roads([5, 1, 0]) nəticəsi olacaq. Bu sorğu bütün şah yolları barədədir. find_roads proseduru ya [5, 1, 0], və yaxud ölçüsü olan və bu elementləri özündə saxlayan istənilən bir massiv qaytarmalıdır. Qeyd edək ki, aşağıdakı sorğular düzgün deyil: count_common_roads([0, 1]): burada -in ölçüsü deyil. count_common_roads([0, 1, 3]): burada qızıl çoxluq deyil, çünki nömrəli şəhərdən nömrəli şəhərə yalnız , , yollarından istifadə etməklə getmək mümkün deyil.
Məhdudiyyətlər Simurgh (2 of 3) (hər bir üçün)
Hər bir üçün, yolu iki müxtəlif şəhəri birləşdirir (i.e., ). İstənilən iki şəhər arasında ən çoxu bir yol var. Yollar vasitəsi ilə istənilən iki şəhər arasında səyahət etmək mümkündür. Bütün şah yolları çoxluğu qızıl çoxluqdur. find_roads proseduru count_common_roads prosedurunu ən çoxu çağırmalıdır. Hər sorğuda çoxluğunda təyin edilmiş yollar qızıl çoxluq təşkil etməlidir. Altməsələlər 1. (13 xal) , 2. (17 xal) , 3. (21 xal) , 4. (19 xal) və istənilən iki şəhər arasında bir yol var. 5. (30 xal) Nümunə yoxlayıcı Nümunə yoxlayıcı giriş verilənlərini aşağıdakı formatda oxuyur: sətir : sətir
(for all ):
sətir : Burada şah yollarının nömrələridir. Nümunə yoxlayıcı yalnız o zaman YES cavab verir ki, find_roads proseduru count_common_roads prosedurunu ən çoxu dəfə çağırmış olsun, və nəticə olaraq düzgün şah yolları çoxluğunu qaytarsın. Əks halda cavab NO olacaqdır. Diqqət edin ki, nümunə yoxlayıcı olan count_common_roads proseduru çoxluğunun qızıl çoxluğa məxsus bütün xüsusiyyətlərə malik olmasını yoxlamır. Bunun yerinə, o, sadəcə massivində olan şah yollarını sayır və nəticə olaraq qaytarır. Buna baxmayaraq, əgər sizin proqramınız count_common_roads prosedurunu qızıl çoxluq təşkil etməyən nömrələrlə çağırarsa, yoxlamanın nəticəsi 'Wrong Answer' olacaqdır. Texniki qeyd count_common_roads proseduru, effektivlik səbəbinə görə, C++ və Pascal dillərində massivin özünü deyil, onun ünvanını (pass by reference) qəbul edir. Bununla belə, proseduru həmişəki kimi adi qaydada çağıra bilərsiniz. Yoxlayıcı sistem massivində olan qiymətlərin dəyişməyəcəyinə təminat verir. Simurgh (3 of 3) Yüklə 19,03 Kb. Dostları ilə paylaş:
|