1. Centipede waking up from wrong side of bed doesn't matter in this problem. Since the centipede gets the slippers randomly, the problem is asking about the worst case which results in the most time taken. 2. If the centipede finishes all the left slippers, i.e. 40 of them , there are still a-40 left slippers present under the bed. The problem doesn't even mention that after wearing 40 left slippers, these a-40 left slippers will also be thrown taking 2 seconds. Throwing is only mentioned for right slippers. Edited by author 22.08.2023 07:39 Edited by author 22.08.2023 07:42 Hi, I'm still getting WA-1, can anybody give me answers to these tests: 80 60 60 80 60 60 Thanks. My AC program writes following answers: 80 60 >> 199 60 80 >> 200 60 60 >> 160 BTW I solved this problem without any boring special cases consideration, using only stupid DP[101][101]... My any Java solutions get's WA 1 too. i think it's problem with java, have same too. wa for any solution, which has got ac before. I saw DP[101][101], is it for dynamic programming ? I don't think we'll need it. Edited by author 31.10.2011 02:12 in this problem dont need DP. you may take max from two optimal cases ;D ...or think how to make on DP Edited by author 31.10.2011 02:21 80 60 199 60 80 200 60 60 160 Its quite easy to do. Basically, there are 2 "worst" cases: 1). We take 40 right (equals 40*2=80 secs), then throw all the rest of the right ones (2*(b-40) secs), and them take the 40 left (40 secs). The time is 80+2*(b-40)+40=120+2*(b-40). 2). We take 39 left (78 secs), take 40 left ones (40 secs), throw all the other left ones away (2*(a-40)), and take the last right one (1 sec). The time is 78+40+2*(a-40)+1=119+2*(a-40). The answer is the maximum of these two. ONU_1785 In the case two, when you say: "We take 39 left (78 secs)", why? If I take the first 39 lefts, this not is 39 secs???? one second per each slipper ONU_1785 means 39 right, it's just a typo. Edited by author 20.05.2012 15:54 In the case two, when you say: "We take 39 left (78 secs)", why? If I take the first 39 lefts, this not is 39 secs???? one second per each slipper He wanted to wright 'We take 39 right' Very hard problem, I thought about 20 minutes and then wrote DP[101][101][41][41] :) why 39 rights and no 40? There are 2 possible bad ways: 1) mode "putting on left slippers" |*0*|0| slippers come only for right legs |*0*|40| (time +40*2) if there are more than 40 slippers for right legs they still come |*0*|40| (time + (b-40)*2) then there are slippers only for left legs |*40*|40| (time +40); 2) mode "putting on left slippers" |*0*|0| slippers come for right legs except 1 |*0*|39| (time +39*2) then slippers come only for left legs |*40*|39| (time +40)
now mode changes to "putting on right slippers" |40|*39*| happy centipede hopes to get the last needed right slipper, she gets all slippers for left legs, which are still left |40|*39*| (time + (a-40)*2) and finally she gets the last one right slipper |40|*40*| (time +1) So, just choose the worst way according to exact input. you have 60 and 80, from where you take 39? using System; namespace _1876_Csharp { class Program { static void Main(string[] args) { int a= Convert.ToInt32(Console.ReadLine()), b = Convert.ToInt32(Console.ReadLine()); int c = Math.Max(2 * a + 39, 2 * b + 40); Console.WriteLine(c); } } } After so many calculation and math I have solved the problem..... Here we can have two worst cases... Case 1: having all the right shoes first.so here needed time is 2*b and we have now all the left shoes remaining...so total time is 2*b+40... Case 2: we may have 39 right shoes so time needed here is (39*2=78)...then we have only one right foot left but we may encounter all the left shoes and here needed time is 40+2*(a-40)....> 40 for the first 40 shoes and 2*(a-40) is for the remaining shoes as they needed to be thrown away...then we have the only one right foot left and it need 1 second... so total time = 78+40+2*(a-40)+1 = 119+2*a-80 = 2*a-39 ans=max(Case 1,Case 2) Edited by author 22.02.2020 03:07 But it's given that both a,b>=40.....so how 39 right shoes can be there? mistake in case 2: 119+2*a-80 = 2*a+39 everything else is correct Edited by author 11.01.2021 22:56 Please, correct me if I am wrong. In the worst case, first of all our centipede will take 40 right slippers (40slip * 2sec) After that it will take all of the remaining right slippers ((rightSlippers-40) * 2sec) Then, because there are no right slippers left, it will take 40 left slippers(40slip * 1sec) And finally take remaining left slippers and throw them away ((leftSlippers-40) * 2sec) I guess I didn't understand the task correctly, may someone explain it to me? Update: I guess I should of have searched a little more, I found what is the case. If any of you are interested the solution is that there may be another situation where we have >40 left slippers, so first we take 39 right ones, then 40 left ones, throw remaining lefts away and take our last right. Depending on which one is longer, you may use this solution or the one I posted before. P.S. of course you don't have to throw away the remaining slippers once all legs are dressed, my bad. 100 40 Answer is 200 ? no,need 39*2 + 40 + 60 * 2 + 1 why wa 3 test? help This problem don't need more than 3 tests, I think ;) Edited by author 22.10.2011 20:08 NO, I think this problem don't need more than 2 tests. there are 2 possible answers: 2*a+39 and 2*b+40. you must choose biggest Why 39 ????? What is 2*a+39 ????? Why 39 ????? What is 2*a+39 ????? 39 * 2 + 40 + (a - 40) * 2 + 1 = 2 * a + 39 #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; if (39+2*a>a+2*b) cout << 39+2*a; else;cout << 40+2*b; return 0; } if (39 + 2 * a> 40 + 2 * b)т.к правую ногу полностью обули take maximum of this two: ansa=a*2+39; ansb=b*2+40;
import java.util.Scanner; public class AcmTimusRu { public static void main(String[] args) { Scanner s = new Scanner(System.in); int a = s.nextInt(); int b = s.nextInt(); if (39 + 2 * a > a + 2 * b) { System.out.println(2*a+39); } else { System.out.println(2*b+40); } } } Not a + 2 * b. You must use 40 + 2 * b. #include <iostream> using namespace std; main() { int a, b; cin >> a >> b; if (39+2*a>a+2*b) cout << 39+2*a; else cout << 40+2*b; } my code is wrong :CC where is error? Edited by author 26.04.2014 10:14 I think the problem is little unclear. It does not mention if the centipede continues putting shoes with the same strategy for right foot, when it is so. Edited by author 03.07.2013 19:21 GIVE ME SOME TESTS 41,40 100,40 40,100 60,60 73,68 read the text! The text is inadequately worded, it does not specify the process for shoeing the right feet after the left feet are filled. The solver must assume that the process for filling the right feet is the same as for filling the left feet. Is this phrase "Today the centipede has got out of bed on the wrong side, so it is preparing for the worst" relevant for solving the problem? No, but explanation "will need for shoeing in the worst case" in output give us the same information. is it necessary to keep a,b between 40 and 100 maybe it's the problem Problem is find to maximal value between two values which are depends of A and B)It's very easy. Edited by author 19.03.2012 18:17 Можно больше тестов от accepted прог, а то условие не совсем понятное для случаев когда a<b, a>b, a=b. What is the interest to solve problem when all partial cases are given? Probably, it is better to clarify what is not clear to you in the problem statement. P.S. Be polite with regard to participants from other countries, use English. Edited by author 24.10.2011 10:32 |
|