Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

LEVONO4 - Լևոնը և օղաբլիթները 4

Լևոնը շատ է սիրում օղաբլիթներ և գնացել է խանութ դրանց ետևից։ Օղաբլիթներ վաճառողը՝ պարոն Օղակը, խաղամոլ է, և Լևոնին առաջարկում է խաղ, որում հաղթելու դեպքում նա կվաստակի իր օղաբլիթը։ Խաղը հետևյալն է՝ տրված է ծառ , որի աﬔն կողի վրա գրված է ﬔկ թիվ, որը ցույց է տալիս, թե քանի խնձոր կա այդ կողի վրա։ Ծառի վրա կա մարդուկ, ով սկզբում գտնվում է 1 համարով գագաթի վրա։ Խաղի ընթացքում Լևոնը և պարոն Օղակը մարդուկին տեղափոխում են մարդուկի ընթացիկ գագաթին հարևան գագաթ, որտեղ մարդուկը դեռ չի եղել։ Կողով անցնելիս մարդուկը ուտում է այդ կողի վրա գտնվող բոլոր խնձորները։ Խաղը սկսում է պարոն Օղակը։ Լևոնը և պարոն Օղակը կատարում են իրենց քայլերը ﬕմյանց հաջորդելով։ Խաղն ավարտվում է, երբ խաղացողը այլևս չի կարող քայլ կատարել։ Ամբողջ ընթացքում մարդուկի կերած խնձորների քանակը նշանակենք x -ով։ Լևոնը հաղթում է, եթե x -ի ﬓացորդը k -ի վրա փոքր է a -ից։ Հակառակ դեպքում հաղթում է պարոն Օղակը։ Բայց քանի որ պարոն Օղակը գիտի, որ Լևոնը շատ խելացի է, նա դժվարացրել է խնդրի պայմանները։ Նա որոշել է, որ նրանք պետք է ﬕանգաﬕց անեն q-ական քայլ (հնարավոր է, որ վերջին խաղացողը կատարի q-ից քիչ քայլ)։ Ձեր խնդիրն է տրված ծառի, k -ի, a -ի և q -ի համար պարզել, թե ով կհաղթի, եթե երկուսն էլ օպտիմալ խաղան։

Մուտքային տվյալներ

Մուտքի առաջին տողում տրված են n , k , a և q թվերը (1 ≤ a < k, 1 ≤ q < n) ։ Հաջորդող n-1 տողերում տրված է գրաֆի նկարագրությունը։ Աﬔն տողում տրված են v1 , v2 և c թվերը, ինչը նշանակում է, որ կա կող v1 և v2 գագաթների ﬕջև, որի վրա կա c հատ խնձոր (1 ≤ v1 , v2 ≤ n , v1 ≠ v2 , 0 ≤ c ≤ 109 ) ։

Ելքային տվյալներ

Ելքի ﬕակ տողում պետք է տպել 1 բառ՝ Levon , եթե կհաղթի Լևոնը և MrCircle , Եթե կհաղթի Պարոն Օղակը։

Ենթախնդիր 4.  2 ≤ n ≤ 105 , 2 ≤ k ≤ 109, q = 1

Օրինակ

Մուտք.
7 2 1 2
1 2 3
2 3 2
1 4 1
4 5 0
4 6 7
6 7 2

Ելք.
MrCircle

Ավելացրեց.Andreasyan
Ամսաթիվ.2018-04-15
Ժամանակի սահմանափակումը.0.200s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Հանրապետական 2018, եզրափակիչ փուլ

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.