Общий форумNumber of zeros in bracket: 0 1 2 3 4 Sequence : (1) (10) (100) (1000) (10000) 1 is found at : T0+1 T1+1 T3+1 T4+1 T5+1 Value of Ti+1 : 0+1 1+1 3+1 6+1 10+1 The i-th triangular number is the sum of the i natural numbers from 1 to i. Ti = i(i+1)/2 i-th '1' is located at (Ti+1)-th position. Let, z = (Ti + 1) = (i(i+1)/2) + 1 -> z = (i^2 + i + 2)/2 -> 2z = i^2 + i + 2 -> (1)x(i^2) + (1)x(i^1) + (-2(z-1)x(i^0) = 0 So, now if we solve for i using quadratic formula, i = (-1 +- squareRoot(8z-7))/2 [do calculation on your own] z = {1,2,4,7,11,...} plugin these values and you will find that squareRoot(8z-7) = an integersquare number for any z. So, a number belongs to z only and if only squareRoot(8z-7) can produce an integer. And here z is the position number where the digits are 1. [code deleted] Edited by author 24.12.2020 19:00 Edited by moderator 14.02.2021 18:16 Бред. В самом деле, достаточно искать символ, который чаще всего встречается.... так не работает работает, не мне одному приходят в голову умные мысли... Please, think about the problem yourself at first! I think you could use this problem to exercise your heuristics and optimization skills and thus I'm sharing a solution that is both easy to think and implement so that somebody less experienced might learn new strategies in optimization problems. ////// Yes, it's a Vehicle Routing Problem, as even confirmed by the author on this forum. Firstly, you can compute —with Dynamic Programming— optimal distance visiting some subset of nodes starting at node 0 and ending at some other node. Let dp[S][last] be the state of such DP, which computes the smallest path cost that visits each vertex of S once and starts at 0 and ends at last. This is a classic TSP DP problem that can be computed in O(N^2 2^n). Note, that you have to use a type shorter than 32-bit to store the DP. The cost of a trip is then dp[S][last] + D(last, 0). Generate a starting solution that performs a trip for each lorry, M trips in total. So far, nothing a beginner cannot do! Perform heuristic search to improve it. I used a Large Neighbourhood Search heuristic. Remove some number of lorries from trips from the CURRENT_SOLUTION and try to insert them one by one again. That is, greedily calculate the cost of insertion, using DP, of each lorry in each trip —or creating a new trip— and choose the lorry and a trip with smallest possible value. Decide if the obtained repaired solution is the new CURRENT_SOLUTION. I implemented this decision using Simulated Annealing, but you can simply do it if the repaired solution has a better cost. If the CURRENT_SOLUTION is better than the BEST_SOLUTION, well, you know what to do! I started from the small number of removed lorries and gradually increased it if after some iterations there weren't an update to the BEST_SOLUTION. This is a gradual increase of Neighbourhood. In fact, my solution is terribly inefficient, and I could use better data representation and save time making some calculations, improved heuristic by adding more complex rules, and perhaps get rid of the DP step in favor of simple random greedy insertions. But, I just decided to keep things simple. 0 0 0 1 0 0 2 1 1 2 2 1 ans Invalid Совет для тех кто решает векторами, лично у меня не получилось сдать задачу векторами, пришлось писать уравнения прямой в пространстве 49 9 9 9 9 9 9 14 14 34 34 34 34 34 42 42 42 42 42 47 49 57 66 68 68 68 68 71 71 71 71 71 74 74 97 97 97 97 97 97 97 100 100 100 100 100 100 100 100 100 100 227 235 264 292 298 322 327 341 820 I have to say ,I'm toooooooo stupid..... wa haha Accpeted congratulations , looking forward another rejudgement hahaha Thanks for the good test ! Are the any other inputs you mined here bit by bit? :) Please share them with us, don't hesitate. What is the best way to collect information for particular test? Time/100ms (if there is window for that), memory/100kB, WA, TLE, RE... what else? What maximum number of bits per try? Let's call it `bitrate`. Serious enough term for further discussion =), isn't it? How to match particular test? Binary search for hash value of the input? Please, reveal your super-duper technology with your fancy-nancy metrics. Edited by author 18.12.2017 22:11 I just use stupid bianry search every veriable and submit many many many times I don't have better ideas and I have only test case 70... Edited by author 19.12.2017 05:09 //6 min 32.43 sec 4 100 71 42 14 4 97 57 47 34 5 100 71 42 42 9 5 100 100 74 9 9 5 100 74 66 49 9 5 100 100 71 42 9 5 100 100 71 42 14 5 100 71 68 68 34 11 97 97 97 97 97 97 68 68 34 34 34 The 83-rd test is almost the same. Can anybody post DP approach, if any exists? Dp[i][diff][c]: amount of pairs of numbers (A, B) of size i where S(A+B)-S(A)-S(B)=diff and we carry c from the sum of A and B Here we consider also number with leading zeroes, we can notice that **diff** is in the range [-460, 900] -maybe we can make it narrower- and that **c** is either 0 or 1. Why would I move the hand to another box? We only have to put pieces in their places, we don't have to put our hand anywhere into the box. If ur hand fixed on box i, then u can move it to some other position j and it worths 1, but if piece of color j in box i now, u can move it to box j with ur hand Not bad Edited by author 07.12.2020 21:40 Not bad Edited by author 12.12.2020 23:06 Hi there! Here is my code for this task: https://notabug.org/thrashzone_ua/c_examples/src/master/rock_heap.c Short notes: 1) Cases when there is one or two rocks from input are separated 2) In case amount of rocks is more then 2, I'm checking if there is a sublist in list of rocks with sum(sublist) = sum(list) / 2. If there is such a sublist and the number of sum is even - 0 will be printed, if number is not even - 1; 3) In case there no such sublist - it's time for greedy algorithm. Could you please take a look and comment my code? Or maybe provide with test set, on which it will fail? Thank you in advance. So, long story short - do not use greedy algorithm, read and think more about dynamic programming. Пишу на C#: using System; namespace Timus_Console { class Program { static void Main(string[] args) { int ans1 = Convert.ToInt32(Console.ReadLine()); int ans2 = Convert.ToInt32(Console.ReadLine()); int st = ans1 + ans2; Console.WriteLine(st); Console.ReadKey(); } } } Edited by author 25.03.2016 11:48 Не могу не чем помочь. Пишу на Питоне и Паскале Please read: http://acm.timus.ru/help.aspx?topic=judge&locale=en"The program must print only the data that is required by the problem statement. The program must not print any prompts (“Enter N:”). The program must not wait for pressing a key at the end of execution" Also you should make your program passing task sample. Both numbers are on the same line in the sample. тоже не пойму в чем прикол, VS studio все ок работает, а на сайте при отправке ошибка компиляции. Какой синтаксис он использует при проверке Пишу на C#: using System; /*Вычислите a+b (1 5) 1000. A+B Problem */ namespace A_B_Problem { public class Program { static void Main(string[] args) { int a = 5; int b = 1; int c = a + b; Console.WriteLine(c); Console.ReadLine(); } } } в конце программы не нужен пустой Console.ReadLine() или .ReadKey(), только вывод ответа Could some one advise regarding the test 16? As far as I can get my solutions works properly nontheless it fails on the test. Edited by author 16.12.2020 13:34 Edited by author 16.12.2020 13:37 For those who has WA4 or WA7 Test #1: 20 10 3 94 3 3 18 36 7 1 10 73 2 15 19 Answer: 1 Test #2: 7 2 11 6 1 4 1 9 2 5 1 8 3 1 2 7 1 4 2 10 1 7 2 4 2 5 3 99 3 1 5 85 3 4 5 100 1 7 5 100 1 7 6 100 1 7 7 Answer: 4 Test #3: 55 14 87 84 26 14 12 24 14 41 27 85 6 42 18 42 5 49 44 54 1 13 40 85 1 55 17 77 1 9 55 34 5 15 50 31 1 32 55 18 2 54 45 59 8 26 44 79 3 43 52 72 4 51 51 101 5 34 46 35 1 52 18 31 8 47 3 92 1 20 38 10 2 50 1 46 2 5 51 10 2 48 13 92 3 21 52 84 1 12 55 58 2 11 17 24 1 46 54 74 1 30 9 32 2 54 43 29 3 28 52 23 2 1 41 89 1 19 44 49 2 53 1 52 2 40 1 77 6 1 33 44 1 42 9 28 1 52 16 53 1 9 52 74 1 42 2 16 1 37 54 27 1 40 55 72 6 3 21 58 1 13 55 9 1 44 55 37 2 50 23 51 7 21 2 6 1 34 43 27 5 39 43 16 1 40 54 63 2 2 54 93 1 7 55 63 2 13 9 12 1 18 55 94 1 54 12 34 2 41 54 91 1 12 47 99 1 55 27 97 4 25 40 70 1 55 29 21 1 39 54 42 1 9 41 89 1 31 53 84 2 50 17 93 1 14 55 81 4 7 36 68 1 55 14 84 2 7 43 51 1 21 55 85 3 53 23 46 6 1 44 49 2 3 28 42 1 20 53 58 1 53 13 15 2 54 21 59 2 47 50 94 1 17 55 28 2 40 25 49 2 48 54 88 1 55 32 55 4 17 8 47 4 3 17 41 3 49 20 7 1 52 20 67 1 49 52 33 1 38 55 85 5 3 4 23 3 21 45 19 3 11 50 36 1 2 39 67 8 31 1 Answer: 24 Good Luck! Be careful if you use custom I/O. Input data may contain several spaces in a row 1. Limitations were changed. Now 2 ≤ m ≤ 200; 1 ≤ stop_ID ≤ 1000. In old version 1 ≤ m ≤ 1000; 1 ≤ stop_ID ≤ 10000, but there were no such tests. 2. Checker was updated. 3. Some new tests were added. 618 solutions lost AC verdict. Hint: if your solution got Runtime Error, check a stack size in your code. Попробуйте использовать массив, в котором a[i] означает, что из станции i выйдут a[i] пассажиров. . случайно Edited by author 08.12.2020 04:24 Edited by author 08.12.2020 04:24 Edited by author 08.12.2020 04:24 Let suppose there is prefix sum array with mod n is pre1,pre2,......,pren. Since there can be only n-1 numbers present except zero. If zero is one of elements in prefix sum array then answer is already 0 to i. Else If zero is not present then some number should repeat because prefix array is of size n but only 1,2.... n-1 numbers are present. So there should be particular i,j => prei==prej. Therefore from i+1 to j segment will be divisible by n. Edited by author 08.12.2020 00:01 What's the WA 3?? and send me please some tests if u have) can anyone tell me what is test case 13? I have RE5, when I use var s = Console.Readline().Split() var sz = s[0]; var firstElement = s[1]; //!!!!!! There is RE! I have to impose conditions test5 and his input file have a line with only one ("1")!! Input doesn't break lines properly. Incorrect tests are fixed. |
|