International Olympiad in Informatics 2017 July 28 August 4, 2017



Yüklə 19,03 Kb.

tarix25.06.2018
ölçüsü19,03 Kb.


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


,



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)   



: tasks -> day2


Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2019
rəhbərliyinə müraciət

    Ana səhifə