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

Վառելիքի արդարություն․ նախ՝ սանդղավորում, ապա՝ հարևան

Ճանապարհորդության պլանավորման ծրագիրը վառելիքի ծախսը գնահատում է երկու հատկանիշի հիման վրա՝ արագություն (կմ/ժ-ով) և ուղևորության տևողություն (րոպեներով)։ Ժամանակի արժեքները շատ ավելի մեծ են, քան արագության արժեքները, ուստի KNN ալգորիթմը արդարացի գնահատական չի տա, եթե երկու հատկանիշներն էլ չսանդղավորվեն նույն միջակայքում։ Ծրագիրը որոշում է նախ կիրառել min-max սանդղավորում, այնուհետև օգտագործել KNN ռեգրեսիա՝ վառելիքի ծախսը կանխատեսելու համար։

Ձեզանից պահանջվում է կարդալ նախապես տրված տվյալները, հաշվել յուրաքանչյուր սյունակի նվազագույն և առավելագույն արժեքները՝ օգտագործելով միայն այդ տվյալները, և դրանց միջոցով սանդղավորել ինչպես արդեն իսկ գոյություն ունեցող, այնպես էլ յուրաքանչյուր նոր տողը՝ օգտագործելով min-max սանդղավորումը։ Եթե նախապես տրված տվյալների որևէ սյունակում բոլոր արժեքները նույնն են, ապա դրա սանդղավորված արժեքը յուրաքանչյուր տողի համար 0 է։ Սանդղավորումից հետո դասակարգումը կատարեք KNN ռեգրեսիայի միջոցով՝ օգտագործելով Էվկլիդյան հեռավորությունը։ Յուրաքանչյուր նոր տողի համար գտեք նախապես տրված տվյալների մեջ k ամենամոտ տողերը և տպեք դրանց վառելիքի թիրախային արժեքների միջինը։

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

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

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

Մուտք

Ելք

4 2
100 60 8
20 30 3
90 50 7
10 10 1
2
80 55
15 20

7.5
2

6 3
60 30 4
80 45 6
100 60 8
40 20 3
20 15 2
90 55 7
3
85 50
25 15
50 30

7
3
4.3333333333

3 2
50 60 5
80 60 8
20 60 2
2
65 30
25 45

6.5
3.5

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