Հետքերով հրապարակում եմ խնդիրներ Ալգորիթմի խաղարկությունից (պատրաստ է դասական սպորտային ծրագրավորմամբ: Երկու ժամում անհրաժեշտ է լուծել երեք խնդիր Java, C#, C++ կամ Python լեզուներով։)
1. Տորթ վեց մարդու համար
Պատասխանատվության ներկայացում
Ժամանակի սահմանաչափը՝ 4 վայրկյան։
Դուք ունեք տորթ։ Վերևից դիտելով, տորթը (խիստ) բարձիթողի բազմանկյուն է։ Ես քեզ տալիս եմ անկյունների փոխադրումները ամբողջական թվերով X և Y։
Դուք ունեք հինգ ընկեր։ Դուք ցանկանում եք բաժանել տորթը վեց հավասար մասերի (բայց ոչ unbedingt նույնանման ձևերով)։ Իհարկե, յուրաքանչյուրը կարող է դա անել հինգ կտրումներով, բայց միայն պրոֆեսիոնալը կարող է անել դա երեք կտրումներով։
Փնտրեք երեք կտրում ուղիղ գծերով, որոնք անցնում են նույն կետից և բաժանում են տորթը վեց հավասար մակերեսով մասերի։ Ախոռեք {x, y, d1, d2, d3}, որտեղ (x, y) — երեք կտրումների ընդհանուր կետն է, իսկ d1, d2, d3 — կտրումների ուղղությունները ռադիաններով։
تعریفԿլասս: CakeForSix
Մեթոդ: cut
Պարամետրեր: int[], int[]
Վերադարձնում է: double[]
Մեթոդի ստորագրություն: double[] cut(int[] x, int[] y)
(հաստատեք, որ ձեր մեթոդը հրապարակային է)
Նշումներ
- Եղանակը x առանցքի դրական ուղղությունը 0 (ռադյան) է, y առանցքի դրական ուղղությունը pi/2 (ռադյան) է։
- d ուղղությամբ կտրումը նույնն է, ինչ pi*k+d ուղղությամբ կտրումը, որտեղ k ցանկացած ամբողջ թիվ է։
- Դուք կարող եք վերադարձնել ցանկացած ուղղություններ, դրանք հարկավոր չէ լինել [0, pi)-ից։
- Գրեյդերը հաշվելու է ձեր վեց կտորների մակերեսները doubles-ով։ Պատասխանը կընդունվի, եթե հարաբերական կամ բացարձակ տարբերությունը նրանց միջև փոքր լինի 10^(-4)։
- Փաստորեն, թող X և Y լինեն ձեր վեց մակերեսներից ամենափոքրն ու ամենամեծը, որոնք հաշվել է գրեյդերը։ Այդ դեպքում ձեր պատասխանը կընդունվի, եթե Y < max(X+10^(-4), X*1+10^(-4))։
- (Մարզման սկզբնական տարբերակում օգտագործվել է ճշտություն 1e-7 փոխարեն 1e-4։ Այս խնդիրը լուծելու նպատակով ճշտության սահմանը նվազեցվել է, քանի որ տեղի էին ունենում դեպքեր, որոնք հավանաբար դարձնում էին խնդիրը անհնարին 1e-7 ճշտությամբ։ Հիանալի աշխարհում սահմանափակումները թույլ չեն տալիս նման դեպքեր և դեռ талапում են բարձր ճշտություն, այսպես, խնդրի լուծումը որոշակի ընդհանուր թվային օպտիմիզացիայի միջոցով հեշտ չէ։)
Սահմաններ
- x-ը պարունակում է 3-ից 50 հավելվածներ միաժամանակ;
- y-ը պարունակում է նույն քանակի հավելվածներ, ինչ x-ը։
- բոլոր անկյունագծերը պետք է լինեն 0-ից 10,000 ներառյալ
- x և y-ը սահմանափակում են բարձիթողի բազմանկյուն, հակառակ ժամացույցի մղման ուղղությամբ։
Այժմաբառը անգլերենում
Նախադասություն
Ժամանակի սահմանաչափը 4 վայրկյան է։
Դուք ունեք տորթ։ Վերևից դիտելով, տորթը բարձիթող (խիստ) բազմանկյուն է։ Ձեզ ներկայացվում են անկյունների փոխադրումները int[]-ում x և y:
Դուք ունեք հինգ ընկեր։ Դուք հիմա ցանկանում եք կտրել տորթը վեց հավասար մասերի (բայց ոչ unbedingt հավասար ձևերով)։ Իհարկե, յուրաքանչյուրը կարող է դա անել հինգ կտրումներով՝ բայց միայն իսկական պրոֆեսիոնալը կարող է անել դա երեքով։
Փնտրեք երեք ուղիղ կտրումներ, որոնք անցնում են նույն կետից, որոնք կտրում են տորթը վեց հավասար մեծությամբ մասերի։ Վերադարձնել {x, y, d1, d2, d3}, որտեղ (x, y) երեք կտրումների ընդհանուր կետն է, իսկ d1, d2, d3՝ նրանց ուղղությունները ռադիաններով։
تعریف
Կլասս: CakeForSix
Մեթոդ: cut
Պարամետրեր: int[], int[]
Վերադարձնում է: double[]
Մեթոդի ստորագրություն: double[] cut(int[] x, int[] y)
(հաստատեք, որ ձեր մեթոդը հրապարակային է)
Նշումներ
— x առանցքի դրական ուղղությունը 0 (ռադյան) է, y առանցքի դրական ուղղությունը pi/2 (ռադյան) է։
— d ուղղությամբ կտրումը նույնն է, ինչ pi*k+d ուղղությամբ կտրումը, որտեղ k ցանկացած ամբողջ թիվ է։
— Դուք կարող եք վերադարձնել οποևղ ուղղություններ, դրանք հարկավոր չէ լինել [0,pi)-ից։
— Գրադարանը կընկալի ձեր վեց թխվածք այցելուի տարածքները երկակի։ Պատասխանը կստացվի, եթե նրանց միջև հարաբերական կամ абсолют տարբերությունը պակաս լինի քան 10^(-4):
— Փորագրելով, թող X և Y լինեն ձեր վեց տարածքների ամենափոքրն ու ամենամեծը, ինչպես հաշվարկված է գրադարանում։ Այնուհետև ձեր պատասխանը կընկալի, եթե Y < max( X + 10^(-4), X * (1+10^(-4)) ):
— (Պրոբլեմի սկզբնական տարբերակը օգտագործում էր 1e-7 ճշգրտություն 1e-4-ի փոխարեն։ Այս պրոբլեմի լուծումը արխիվում ճշգրտության սահմանը նվազեցվել է, քանի որ գոյություն ունեն մարտահրավերի դեպքեր, որոնք հավանաբար չեն թույլատրում խնդիրը լուծել 1e-7 ճշգրտությամբ։ Իդեալական աշխարհի պայմանները չի թույլատրում նման դեպքեր և դեռևս պահանջում են բարձր ճշգրտություն, այնպես որ, խնդիրը հեշտ չի լուծվում ընդհանուր թվային օպտիմիզացիայի միջոցով.)
Պայմաններ
— x-ը կունենա 3-ից 50 էլեմենտի միջև, ներառյալ։
— y-ը կունենա x-ի հետ նույն թվաքանակը։
— Բոլոր համակարգերը կլինեն 0-ից 10,000-ի միջև, ներառյալ։
— x և y-ն կնկատեն մի կլոր պոլիգոն հակակառավարական կարգով։
Օրինակներ
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Ո վերադարձները:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Սիմետրիկ, բայց ոչ ճիշտ վեցանկյուն։ Պատասխանի օրինակ բերում է, որ այն հորիզոնական կերպով բաժանում է կեսերի և արվում է երկու այլ բաժանում կենտրոնում, որոնք բաժանում են յուրաքանչյուր մասը երեք մասի։
1)
{0, 1000, 0}
{0, 0, 1000}
Ո վերադարձները:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Ծայրահեղ եռանկյուն, և կրկին, մենք կարող ենք սկսել որևէ մեկը երեք բաժանումներից հիշողության առանցքով։
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Ո վերադարձները:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Բազմախառն հինգանկյուն։
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Ո վերադարձները: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Քառակուսի, ուղիղ 45 աստիճան։
[]
Պատասխանելու համար պետք է գրանցված օգտվող լինել։ , խնդրում եմ։
Ես լուծեցի խնդիրը
միայն 10 րոպեում
10-30 րոպե
30-60 րոպե
1-2 ժամ
մոտ 2 ժամից ավել
հանրապետություն։
42 օգտագործող քվեարկել են: 47 օգտվողներ ձեռնպահ են մնում։
Ընտանիք: habr.com
