Oyun#7762
Kiçik oğlan Can-Ci oyun oynamağı çox sevir. Ona sual verildikdə, sadə cavab vermək əvəzinə, oyun təklif edir.
Can-Ci dostu Mey-Yu ilə görüşdü və ona Tayvanda aviareyslər şəbəkəsinin necə qurulduğunu izah etdi. Xüsusilə, Tayvanda n şəhər var, bunlar 0-dan n - 1-ə qədər nömrələnib. Bu şəhərlər arasında bəzi iki tərəfli aviareyslər mövcuddur.
Mey-Yu Can-Ci-dən soruşdu ki, həqiqətənmi, yalnız aviareyslərdən istifadə edərək hər hansı bir şəhərdən digərinə getmək mümkündürmü. Can-Ci isə sualı cavablandırmaq əvəzinə oyun təklif etdi.
Mey-Yu belə suallar verə bilər: "Şəhərlər x və y birbaşa aviareyslə bağlıdırmı?". Can-Ci hər sualı dərhal cavablandırmalıdır. Mey-Yu hər şəhər cütlüyü haqqında yalnız bir dəfə soruşur, yəni ümumilikdə r = n * (n - 1) / 2 sual verir. Mey-Yu oyunu qazanmış sayılır əgər ilk i sualın cavablarını aldıqdan sonra, bəzi i < r üçün, aviareyslər şəbəkəsinin əlaqəli olub-olmadığını müəyyən edə bilirsə. Bu, yalnız aviareyslərdən istifadə edərək hər hansı bir şəhərdən digərinə getməyin mümkün olduğunu göstərir. Əgər ona bütün r sualları vermək lazım gəlsə, Can-Ci qazanır.
Oyunu daha maraqlı etmək üçün dostlar razılaşdılar ki, Tayvanda mövcud olan aviareyslər şəbəkəsini unudacaqlar və oyunun gedişində öz şəbəkələrini quracaqlar, Mey-Yu-nun əvvəlki suallarına əsasən cari suala cavab seçəcəklər. Can-Ci-yə oyunu qazanmağa kömək edəcək bir proqram yazmaq lazımdır, hansı ki, hər suala necə cavab verməli olduğunu həll edəcək.
Oyunun qaydalarını aşağıdakı üç nümunədə nəzərdən keçirəcəyik. Hər bir nümunədə n = 4 şəhər və r = 6 sual-cavab raundu var.
Birinci nümunədə (aşağıdakı cədvəl) Can-Ci uduzur, çünki 4-cü sualdan sonra Mey-Yu əmindir ki, yalnız aviareyslərdən istifadə edərək hər hansı iki şəhər arasında uçmaq mümkündür, 5 və 6 suallarının cavablarından asılı olmayaraq.
Növbəti nümunədə Mey-Yu üçüncü sualdan sonra müəyyən edə bilir ki, Can-Ci qalan suallara necə cavab versə də, yalnız aviareyslərdən istifadə edərək 0 şəhərindən 1 şəhərinə getmək mümkün deyil. Bu halda Can-Ci yenə uduzur.
Son nümunədə Mey-Yu bütün 6 sualın cavablarını alana qədər cavabı müəyyən edə bilmir, buna görə Can-Ci qazanır. Xüsusilə, Can-Ci son suala "bəli" cavab verdiyi üçün hər hansı bir şəhərdən digərinə uçmaq mümkündür. Əgər "xeyr" cavab versəydi, uçmaq mümkün olmazdı.
Can-Ci-yə oyunu qazanmağa kömək edəcək bir proqram yazın. Qeyd edin ki, Mey-Yu və Can-Ci bir-birinin strategiyasını bilmirlər. Mey-Yu şəhər cütlükləri haqqında istənilən ardıcıllıqla soruşa bilər və Can-Ci hər suala dərhal cavab verməlidir, digər sualları gözləmədən. Aşağıdakı iki funksiyanı həyata keçirməlisiniz:
initialize(n) - başlanğıcda çağırılacaq funksiya. n parametri şəhərlərin sayını təyin edir;
hasEdge(u, v) - sonra bu funksiya r = n * (n - 1) / 2 dəfə çağırılacaq. Bu funksiyanın hər çağırışı Mey-Yu-nun növbəti sualıdır. Siz cavabı seçməlisiniz: u və v şəhərləri arasında birbaşa aviareys varmı. Xüsusilə, qaytarılan dəyər 1 olmalıdır, əgər birbaşa aviareys varsa, və 0 əks halda.
Hər alt tapşırıq bir neçə oyundan ibarətdir. Siz yalnız bütün oyunları qazandığınız halda alt tapşırıq üçün xal alacaqsınız.
Yuxarıda təsvir olunan funksiyaları aşağıdakı imzalarla həyata keçirməlisiniz:
C/C++ proqramları
void initialize(int n);
int hasEdge(int u, int v);
Pascal proqramları
procedure initialize(n: longint);
function hasEdge(u, v: longint): longint;
Grader aşağıdakı formatda giriş oxuyur:
birinci sətir n sayını ehtiva edir;
növbəti r sətirin hər biri u və v şəhərləri haqqında sorğunu təsvir edən iki tam ədəd ehtiva edir.
Hər sual üçün ayrıca sətirdə 1 çap olunacaq, əgər u və v arasında kənar varsa, və 0 əks halda.
Nümunə 1