Օլիմպիական ծրագրավորում

[Cesare]

Այստեղ կքննարկենք տարբեր ալգորիթմներ , լեզուների հմտությունները և այլն :

Ավելացվել է 4 րոպե անց
Կարծում եմ այստեդ կարևոր չի թե ինչ լեզվով ես ծրագրավորում :
Ընդհանրապես այստեղ կարևորը խնդրի ալգորիթմն է :
Օրինակ ես լիքը սայտերում գրանցված եմ, որտեղ տարբեր խնդիրներ են :
Կարծում եմ Ձեզնից ոմանք գաղափար ունեն սրա մասին :
Եվ Եթե մեկ մեկ օգնեք ինձ շատ լավ կլինի :

Ի դեպ ցանկացողներին կարող եմ տրամադրել այդ սայտերից :

[Սամվել]

Մդդա…լավա հա ես ել միտք ունեի սենց մի բան ասեի…խնդիրները գրի կաշխատեմ մի բանով օգնեմ…իմ վախտը Օլիմպիադաների անցելա…քոնը նորա սկսվում կաշխատեմ մի բանով օգնեմ

[Cesare]

Cow_Tours
Farmer_John_has_a_number_of_pastures_on_his_farm._Cow_paths_connect_some_pastures_with_certain_other_pastures,_forming_a_field._But,at_the_p resent_time,_you_can_find_at_least_two_pastures_that_cannot_be_connected_by_any_sequence_of_cow_paths,_thus_partitioning_Farmer_John's_farm_ into_multiple_fields._
Farmer_John_would_like_add_a_single_a_cow_path_between_one_pair_of_pastures_using_the_constraints_below._
A_field's_`diameter'_is_defined_to_be_the_largest_distance_of_all_the_shortest_walks_between_any_pair_of_pastures_in_the_field._Consider_the _field_below_with_five_pastures,_located_at_the_points_shown,_and_cow_paths_marked_by_lines:_
________________15,15___20,15
__________________D_______E
__________________*-------*
__________________|______/|
__________________|____/__|
__________________|__/____|
__________________|/______|
_________*--------*-------*
_________A________B_______C
_________10,10___15,10___20,10
The_`diameter'_of_this_field_is_approximately_12.07106,_since_the_longest_of_the_set_of_shortest_paths_between_pairs_of_pastures_is_the_path _from_A_to_E_(which_includes_the_point_set_{A,B,E})._No_other_pair_of_pastures_in_this_field_is_farther_apart_when_connected_by_an_optimal_s equence_of_cow_paths._
Suppose_another_field_on_the_same_plane_is_connected_by_cow_paths_as_follows:_
_________________________*F_30,15
_________________________/_
________________________/__
______________________/____
____________________/______
___________________*------_
___________________G______H
___________________25,10___30,10
In_the_scenario_of_just_two_fields_on_his_farm,_Farmer_John_would_add_a_cow_path_between_a_point_in_each_of_these_two_fields_(namely_point_s ets_{A,B,C,D,E}_and_{F,G,H})_so_that_the_joined_set_of_pastures_{A,B,C,D,E,F,G,H}_has_the_smallest_possible_diameter._
Note_that_cow_paths_do_not_connect_just_because_they_cross_each_other;_they_only_connect_at_listed_points._
The_input_contains_the_pastures,_their_locations,_and_a_symmetric_"adjacency"_matrix_that_tells_whether_pastures_are_connected_by_cow_paths. _Pastures_are_not_considered_to_be_connected_to_themselves._Here's_one_annotated_adjacency_list_for_the_pasture_{A,B,C,D,E,F,G,H}_as_shown_a bove:_
________________A_B_C_D_E_F_G_H
______________A_0_1_0_0_0_0_0_0
______________B_1_0_1_1_1_0_0_0
______________C_0_1_0_0_1_0_0_0
______________D_0_1_0_0_1_0_0_0
______________E_0_1_1_1_0_0_0_0
______________F_0_0_0_0_0_0_1_0
______________G_0_0_0_0_0_1_0_1
______________H_0_0_0_0_0_0_1_0
Other_equivalent_adjacency_lists_might_permute_the_rows_and_columns_by_using_some_order_other_than_alphabetical_to_show_the_point_connection s._The_input_data_contains_no_names_for_the_points._
The_input_will_contain_at_least_two_pastures_that_are_not_connected_by_any_sequence_of_cow_paths._
Find_a_way_to_connect_exactly_two_pastures_in_the_input_with_a_cow_path_so_that_the_new_combined_field_has_the_smallest_possible_diameter_of _any_possible_pair_of_connected_pastures._Output_that_smallest_possible_diameter._
PROGRAM_NAME:_cowtour
INPUT_FORMAT
Line_1:__An_integer,_N_1_<=_N_<=_150),_the_number_of_pastures__
Line_2-N+1:__Two_integers,_X_and_Y_(0_<=_X_,Y<=_100000),_that_denote_that_X,Y_grid_location_of_the_pastures;_all_input_pastures_are_unique.__
Line_N+2-2*N+1:__lines,_each_containing_N_digits_(0_or_1)_that_represent_the_adjacency_matrix_as_described_above,_where_the_rows'_and_columns'_indice s_are_in_order_of_the_points_just_listed.__
SAMPLE_INPUT_(file_cowtour.in)_
8
10_10
15_10
20_10
15_15
20_15
30_15
25_10
30_10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
OUTPUT_FORMAT
The_output_consists_of_a_single_line_with_the_diameter_of_the_newly_joined_pastures._Print_the_answer_to_exactly_six_decimal_places._Do_not_ perform_any_special_rounding_on_your_output._
SAMPLE_OUTPUT_(file_cowtour.out)
22.071068

պռաբելների տեղը գիծ եմ դրել, որ նկարը իրար չխառնվի :
Ես խնդիրը ես լուծել եմ :
Իմ մոտ 8-րդ տեստի վրա սխալ պատասխան ա տալիս :
Եթե կարանաս ջոգես տեստն ել կասեմ :

Ավելացվել է 8 րոպե անց
չե մեկա կարգին չեղավ :
Փորձեմ սենց :
Չեղավ կցել ֆայլը մեծ եր :
Եթե անհասկալի եղավ ասա կգրեմ :

Ավելացվել է 9 րոպե անց
Մի բան ել : Ստեղ գրանցումը ազատ ա :
Կապ չունի տարիքը եթե ուզում ես սա և ելի մի քանի սայտ կարամ ասեմ գրանցվես :

[Սամվել]

պռաբելների տեղը գիծ եմ դրել, որ նկարը իրար չխառնվի :
Ես խնդիրը ես լուծել եմ :
Իմ մոտ 8-րդ տեստի վրա սխալ պատասխան ա տալիս :
Եթե կարանաս ջոգես տեստն ել կասեմ :

Ավելացվել է 8 րոպե անց
չե մեկա կարգին չեղավ :
Փորձեմ սենց :
Չեղավ կցել ֆայլը մեծ եր :
Եթե անհասկալի եղավ ասա կգրեմ :

Ավելացվել է 9 րոպե անց
Մի բան ել : Ստեղ գրանցումը ազատ ա :
Կապ չունի տարիքը եթե ուզում ես սա և ելի մի քանի սայտ կարամ ասեմ գրանցվես :

այսօր ժամանակ չունեմ կարդամ…իրիկունը կկարդամ

մենակ Թարգմանի էլի ներվայանում եմ ետ անգլերենից
վավ որ չթարգմանես էլ կլինի…սայտն էլ տուր պետք կգա

[PygmaliOn]

Սայտի հասցեն միանգամից ստեղ կգրես, ինձ էլ պետք կգա երևի:

[Cesare]

Քաղաքից բացակայում եի դրա համար պատասխան չկար :
Kiborg ջան ես սայտը որ տամ օգուտ չի լինի այսինքն կայնի տամ նայի խի :
www.usaco.org : Ինքնա Ռեգիստրացիա եղի չի խանգարի :
Ես սայտում կա 5 գլուխ ամեն գլխում 4-5 մաս ամեն մասում տեքստ
ու դրա վերոբերյալ 3 - 5 խնդիր : միչև մի մասի սաղ խնդիրները չլուծես
մյուսը չես կարա բացես : Իմ ասածը 2-րդ գլխի 4-րդ մասից ա : Դրա համար օգուտ չկա սայտը ասելու մեջ, բայց գրանցվելը հաստատ չի խանգարի :

[Cesare]

Գրեմ իմ հասկացած ձևով: Հնարավոր ա որ ինչ որ բան
լավ չեմ հասկացել և դրա պատճառով ա սխալ տալիս:
Լավ գրեմ կարճ ու հասկանալի: Տրված ա մի հատ գրաֆ:
Ետ գրաֆում հայտնի ա յուրաքանչյաուր 2 գագաթի
միյև եղաչ հեռավորությունը : Ետ գրաֆը բաժանված ա 2
Մասի, այնպես, որ ետ 2 խմբերից մեկում գտնվող գագաթից
Մյուս խմբում գտնվող գագաթ տանող ճանապարհ չկա
(հնարավոր չէ հասնել): Պիտի ետ 2 խմբերում գտնվող մի
Զույգ գագթ միացնես այնպես, որ ետ 2 խմբերում գտնվող
ցանկացած 2 գագաթների միջև եղած հեռավորությունների
max_ը լինի min: OK ???
Մուք գույնով գրված ա են պահը որ կարողա սխալ եմ հասկացել:
Դե քեզ տենամ,
եթե պետք ա իմ cpp կոդն ու ալգորիթմն ել կասեմ:

[Սամվել]

Գրեմ իմ հասկացած ձևով: Հնարավոր ա որ ինչ որ բան
լավ չեմ հասկացել և դրա պատճառով ա սխալ տալիս:
Լավ գրեմ կարճ ու հասկանալի: Տրված ա մի հատ գրաֆ:
Ետ գրաֆում հայտնի ա յուրաքանչյաուր 2 գագաթի
միյև եղաչ հեռավորությունը : Ետ գրաֆը բաժանված ա 2
Մասի, այնպես, որ ետ 2 խմբերից մեկում գտնվող գագաթից
Մյուս խմբում գտնվող գագաթ տանող ճանապարհ չկա
(հնարավոր չէ հասնել): Պիտի ետ 2 խմբերում գտնվող մի
Զույգ գագթ միացնես այնպես, որ ետ 2 խմբերում գտնվող
ցանկացած 2 գագաթների միջև եղած հեռավորությունների
max_ը լինի min: OK ???
Մուք գույնով գրված ա են պահը որ կարողա սխալ եմ հասկացել:
Դե քեզ տենամ,
եթե պետք ա իմ cpp կոդն ու ալգորիթմն ել կասեմ:

Հայկ ջան բան Ճիշտն ասած չհասկացա գրածիցտ ավելի լավա մի հատ էլ սրա անգլերենը դիր

[Cesare]

Այսինքն ոնց չհասկացար ??
Լավ չեմ գրել թե ուրիշ խնդիր կա ??

[Սամվել]

Այսինքն ոնց չհասկացար ??
Լավ չեմ գրել թե ուրիշ խնդիր կա ??

Հիմա տեղ եմ գնում կգամ կնայեմ մի հատ էլ եթե դժվար չի մի հատ էլ անգլերենը դիր կգամ կնայեմ

[Cesare]

Վերևը կա … Չջոգա խի ես ուզում …
Բայց որ ուզում ես դնեմ :

Cow_Tours
Farmer_John_has_a_number_of_pastures_on_his_farm._ Cow_paths_connect_some_pastures_with_certain_other _pastures,_forming_a_field._But,at_the_present_tim e,_you_can_find_at_least_two_pastures_that_cannot_ be_connected_by_any_sequence_of_cow_paths,_thus_pa rtitioning_Farmer_John's_farm_into_multiple_fields ._
Farmer_John_would_like_add_a_single_a_cow_path_bet ween_one_pair_of_pastures_using_the_constraints_be low._
A_field's_`diameter'_is_defined_to_be_the_largest_ distance_of_all_the_shortest_walks_between_any_pai r_of_pastures_in_the_field._Consider_the_field_bel ow_with_five_pastures,_located_at_the_points_shown ,_and_cow_paths_marked_by_lines:_
________________15,15___20,15
__________________D_______E
__________________*-------*
__________________|______/|
__________________|____/__|
__________________|__/____|
__________________|/______|
_________*--------*-------*
_________A________B_______C
_________10,10___15,10___20,10
The_`diameter'_of_this_field_is_approximately_12.0 7106,_since_the_longest_of_the_set_of_shortest_pat hs_between_pairs_of_pastures_is_the_path_from_A_to _E_(which_includes_the_point_set_{A,B,E})._No_othe r_pair_of_pastures_in_this_field_is_farther_apart_ when_connected_by_an_optimal_sequence_of_cow_paths ._
Suppose_another_field_on_the_same_plane_is_connect ed_by_cow_paths_as_follows:_
_________________________*F_30,15
_________________________/_
________________________/__
______________________/____
____________________/______
___________________*------_
___________________G______H
___________________25,10___30,10
In_the_scenario_of_just_two_fields_on_his_farm,_Fa rmer_John_would_add_a_cow_path_between_a_point_in_ each_of_these_two_fields_(namely_point_sets_{A,B,C ,D,E}_and_{F,G,H})_so_that_the_joined_set_of_pastu res_{A,B,C,D,E,F,G,H}_has_the_smallest_possible_di ameter._
Note_that_cow_paths_do_not_connect_just_because_th ey_cross_each_other;_they_only_connect_at_listed_p oints._
The_input_contains_the_pastures,_their_locations,_ and_a_symmetric_"adjacency"_matrix_that_tells_whet her_pastures_are_connected_by_cow_paths._Pastures_ are_not_considered_to_be_connected_to_themselves._ Here's_one_annotated_adjacency_list_for_the_pastur e_{A,B,C,D,E,F,G,H}_as_shown_above:_
________________A_B_C_D_E_F_G_H
______________A_0_1_0_0_0_0_0_0
______________B_1_0_1_1_1_0_0_0
______________C_0_1_0_0_1_0_0_0
______________D_0_1_0_0_1_0_0_0
______________E_0_1_1_1_0_0_0_0
______________F_0_0_0_0_0_0_1_0
______________G_0_0_0_0_0_1_0_1
______________H_0_0_0_0_0_0_1_0
Other_equivalent_adjacency_lists_might_permute_the _rows_and_columns_by_using_some_order_other_than_a lphabetical_to_show_the_point_connections._The_inp ut_data_contains_no_names_for_the_points._
The_input_will_contain_at_least_two_pastures_that_ are_not_connected_by_any_sequence_of_cow_paths._
Find_a_way_to_connect_exactly_two_pastures_in_the_ input_with_a_cow_path_so_that_the_new_combined_fie ld_has_the_smallest_possible_diameter_of_any_possi ble_pair_of_connected_pastures._Output_that_smalle st_possible_diameter._
PROGRAM_NAME:_cowtour
INPUT_FORMAT
Line_1:__An_integer,_N_1_<=_N_<=_150),_the_number_ of_pastures__
Line_2-N+1:__Two_integers,_X_and_Y_(0_<=_X_,Y<=_100000),_ that_denote_that_X,Y_grid_location_of_the_pastures ;_all_input_pastures_are_unique.__
Line_N+2-2*N+1:__lines,_each_containing_N_digits_(0_or_1)_t hat_represent_the_adjacency_matrix_as_described_ab ove,_where_the_rows'_and_columns'_indices_are_in_o rder_of_the_points_just_listed.__
SAMPLE_INPUT_(file_cowtour.in)_
8
10_10
15_10
20_10
15_15
20_15
30_15
25_10
30_10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
OUTPUT_FORMAT
The_output_consists_of_a_single_line_with_the_diam eter_of_the_newly_joined_pastures._Print_the_answe r_to_exactly_six_decimal_places._Do_not_perform_an y_special_rounding_on_your_output._
SAMPLE_OUTPUT_(file_cowtour.out)
22.071068

[Ared]

Inc karox es ayd xndirneri sayteric tal.

Մոդերատորական: Կարդացեք ակումբի կանոնադրությունը։ Մասնավորապես ֆորումում չեն ողջունվում լատիներեն տառերով հայերեն գրառումները:
Եթե ինչ-որ պատճառով հայերեն մեքենագրելու հետ կապված դժվարություններ կան, ապա կարող եք օգտագործել ֆորումում ներդրված հայերեն մեքենագրման համակարգը, Տրանսլիտի ձևափոխիչը կամ կարդացեք «Ինչպե՞ս գրել հայերեն» թեման : Կամ էլ օգտվեք Փոխարկիչից։

[MSGM]

Որոշեցի վերակենդանացնել այս թեման, երևի հետաքրքրվողներ կլինեն: Առաջարկում եմ, օրինակ, հետևյալ խնդիրը:

Որևէ տողի "արտադրյալի արժեք" կանվանենք այդ տողի մեջ պարունակվող թվանշանների արտադրյալը: Օրինակ` "263" -- 2 * 6 * 3 = 36:
Տողը կանվանենք "գունավոր", եթե դրա բոլոր ենթատողերի արտադրյալի արժեքները տարբեր թվեր են (այսինքն` կրկնվող արժեքներ չկան): Օրինակ` "263"-ի ենթատողերն են "2", "6", "3", "26", "63" և "263", որոնց արտադրյալի արժեքներն են 2, 6, 3, 12, 18, 36: Քանի որ կրկնվող թվեր չկան, "263" տողը գունավոր է: Իսկ օրինակ "236"-ը գունավոր չէ:
Տրված են n (1 <= n <= 50) և k (1 <= k <= 1,000,000,000) թվերը, պահանջվում է գտնել n երկարությամբ k-րդ ամենափոքր (այբբենական դասավորությամբ) գունավոր տողը: Եթե n երկարությամբ գունավոր տողերի քանակը k-ից փոքր է, պետք է վերադարձնել դատարկ տող:

Օրինակներ.

1)
n = 3, k = 4
Պատասխանը` "238", դրանից փոքր մյուս 3 գունավոր տողերն են` "234", "235", "237":
2)
n = 4, k = 2000
Պատասխանը` ""(դատարկ տող):
3)
n = 5, k = 1
Պատասխանը` "23457":
4)
n = 2, k = 22
Պատասխանը` 52:

[Հովհաննես]

Այդպես հանգիստ կարելի է ասել, որ 9+-ում ոչ մի գունավոր չկա էլ ինչ
Հետո ցանկացած թիվ, որ գոնե մեկ հատ 1 է պարումակում նույնպես չի կարող գունավոր լինել, նույնը վերաբերում է 0-ին, ուրեմն 8+ :Ճ
K ավելի մեծ է քան պահանջվող թիվը,

[MSGM]

Դե էտքան բանը նկատելը հերիք ա էս խնդիրը լուծելու համար, որովհետև կարելի ա դիտարկել բոլոր հնարավոր տողերը (դրանք n! հատ են, n <= 8, թե չէ` դատարկ տող), գտնել գունավորները ու տեսնել դրանցից որն ա k-երորդը: Էսի շատ հասարակ խնդիր էր: