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

Հինգ համեմունք, մեկ որոշում

Խոհարարը ուսումնասիրում է իրեն հայտնի բաղադրատոմսերի գիրքը։ Յուրաքանչյուր բաղադրատոմսում նշված է հինգ համեմունքի ուժգնությունը և թե որ ուտեստների ընտանիքին է այն պատկանում։ Երբ հայտնվում է նոր բաղադրատոմս, խոհարարը գտնում է դրան ամենանման k հայտնի բաղադրատոմսերը և թույլ տալիս, որ դրանք «քվեարկեն» ուտեստի ընտանիքի համար։

Կանխատեսեք յուրաքանչյուր նոր բաղադրատոմսի ընտանիքը՝ օգտագործելով k-մոտակա հարևանների (k nearest neighbors) ալգորիթմը հինգ չափանի համեմունքների տարածությունում։ Որպես հեռավորություն օգտագործեք L1 (Մանհեթենյան) հեռավորությունը, այսինքն՝ հինգ համեմունքների արժեքների բացարձակ տարբերությունների գումարը։ Եթե հեռավորությունները կամ քվեները հավասարվեն, նախապատվությունը տվեք այն բաղադրատոմսերին, որոնք մուտքային տվյալներում ավելի շուտ են հանդիպում।

Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ հայտնի բաղադրատոմսերի քանակը։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է հինգ իրական թիվ՝ s1, s2, s3, s4, s5, որոնց հաջորդում է ուտեստի ընտանիքը նշող բառը։ Այս տվյալները նկարագրում են մեկ հայտնի բաղադրատոմսի համեմունքների մակարդակներն ու ընտանիքը։

Այնուհետև տրված է k ամբողջ թիվը։ Հաջորդ տողում տրված է q ամբողջ թիվը՝ դասակարգման ենթակա նոր բաղադրատոմսերի քանակը։ Վերջին q տողերից յուրաքանչյուրը պարունակում է հինգ իրական թիվ՝ t1, t2, t3, t4, t5, որոնք նոր բաղադրատոմսի համեմունքների մակարդակներն են։

Յուրաքանչյուր նոր բաղադրատոմսի համար առանձին տողով տպեք կանխատեսված ուտեստի ընտանիքը։

Մուտք

Ելք

4
0 0 0 0 0 soup
1 0 0 0 0 curry
0 1 0 0 0 curry
2 2 2 2 2 stew
3
2
0.2 0.1 0 0 0
2 1.8 2 2 2

curry
curry

3
0 0 0 0 0 curry
0 0 1 0 0 noodles
0 0 0 1 0 noodles
1
3
0 0 0.4 0 0
0 0 0.9 0 0
0 0 0 1 0

curry
noodles
noodles

3
0 0 0 0 0 curry
1 0 0 0 0 stew
-1 0 0 0 0 noodles
2
1
0 0 0 0 0

curry

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