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

Տների համեմատություն. հինգ «արդար» հարևան

Տների ցանկում ընդհանուր գինն ու մակերեսը կարող են մոլորեցնել KNN ալգորիթմը։ Գնորդներն իրականում համեմատում են 1մ²-ու արժեքը։ Որպեսզի համեմատությունն «արդար» լինի, ձեր առաջարկող համակարգը պետք է գտնի այն հինգ տները, որոնց 1մ²-ու արժեքն ամենամոտն է նոր տան համապատասխան արժեքին։

Ձեզանից պահանջվում է կարդալ տների սկզբնական ցանկը, այնուհետև յուրաքանչյուր նոր տան համար արտածել սկզբնական ցանկից հինգ ամենամոտ տների ինդեքսները՝ դասավորված ամենամոտից մինչև ամենահեռու հերթականությամբ։ Տների մոտիկությունը որոշվում է նրանց 1մ²-ու արժեքների նմանությամբ։ Եթե երկու տներ հավասարապես մոտ են, ապա առաջինը պետք է նշել ավելի փոքր ինդեքս ունեցողը։ Տները համարակալվում են 1-ից՝ ըստ իրենց հերթականության։

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

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

Ծրագիրը պետք է տպի q տող։ Յուրաքանչյուր տող պետք է պարունակի հինգ ամբողջ թիվ՝ սկզբնական ցանկից հինգ ամենամոտ տների ինդեքսները։

Մուտք

Ելք

6
100000 40
120000 50
150000 60
200000 80
130000 52
156000 60
2
125000 50
180000 60

1 3 4 5 2
6 1 3 4 5

7
90000 30
180000 90
150000 50
210000 70
175000 70
240000 80
195000 65
3
150000 60
240000 100
210000 70

5 1 2 3 4
5 2 1 3 4
1 3 4 6 7

8
135000 45
128000 64
99000 66
160000 80
180000 100
144000 48
210000 70
150000 75
1
144000 60

2 4 8 1 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