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

Ուղեցույց․ 1-NN՝ հավասարակշռված մասշտաբավորումից հետո

Ձեր արշավային հավելվածը երթուղիներ է առաջարկում՝ օգտագործելով KNN ալգորիթմը։ Յուրաքանչյուր երթուղի նկարագրվում է երկու հատկանիշով՝ թեքությունը աստիճաններով և բարձրությունը մետրերով։ Բարձրության արժեքները շատ ավելի մեծ են, ուստի առանց մասշտաբավորման դրանք գերիշխում են հեռավորության հաշվարկում, և KNN-ը կայացնում է ոչ օբյեկտիվ որոշումներ։ Այս խնդիրը լուծելու համար դուք որոշում եք նախ մասշտաբավորել երկու հատկանիշները, ապա կատարել դասակարգում։

Ձեզանից պահանջվում է կարդալ նախնական տվյալները պիտակներով, այնուհետև դասակարգել նոր տողերը։ Հաշվեք յուրաքանչյուր սյունակի համար նվազագույն և առավելագույն արժեքները՝ օգտագործելով միայն նախնական տվյալները, այնուհետև մասշտաբավորեք և՛ նախնական, և՛ նոր տողերը [0,1] միջակայքին, որից հետո կանխատեսեք յուրաքանչյուր նոր տողի պիտակը՝ օգտագործելով 1-NN ալգորիթմը մասշտաբավորված տարածության մեջ։ Եթե նախնական տվյալների որևէ սյունակում բոլոր արժեքները նույնն են, ապա դրա մասշտաբավորված արժեքը բոլոր տեղերում համարեք 0։ Եթե մի քանի նախնական տողեր ունեն նույն նվազագույն հեռավորությունը, ընտրեք այն տողի պիտակը, որն ավելի շուտ է հանդիպում նախնական տվյալների մեջ։

Մուտքի առաջին տողը պարունակում է երկու ամբողջ թիվ՝ n-ը և d-ն, որոնք համապատասխանաբար ներկայացնում են պիտակավորված տողերի և հատկանիշների քանակը։ Այս խնդրում d = 2 է՝ թեքություն և բարձրություն։ Յուրաքանչյուր հաջորդ n տող պարունակում է d իրական թիվ, որին հաջորդում է պիտակը՝ առանց բացատների։

Հաջորդ տողը պարունակում է մեկ ամբողջ թիվ՝ q-ն, որը ներկայացնում է դասակարգման ենթակա նոր տողերի քանակը։ Յուրաքանչյուր հաջորդ q տող պարունակում է d իրական թիվ՝ թեքությունը և բարձրությունը, որոնք պետք է դասակարգվեն՝ օգտագործելով նախնական տվյալների հիման վրա հաշվարկված մասշտաբավորումը։

Ծրագիրը պետք է ելքում տպի q տող, որոնցից յուրաքանչյուրը պարունակի համապատասխան նոր տողի համար կանխատեսված պիտակը։

Մուտք

Ելք

3 2
0 1000 A
10 1100 B
0 900 A
2
1 1010
9 1090

A
B

3 2
0 1000 A
5 1000 B
10 1000 B
3
4 900
7 1500
0 1000

B
B
A

2 2
0 1000 A
2 1000 B
1
1 800

A

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