Game Language: az-az oyun (Game)

---

1 / 3

International Olympiad in Informatics 2014

13-20th July 2014

Taipei, Taiwan

Day-1 tasks

game

Language: az-AZ

Oyun (Game)

Gənc oğlan Jian-Jia tapmacanı xoşlayır. Ondan nə isə soruşduqda, o, birbaşa cavab verməkdənsə oyun

oynamağa üstünlük verir. Jian-Jia dostu Mei-Yu ilə görüşür və onunla Tayvanın uçuş xətlərinin

şəbəkəsi haqqında söhbət edir. Tayvanda   sayda şəhər var (numbered 0, ...,

kimi nömrələnib)

və onların bəziləri bir-birilə uçuş xətləri ilə birləşib. Hər bir uçuş (reys) iki şəhəri birləşdirir və hər iki

istiqamətdə ola bilər.

Mei-Yu istənilən iki şəhər arasında təyyarə reysinin olub-olmaması (birbaşa, yaxud dolayı) haqda Jian-

Jiadan soruşur. Jian-Jia suala açıq cavab vermək istəmir və əvəzində oyun oynamağı təklif edir. Mei-

Yu ona belə bir sual verə bilər: “  və   şəhərləri arasında birbaşa təyyarə reysi varmı?” və Jian-Jia

belə suallara dərhal cavab verəcək. Mei-Yu cəmi

sual verməklə hər bir şəhər

cütlüyü haqqında soruşa bilər. Əgər Mei-Yu verə biləcəyi   sualın ilk   saydasına

cavab aldıqdan

sonra istənilən iki şəhər arasında təyyarə ilə (birbaşa, yaxud dolayı) səyahət edə bilməsinin

mümkünlüyü haqqında nəticə çıxara bilirsə, o qalib gəlir. Əks halda, yəni o,   sualın hamısını verirsə,

qalib Jian-Jia olur.

Qaydalarına görə, oyunun Jian-Jia üçün maraqlı olması üçün dostlar razılaşırlar ki, Jian-Jia Tayvanın

mövcud uçuş xətləri şəbəkəsini unuda bilər və o, suallara istədiyi kimi cavab verə bilər. Siz Jian-Jiaya

suallara necə cavab verməli olduğunu bildirməklə oyunu udmaqda ona yardım etməlisiniz.

Örnəklər (Examples)

Biz oyun qaydalarını üç nümunə üzərində araşdıracağıq. Hər bir nümunədə

şəhər və

sual-cavab raundu var.

Birinci nümunədə (aşağıdakı cədvəl), Jian-Jia uduzur, çünki Mei-Yu 4-cü raunddan sonra, Jian-Jianın

5 və ya 6-cı suallara necə cavab verəcəyindən asılı olmayaraq, istənilən iki şəhər arasında təyyarə ilə

səyahət edə biləcəyinə əmin olur.

raund

sual

cavab

1

0, 1

yes

2

3, 0

yes

3

1, 2

no

4

0, 2

yes

-----

-------- ------

5

3, 1

no

6

2, 3

no

INövbəti nümunədə Mei-Yu 3-cü raunddan sonra, Jian-Jianın 4, 5 və ya 6-cı suala necə cavab

verəcəyindən asılı olmayaraq, sübut edə bilər ki, kimsə 0 və 1 şəhərləri arasında təyyarə ilə uça bilməz,

deməli, Jian-Jia yenə də uduzur.

---

2 / 3

round question answer

1

0, 3

no

2

2, 0

no

3

0, 1

no

-----

--------

------

4

1, 2

yes

5

1, 3

yes

6

2, 3

yes

Sonuncu nümunədə Mei-Yu altı sualın hamısına cavab aldıqdan sonra istənilən iki şəhər arasında

təyyarə ilə səyahət etməyin mümkün olub-olmamasını müəyyən edə bilmir, deməli, oyunu Jian-Jia

udur. Çünki, əgər Jian-Jia sonuncu suala yes cavabını verərsə (aşağıdakı cədvəldə), onda istənilən iki

şəhər arasında uçuş mümkündür. Fəqət, əgər Jian-Jia sonuncu suala no cavabını verərsə, uçuş

mümkün olmayacaq.

round question answer

1

0, 3

no

2

1, 0

yes

3

0, 2

no

4

3, 1

yes

5

1, 2

no

6

2, 3

yes

Task

Please write a program that helps Jian-Jia win the game. Note that neither Mei-Yu nor Jian-Jia knows

the strategy of each other. Mei-Yu can ask about pairs of cities in any order, and Jian-Jia must answer

them immediately without knowing the future questions. You need to implement the following two

functions.

initialize(n) -- We will call your initialize first. The parameter   is the number of

cities.

hasEdge(u, v) -- Then we will call hasEdge for

times. These calls

represent Mei-Yu's questions, in the order that she asks them. You must answer whether there

is a direct flight between cities   and  . Specifically, the return value should be 1 if there is a

direct flight, or 0 otherwise.

Subtasks

subtask points

1

15

---

3 / 3

2

27

3

58

subtask points

Implementation details

You have to submit exactly one file, called game.c, game.cpp or game.pas. This file implements

the subprograms described above using the following signatures.

C/C++ programs

void initialize(int n);

int hasEdge(int u, int v);

Pascal programs

procedure initialize(n: longint);

function hasEdge(u, v: longint): longint;

Sample grader

The sample grader reads the input in the following format:

line 1: n

the following   lines: each line contains two integers u and v that describe a question regarding

cities   and  .