Блог пользователя fcspartakm

Автор fcspartakm, 9 лет назад, По-русски

508A — Паша и пиксели

Для решения данной задачи заведем матрицу типа bool размера n на m. В ячейке (x, y) данной матрицы будем ставить значение true, если соответствующая клетка окрашена в черный цвет.

Пусть на k-том ходу Паша красит пиксель в позиции (i, j). Тогда на этом ходу игра закончится, если образуется квадрат 2 × 2 из черных клеток, а клетка (i, j) будет левым нижним, левых верхним, правым нижним или правым верхним углом этого квадрата. Только такие квадраты и нужно проверить на текущем ходу. Если таких квадратов не образуется за k ходов, выводим 0. Асимптотика решения — O(k), где k — количество ходов.

508B — Антон и та самая валюта

Так как изначально число нечетное (значит последняя цифра в нем нечетная), а необходимо сделать четное, то понятно, что необходимо поменять местами последнюю цифру с какой-то четной. Стоить отметить, что так как число очень большое, удобно его хранить в строке. Так как необходимо сделать максимально возможное число, сделаем следующее.

Переберем все цифры в числе, начиная от старшей, и если встретим четную цифру, которая меньше последней цифры числа — поменяем их местами, это и есть ответ. Если такой цифры не нашлось, переберем все цифры числа в порядке от предпоследней до первой (до старшей цифры числа), и если встретим четную — поменяем местами ее и последнюю цифру числа. Ответ не найдется лишь в одном случае, если в числе нет четных цифр. В таком случае выводим  - 1. Асимптотика решения — O(n), где n — длина числа.

508C — Аня и привидения

Данная задача решается с помощью принципа жадности. Так как приходы всех привидений заданы в хронологическом порядке — будем перебирать их по очереди.

Будем хранить массив, в котором будем помечать моменты времени, в которые мы зажигали свечи (например, ставить в соответствующую позицию 1). Тогда для каждого нового привидения узнаем количество свечей, которые будут гореть во время его посещения по данному массиву.

Если привидение пришло в момент времени wi, проитерируемся по нашему массиву от wi - 1 до wi - t, где t — количество секунд, которое горит свеча, и посчитаем количество единиц. Если это количество не меньше, чем r, перейдем к следующему привидению. Иначе, проитерируемся по массиву от wi - 1 до wi - t, и, если в текущее время свеча еще не зажигалась — сделаем это, и поставим в эту позицию 1. Это нужно делать, пока количество единиц в этом отрезке массива не станет равно r. Если так сделать нельзя на какой — то итерации, то выводим  - 1.

В конце нужно просто пройти по нашему массиву, и посчитать количество зажженных свечей, то есть единиц в массиве. Асимптотика решения — O(mt), где m — количество привидений, t — количество секунд, в течении которого горит одна свеча.

508D — Таня и пароль

В данной задаче входные данные сначала нужно представить в виде ориентированного графа. Вершинами в данном графе являются все возможные строки из двух символов — строчных и прописных букв латинского алфавита, а также цифр. Тогда для всех заданных трехбуквенных строк si-ых, добавим ребро из si[0]si[1] в si[1]si[2].

Теперь осталось найти в данном графе эйлеров путь. Для этого можно воспользоваться алгоритмом Флери. Стоит отметить, что Эйлеров путь найдется, если количество вершин, у которых степень исхода и входа отличается на единицу, не более двух, а степени исхода и входа всех остальных вершин равны. Если Эйлеров путь не найдется, нужно вывести NO. Асимптотика решения — O(m), где m — число ребер в графе, а соответственно и число заданных подстрок, ведь от каждой подстроки в граф будет добавлено ровно одно ребро.

508E — Артур и скобки

Данная задача решается методом динамического программирования. Заведем квадратную матрицу Z размера n × n, где n — количество открывающихся скобок в последовательности. Основной идеей данной задачи является то, что если открывающаяся скобка стоит в позиции l, а соответствующая ей закрывающаяся скобка — в позиции r, то с позиции l + 1 до позиции r - 1 должна стоять правильная скобочная последовательность.

В нашей динамике первый параметр lf — номер открывающейся скобки, а второй rg — номер самой последней открывающейся скобки, которая может быть в правильной скобочной последовательности, которая будет находиться между открывающейся скобкой под номером lf и соответствующей ей закрывающейся.

Значением динамики будет — true (можно составить такую последовательность) или false (нельзя).

Будем писать ленивую динамику по этим двум параметрам (по отрезкам). Переберем cnt — сколько открывающихся и, соответственно, закрывающихся скобок будет стоять между открывающейся скобкой под номером lf и соответствующей ей закрывающейся. Если это количество попадает в нужный интервал для открывающейся скобки номер lf, запустим нашу динамику от двух отрезков — (lf + 1, lf + cnt) и (lf + cnt + 1, rg).

Если для обоих отрезков можно составить правильные скобочные последовательности, соответствующие входным данным, положим в Z[lf][rg] значение true. Чтобы восстановить ответ, нужно переходить из отрезка (lf, rg) в отрезки (lf + 1, lf + cnt) и (lf + cnt + 1, rg), если для их обоих возможно составить правильную скобочную последовательность и рекурсивно восстанавливать ответ. Если Z[0][n - 1] равно false, то нужно вывести IMPOSSIBLE. Асимптотика решения — O(n3).

UPD Данная задача может быть решена с помощью жадного алгоритма. Асимптотика решения O(n). Пример такого решения участника matrix.

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Fast editorial.

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

give me -

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could you please upload solutions?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Hello new user.

    You can find others solutions in site. Go to Dashboard then click on x???? numbers right side of problems name.

    On the opened page , click on numbers in first column(#) and read the answer , but be careful just read the Accepted submits :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why can't divide and conquer be applied to problem E?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D has less accepts of E. D is harder than of E OR because of hard->easy solvers ?!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Well E is pretty easy, just a simple DP (it's not completely obvious what the DP should exactly do, but the rough idea of DPing by current opening bracket and the distance to its closing one is there quite clearly). On the other hand, the algorithm needed for D can be hard to code even if you know what to do.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится -17 Проголосовать: не нравится

      On the other hand, the algorithm needed for D can be hard to code even if you know what to do.

      You are talking about dfs, right?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        Considering you failed systests, are you saying you can't code a DFS?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Having silly bugs is ok for me.

          You seem to be pretty hateful. I was not pointing at me or you personally. After your words about difficulty level of this problem I just wanted to ensure that you are talking about the same solution as I had.

          Relax ;)

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +6 Проголосовать: не нравится

            It's hard to make silly bugs in "just a DFS".

            Hate seems to be a pretty common retort these days. There are cases when I read a problem and think "ok, this is easy to do", then start coding, but with some "oh wait, I can't just do this" moments, a lot of silly mistakes and it still fails in the end. When I look back at the result, I usually think that maybe it wasn't so simple after all. I was just pointing this out as a similar case.

            Constructing Eulerian circuits is a well-known problem, but IMO falls into this category.

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              It's hard to make silly bugs in "just a DFS".

              Ok, compare my failed and accepted solutions.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Okay, I just did. What I saw: twice "obviously not just a DFS". (which doesn't mean that it doesn't use DFS, but that it uses a lot of other stuff)

                It's definitely something that can be hard to code, which is what I was initially saying, and it's more complicated than the DP (+ reconstruction) needed in E. Thanks for confirming my point :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why you didn't increase constraints for C?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    With these constrains some can confuse the problem with a dp problem, that was my first impression when I read the problem and constrains (I guess).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if the constraints for problem C are increased, i think we can do it using segment trees. am i right?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah, I was talking about increasing up to about 105 not to 103.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you explain solution or share code with segment tree ? thanx

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Count the number of candles lit from time w-t to w-1 using the segment tree/bit O(log n). If this is less than r, then count how many candles can you light up in the range w-t to w-1, and if you don't have enough time to light up these candles, output -1, else add the number of candles you light up to the total and perform an update on the segment tree/bit O(log n)

          Hence asymptotic complexity will be O(n.log n). By the way, will we have to perform updates with lazy propagation?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

can anyone explain the solution for problem E more clearly.....

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

В Е зашла простая жадность :) я конечно рад, но все же интересно — это просто неудачные тесты были или действительно решение верное?

Как решал: проходил слева направо от 1 до 2n и смотрел: можно ли сейчас закрыть текущую открытую скобку. Если да, то закрывал последнюю скобку, если нет, то открывал новую. Вот, собственно и все решение.

посылка

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я тоже жадность написал на Е))

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Speaking of C, we should output -1 only if r > t, am I right? And if so, looks like if we need to light k new candles for next ghost, we will always have at least k consecutive free seconds right before this ghost. Can't prove this, but got AC with solution based on this assumptions.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your assumption is really amazing...!!! :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are close, I think :) Don't know if it's enough to stand out for the proof, but at least gives intuition why does it work. If t < r it's -1. When you try to lighten up r candles the first lightened up are starting to burn out and you cannot keep up. Otherwise, in the worst case, when t == r, we can always start lightning candles way before first ghost appears and keep lightning candle every second. That way at least r candles are always up. Having that in mind, you can start thinking of better approach if you have longer lasting candles. And that better approach is greedy solution described in editorial.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have a question. I was trying to solve D, but got TLE as my verdict. I suppose it was because I used a map to assign each substring a value. As I was looking through the accepted solutions, I saw that a few used, what appeared to be, a function to assign each substring of length two a value. However, they did not use the same constants. example

Does this technique have a name? If so, can somebody supply me a problem or two with which I can practice?

Thanks. :]

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello,

Please I got a time limited excecced on problem B, I don't really see what's the problem with my source code, i've an 10^5 complexity algorithm and I've use Strings and BigIntegers (I use java). Here's my source code, could anybody tell me what's wrong please, or propose me one solution that works?

Help please. ~~~~~

import java.math.BigInteger; import java.util.Scanner;

public class div2_288_pbB {

public static void main(String[] args) {
    String  tomorrow="-1";
    Scanner sc = new Scanner(System.in);
    String ch=sc.nextLine();
    int i=ch.length()-1;



       for(int j=0; j<i; j++){
          char[] ch2= ch.toCharArray();

          int temp1=(int)(ch2[j] - '0');
          if(temp1%2 ==0){
              char temp=ch2[j];
              ch2[j]=ch2[i];
              ch2[i]=temp;



              BigInteger b1 = new BigInteger(new String(ch2));
              BigInteger b2 = new BigInteger(new String(tomorrow));

              if(b1.subtract(b2).compareTo(BigInteger.valueOf(0))== 1 ) 
                 tomorrow=new String(ch2);
          }
       }
    System.out.print(tomorrow);

}

}

~~~~~

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I am learning to write formal proof for the algorithms, I am lost on how to start proof for the greedy algorithm of 508E - Arthur and Brackets. I know how it works, but how to prove it formally. Any helps on this?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I can write proof, but I don't know English very well)) I submited greedy algorithm on contest.
    http://codeforces.com/contest/508/submission/9586845

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I understand the algorithm. What about proof of correctness ?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Here's an attempt at the proof of correctness.

        Typically, whenever we see a problem with greedy and we want to prove that it is correct, we do some sort of "exchange" argument (i.e. given a valid/optimal configuration, we can always swap some things so it looks like what our greedy will do).

        Suppose we have some valid solution that did not close parenthesis as soon as possible.

        For instance, let's look at a simple example

        3
        2 5
        1 4
        1 4
        

        One valid solution is ((())), while a greedy would give us (())()

        Let position i be the first position in which the valid solution could close a parenthesis, but didn't. In our example above, the first position in which this happens is at position 3.

        Now, let k be the index of the opening parenthesis of the closing parenthesis at position i that we could have closed (in our example, this would be the second parenthesis). We will make a swap in our valid solution to make it one step closer to what the greedy would have done. Let j be the position in our valid solution of the k'th opening parenthesis.

        Back to our example, we have this scenario:

            j
            v
        ((()))
         ^^ 
         ki
        

        Now, we're ready to make a swap. It is perhaps best described with a picture as follows:

            j
          --v
        ((()))
        
        turns into
        
          j 
          v--
        (()())
        

        Notice that the things under the dash marks are unchanged, so this is still valid. The only distance that changes is the k'th opening parenthesis, and it decreases to a valid amount. This means that this is still a valid solution, but we've moved our valid solution to look more like our greedy's solution. We can apply this argument over and over again until we get something that looks exactly like our greedy (i.e. close parenthesis as soon as possible).

        The above shows that for any valid solution, we can make a series of swaps so that it exactly matches our greedy solution. That means that if there exists a valid solution, then our greedy solution will find a solution. The contrapositive of this statement is also true, which says that if our greedy doesn't find a solution, then there is no valid solution. So, closing parenthesis as soon as possible works.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can someone explain the dynamic programming solution for E?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Yes

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Haha, very funny, I can't stop laughing -_-

      Aside, will someone please explain the dynamic programming solution for E? Just define what Z[i][j] is, I can probably figure out the recurrences :P

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится -21 Проголосовать: не нравится

        Yes

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        Here in Z (I, j) I is the position of opening bracket u r currently at and j is end point of this segment.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        I would also want an explanation ofthe dynamic programming solution for E, in the editorial is poorly written in English and I am unable to understand it.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          I quite agree, the explanation for E is poorly written. hereicomewf : what exactly is "this segment" in your explanation?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Let Z[i][j] be true if there is a way to satisfy the conditions using ONLY the ith to jth conditions (with j-i+1 pairs of parenthesis), and false otherwise. Our final answer is Z[0][n-1] (if you want to actually reconstruct a solution, you need to keep prev pointers, but this is not the main point of the algorithm).

    We know that i opens then closes, and let k be the number of pairs of open/close parenthesis that go in between the i-th open and close parenthesis. Then, we need L[i] <= 2k+1 <= R[i] as well as Z[i+1][i+k] and Z[i+k+1][j] (you need to define base cases and the corner cases carefully, but it's not too hard).

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Мне кажется, или жадный алгоритм — более очевидное решение по Е, чем какая-то динамика.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution for problem C is in O(w) (O(w*log(w)) while contest because of using BIT). And it's accepted. So we don't need (m*t) here?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the dynamic programming solution of problem E?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

код matrix к задаче Е на тест 2 2 2 1 2 выдает IMPOSSIBLE вроде же должен (()) или я не прав?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain dfs solution of problem D.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Firstly, you need to construct the graph. According to the solution of the tutorial (which is really a good one), you can build the graph from the three letter strings. Say for example:

    You have a string abc. While making graph, you split this string into two parts: ab and bc. Now suppose your adjacency list is adj. All you need to do is push the right node (bc) to the list of the left node (ab) like this: adj["ab"].push_back("bc").

    Now you need to make sure that the constructed graph has an Eulerian Circuit or an Eulerian Path. For this you have to make some checking. You should check out this link if you don't know the conditions of Eulerian Circuits or Paths: Conditions for Eulerian Paths and Circuits. Remember that the graph is directed. :)

    After you have made the confirmation that your graph has an Eulerian Path or Circuit, all you need to do is run a dfs. In this case I ran dfs and made sure that all the edges from a node are visited. To save the path, I pushed them in a vector. The resultant vector will store the nodes in reverse order, so I had to reverse it.

    You can check my submission here: 9619543 I did not convert the characters and strings into integers as I thought that the time limit is quite good enough. It took 873ms which is really good compared to 2000ms :D :P

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem D, I am curious that, is the number of edges m too large for a recursive solution? My code gave a Runtime Error for testcase 30 on my computer. However it passed the test on codeforces' server.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem D i'm detecting if the the graph is a euler graph and then i'm finding the path using heirholzer's algorithm ... i don't know what i'm doing wrong but i'm stuck at testcase 8 ... can anyone point out my mistake ?? 9608421

»
9 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

seems that systests for problem D are weak. I dont want to point fingers but some solutions don't pass these tests:

8 ebc bcd deb cde dey eyx yxq qey xqe

8 ebc bcd deb cde dey eyx yxq xqe qey

answer for both should be YES

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Actually, notice that you have n=8 but 9 strings after that, so the input is invalid.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    didn't look carefully enough. some Eulerian path implementations seemed deceptively too simple )

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I know it's four weeks late but I have a little question on problem E:

Does the test case 2 2 2

Gives a (()) ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No the answer for 2 2 2 2 2 is IMPOSSIBLE, as you can see that the minimum distance of between 2nd opening and closing brackets has to be 2, and is 1 in (()). Keep in mind that the bracket that opens first, closes last. If we denote each bracket differently which is required in the question, your answer is ([)] which as you can see is not a proper sequence.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, and sorry for typo, I meant for 2 2 2 instead but I got your point :)

      I just totally ignore the basic point: "the bracket that opens first, closes last"...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi everyone. As I know, when we need to find Euler path or Euler circuit we should keep in mind to avoid choosing 'bridge'-s, I found some forums where people solve without considering it, by stacks, for their algorithm I have test case where it fails. But I don't know how to find and update bridges in graph in such a way, that time complexity didn't make a problem for problem D. Could you help me?!

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Just modifying the 508 — B 'Anton and currency you all know' problem,
how to solve if we want to find the maximum number by swapping exactly 2 digits?
(given input number can be odd or even but number to be obtained should be
case 1 : even,
case 2: odd,
case 3 : can be odd or even) ?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm a newbee..This may be a silly question.:P..but can anyone tell me why we are checking euler path in D problem.??..also for euler path in and out degree should be equal..right.??here it is written to be <=1

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

The editorial of problem D suggests to use Fleury's algorithm but that algorithm is O(m^2),where m is the no. of edges, which is not efficient enough to solve the problem. To solve it we must use Hierholzer's algorithm to find the Euler path or circuit. This algorithm works in O(m). Here's my solution using this algorithm: 45387404

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody give a formal proof of greedy solution of problem E ?

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can some one check my solution .It is not pass test case 7: Submit

output: - 0 64 65 2 1 64 65 2 2 64 65 2 3 64 65 2 4 64 65 2 5 64 65 2 6 64 65 2 7 64 65 2 8 64 65 2 9 64 65 2 10 64 65 2 11 64 65 2 12 64 65 2 13 64 65 2 14 64 65 2 15 128 129 4 16 128 129 4 17 128 129 4 18 128 129 4 19 128 129 4 20 128 129 4 21 128 129 4 22 128 129 4 23 128 129 4 24 128 129 4 25 128 129 4 26 128 129 4 27 128 129 4 28 128 129 4 29 128 129 4 30 128 129 4 4