Задача A. Собеседования
Задачу добавил: alef
Успешно сдано решений: 496
Будущий программист Кеша хочет попасть на летнюю стажировку. Вообще говоря, он хочет попасть на стажировку во вполне конкретную компанию. Однако Кеша считает, что нужно сходить на все собеседования, на какие получится попасть.
К огорчению Кеши, некоторые компании проводят собеседования в один и тот же день. Вот и завтра собеседования с желающими попасть на стажировку проводят две компании — AAA и BBB.
В компании AAA собеседования начнутся в момент времени s1, а в компании BBB — в момент времени s2. Длительность собеседования с кандидатом на стажировку в компании AAA составляет t1 единиц времени, а в компании BBB — t2 единиц времени. Последних кандидатов в компании AAA пригласят на собеседование в момент времени f1, а в компании BBB — в момент времени f2. Кроме того, на дорогу от компании AAA до компании BBB (или наоборот, от компании BBB до компании AAA) у Кеши уйдёт r единиц времени.
Собеседования в обеих компаниях проводит большое количество специалистов, поэтому можно считать, что беседовать с Кешей начнут сразу же, как только он придёт в офис компании.
Кеша, конечно, хочет попасть на собеседование в обе компании. Однако если успеть в обе компании ему точно не удастся, он сходит на то собеседование, после которого он может раньше освободиться. Ваша задача — определить, попадёт ли Кеша только на одно собеседование или же на оба, и если на оба — то в каком порядке он должен посещать компании.
В первой строке содержатся целые числа s1, f1, t1 (1 ≤ s1 < f1 ≤ 1000, 1 ≤ t1 ≤ 1000) — момент времени, когда начнутся собеседования в компании AAA, момент времени, когда на собеседования в компании AAA будут приглашены последние кандидаты, длительность собеседования с канидадтом в компании AAA.
Во второй строке содержатся целые числа s2, f2, t2 (1 ≤ s2 < f2 ≤ 1000, 1 ≤ t2 ≤ 1000) — момент времени, когда начнутся собеседования в компании BBB, момент времени, когда на собеседования в компании BBB будут приглашены последние кандидаты, длительность собеседования с канидадтом в компании BBB.
В третьей строке содержится целое число r (1 ≤ r ≤ 1000) — время, которое необходимо Кеше на дорогу между компаниями.
Выведите в качестве ответа строку, состоящую из одного или двух символов.
Строка должна состоять из одного символа, если Кеша успеет на собеседование только в одну из компаний. Этот символ должен быть символом A, если Кеша пойдёт на собеседование в компанию AAA, и символом B, если Кеша пойдёт на собеседование в компанию BBB. Если возможны два варианта ответа, выведите любой.
Строка должна состоять из двух символов, если Кеша успеет на оба собеседования. Если Кеше нужно сначала посетить компанию AAA, а затем компанию BBB, то ответом должна стать строка AB. Если же Кеше нужно сначала посетить компанию BBB, а затем компанию AAA, то ответом должна стать строка BA. Если оба варианта ответа являются допустимыми, выведите любой.
Подзадача 1 (до 20 баллов)
Отрезки [s1, f1] и [s2, f2] не пересекаются.
Баллы начисляются за каждый пройденный тест.
Подзадача 2 (до 80 баллов)
Взаимное расположение отрезков [s1, f1] и [s2, f2] может быть любым.
Баллы начисляются за каждый пройденный тест.
По запросу сообщается результат проверки на каждом тесте.
50 180 30
220 250 25
60
AB
220 250 25
50 180 30
175
B
120 150 50
110 210 60
45
A
110 210 60
120 150 50
40
BA
10 500 120
100 400 80
75
AB
Обратите внимание, что 3, 4 и 5 примеры не удовлетворяют условиям Подзадачи 1. Однако, чтобы быть принятой на окончательную проверку, Ваша программа должна выводить правильные ответы на все тесты из условия.
А теперь поясним приведённые примеры.
В первом примере Кеша может прийти на собеседование в компанию AAA в момент времени 130, и спустя 30 единиц времени (которые будет длиться собеседование) отправиться в компанию BBB. Кеша придёт в точности к началу собеседования в компании BBB (в момент 220). Ответом будет строка из двух символов AB.
Во втором примере Кеша никак не успеет на оба собеседования. По условию задачи он выберет то, после которого он раньше освободится. Как легко видеть, это собеседование в компании BBB: Кеша может прийти, например, к самому началу собеседования (к моменту 50) и спустя 30 единиц времени (в момент 80) уже будет свободен (собеседования в компании AAA ещё не успеют начаться к этому моменту). Таким образом, ответом будет строка из одного символа B.
В третьем примере Кеша также не сможет попасть на оба собеседования. Однако в этом случае ответом может быть и строка A (как в примере), и строка B. Действительно, если Кеша отправится на собеседование в компанию AAA к самому раннему моменту времени 120, то он может быть свободен спустя 50 единиц времени в момент 170. Если же Кеша решит пойти на собеседование в компанию BBB к самому раннему моменту времени 110, то он также освободится в момент 170, спустя 60 единиц времени.
В четвёртом примере Кеше следует пойти на собеседование сначала в компанию BBB, притом к самому раннему моменту времени 110. Тогда спустя 60 единиц времени — в момент 170 — он сможет отправиться в компанию AAA. Доберётся он до компании AAA в момент времени 210, когда будут приглашать пройти на собеседование последних кандидатов (так что Кеша успеет). Поэтому ответом будет BA (легко проверить, что AB не может быть ответом).
В пятом примере Кеша успевает на оба собеседования, и не важно, в каком порядке он будет их посещать. Например, Кеша может прийти в момент 10 в компанию AAA, пройти собеседование и в момент времени 130 отправиться в компанию BBB. До неё он доберётся в момент времени 205, что позволяет ему попасть на собеседование (последних кандидатов пригласят в момент времени 400). Также Кеша может сначала отправиться в компанию BBB (например, к моменту времени 100), пройти собеседование за 80 единиц времени, и в момент 255 оказаться в компании AAA. Последних кандидатов там приглашают в момент 500, так что Кеша опять же успевает. И ответ AB, и ответ BA будут верными.