Երկու որոշում, մեկ ծանրոց

Առաքման ծառայությունը պետք է յուրաքանչյուր ծանրոցի համար ընտրություն կատարի արագ (express) և սովորական (economy) առաքման միջև՝ հիմնվելով երկու տվյալի վրա՝ weight (կիլոգրամներով) և distance (կիլոմետրերով)։ Ելակետային տվյալներում հեռավորության արժեքները, որոնք կիլոմետրերով են, գերակշռում են զանգվածի արժեքներին։ Սանդղավորումից (scaling) հետո կիլոմետրերի և կիլոգրամների ազդեցությունը հավասարակշռվում է։ Միևնույն ծանրոցը կարող է երկու տարբեր որոշում ստանալ, և առաքման ծառայությունը ցանկանում է տեսնել երկուսն էլ։

Ձեզանից պահանջվում է կարդալ պիտակավորված ծանրոցների սկզբնական ցուցակը, այնուհետև յուրաքանչյուր նոր ծանրոցի համար տպել երկու պիտակ։ Առաջինը՝ 3-NN ալգորիթմի կանխատեսումը՝ հիմնված ելակետային տվյալների վրա։ Երկրորդը՝ 3-NN ալգորիթմի կանխատեսումը՝ հիմնված min-max սանդղավորումից հետո ստացված տվյալների վրա։ Սանդղավորումը պետք է կատարվի՝ օգտագործելով միայն սկզբնական ցուցակի տվյալները։ Հարևաններին գտնելու համար օգտագործեք Էվկլիդյան հեռավորությունը։ Եթե սկզբնական ցուցակում որևէ հատկանիշի (feature) բոլոր արժեքները նույնն են, ապա դրա սանդղավորված արժեքը բոլոր տողերի համար 0 է։ Եթե ամենամոտ հարևանների պիտակների քանակները հավասար են (tie), տպեք այբբենական կարգով ամենափոքր պիտակը.

Մուտքի առաջին տողում տրված է n ամբողջ թիվը, որը ցույց է տալիս ծանրոցների քանակը սկզբնական ցուցակում։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ և մեկ պիտակ՝ առանց բացատների՝ weight distance label (զանգված, հեռավորություն, պիտակ)։

Այնուհետև հաջորդ տողում տրված է q ամբողջ թիվը՝ նոր ծանրոցների քանակը։ Հաջորդ q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ weight distance (զանգված, հեռավորություն)։

Ծրագիրը պետք է տպի q տող։ Յուրաքանչյուր տող պետք է պարունակի երկու պիտակ՝ բաժանված բացատով․ սկզբում՝ 3-NN ալգորիթմի որոշումը ելակետային տվյալների համար, այնուհետև՝ սանդղավորված տվյալների համար։