Մեքենայական ուսուցում

K-sweep․ Քանի՞ հարևանի հարցնեմ

Մի նորեկ է ժամանում մարդաշատ քաղաք։ Նա գիտի որոշ բարյացակամ տեղացիների դիրքերը և թե նրանցից յուրաքանչյուրը ինչ ուղղություն կառաջարկի՝ ձախ թե աջ։ Փողոցի տարբեր խաչմերուկներում կանգնելով՝ նորեկը հարցնում է ավելի ու ավելի շատ մոտակա տեղացիների և գրի առնում, թե ինչպես է փոխվում խորհուրդը։ Հեռավորությունները հաշվվում են ուղիղ գծով՝ սկզբնամակ խաչմերուկից։

Յուրաքանչյուր խաչմերուկի համար դուք պետք է կանխատեսեք ուղղությունը՝ հարցնելով նախ 1 ամենամոտ տեղացուն, հետո՝ 2 ամենամոտ տեղացիներին, հետո՝ 3-ին, և այդպես շարունակ մինչև բոլոր n տեղացիներին։ Եթե երկու տեղացիներ գտնվում են ճիշտ նույն հեռավորության վրա, ապա պետք է նախապատվությունը տալ նրան, որը մուտքային տվյալներում ավելի շուտ է հանդիպել։

Մուտքի առաջին տողում տրված է միակ ամբողջ թիվը n որը ներկայացնում է հայտնի տեղացիների քանակը։

Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y որին հաջորդում է ուղղությունը (left կամ right)՝ նկարագրելով մեկ տեղացու դիրքն ու խորհուրդը։

Հաջորդ տողում տրված է միակ ամբողջ թիվը q որը ներկայացնում է ստուգվելիք խաչմերուկների քանակը։
Վերջին q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y՝ խաչմերուկի դիրքը։

Յուրաքանչյուր խաչմերուկի համար մեկ տողում տպեք բացատներով անջատված n կանխատեսում՝ k = 1, 2, …, n արժեքների համար՝ օգտագործելով տվյալ խաչմերուկի համար հարևանների ֆիքսված դասավորությունը։

Մուտք

Ելք

4
0 0 left
2 0 right
0 2 right
-1 -1 left
3
0.9 0.1
1.1 0
1 1

left left right left
right left right left
left left right left

3
-1 0 left
3 0 right
0 4 right
2
2 1
2 5

right left right
right right right

3
0 1 left
0 -1 right
5 0 right
2
0 0
3 0

left left right
right left right

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue