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.
Bu prosedur ölçüsü
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)
Dostları ilə paylaş: |