I had WA #1 as I printed loops. In other words, if my program had to output a path of length K it would print
1 1
1 2
2 2
2 3
...
(K - 1) (K - 1)
(K - 1) K

Having deleted them, I secured my AC :P

i don't think it's only about IO. i suppose they used not linked list (or just list in c++), but array with 2 iterators + didn't copy the data when there are already more then n - #of_moves elements in array/list

def prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

k = int(input())
for i in range(k):
    n = int(input())
    count = 0
    for f in range(2, 100):
        if prime(f) == True:
            count += 1
        if count == n:
            break
    print(f)


I have same problem

I haven't solved this problem yet. The table that you see right after "The frame consists of the following characters:" statement tells you how you should read these special characters.

I tried to generate the sample input, but not sure if it is correct since these are unprintable characters (atleast with my local PC encoding) and I cannot really verify it.

Nevertheless, here is my attempt to generate it. It looks rugged, but that is because of encoding issues. You should probably output it on your own PC with the program below.


..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
...........ÚÄÄÄÄÄ¿................................
...........³.....³................................
....ÚÄÄÄÄÄij.....³..........ÚÄ¿...................
....³......³.....³..........³.³...................
....³......³.....³..........ÀÄÙ...................
....³......³....Ú³ÄÄÄÄ¿.............ÚÄ¿...........
....³......ÀÄÄÄÄÄÙ....³.............³.³...........
....³......³....³.....³.............ÀÄÙ...........
....³......³....³.....³.........ÚÄÄ¿..............
....ÀÄÄÄÄÄÄÙ....³.....³.........³..³..............
................³.....³.........³..³..............
................ÀÄÄÄÄÄÙ.........ÀÄÄÙ..............
..................................................
..................................................


and the program that output it. It reads squares as in output sample and draws a board.


struct square {
  int x, y, a;
  square() = default;
  square(int x, int y, int a) : x(x), y(y), a(a) {}
};

void solve(std::istream &in, std::ostream &out) {
  std::vector<square> squares;
  int n;
  in >> n;
  for (int i = 0; i < n; ++i) {
    int x, y, a;
    in >> x >> y >> a;
    squares.emplace_back(x, y, a);
  }
  unsigned char board[20][50];
  for (int i = 0; i < 20; ++i) {
    for (int j = 0; j < 50; ++j) {
      board[i][j] = '.';
    }
  }
  for (square sq : squares) {
    board[sq.y][sq.x] = 218; // top-left
    board[sq.y][sq.x + sq.a - 1] = 191; // top-right
    board[sq.y + sq.a - 1][sq.x] = 192; // bottom-left
    board[sq.y + sq.a - 1][sq.x + sq.a - 1] = 217; // bottom-right
    for (int x = sq.x + 1; x < sq.x + sq.a - 1; ++x) {
      board[sq.y][x] = 196; // top edge
      board[sq.y + sq.a - 1][x] = 196; // bottom edge
    }
    for (int y = sq.y + 1; y < sq.y + sq.a - 1; ++y) {
      board[y][sq.x] = 179; // left edge
      board[y][sq.x + sq.a - 1] = 179; // right edge
    }
  }
  for (int i = 0; i < 20; ++i) {
    for (int j = 0; j < 50; ++j) {
      out << board[i][j];
    }
    out << '\n';
  }
}


int main() {
  solve(std::cin, std::cout);
}


As for reading it. I think you used char, while you need unsigned char or int for this problem. You can use getchar() that returns int or read into unsigned char s[SIZE]


Edited by author 20.08.2018 20:13

Edited by author 20.08.2018 20:13

Edited by author 20.08.2018 20:13

Edited by author 20.08.2018 20:19

Edited by author 20.08.2018 20:26

Edited by author 20.08.2018 20:34

As the frame defined by the tripple (X, Y, A) will have such vertices:
(X, Y)
(X, Y + A - 1)
(X + A - 1, Y)
(X + A - 1, Y + A - 1)

Ask for Admin

My AC program also gives this result.

I don't think the tests for the problem are very hard. Using Haskell my program solves this in about 0.5 secs but gets an AC in .031 secs (which I think is the lowest time you can get now), so they could definitely make the problems harder.

The frame is a square=。=

you can try to to it with stack instead of recursion

Maybe that's because you didn't calculate the right shortest-path with the least boots changed(that is, your first number of the output is wrong, but the other one is right). I've got WA7 because I used only one bfs to calculate both values. 2 bfs should be used. (BTW, some of my classmates said only one bfs could also work??? I'm not sure about this.

You should try to look up on the Internet how to find Fibonacci number with matrix exponentiation. The level of material should be accessible to a high school student if you are willing to spend couple of hours getting comfortable with new notations/definitions. There's not much theory behind this. You also need to know how to do fast exponentiation (i.e. in O(lon n) instead of O(n)) and use Long arithmetics (like BigInteger in Java).

Don't know if still relevant =), but the first test is different from sample.
It's a single-level test.

Edited by author 18.08.2018 08:24

first for bound=1e5,using matirx power to compute x0,x1  x[bound],x[bound+1] ,x[2*bound],x[2*bound+1].....  upper bound is 2*p   using map to record  (x[i*bound],x[i*bound+1])

I use this formula and discrete log algo to find candidate of xn+1

then continue to compute xn-1 xn-2 .... until we find (xi,xi+1) in the map then it is valid
otherwise it is invalid
complex : sqrt(p*log(p))

Edited by author 02.12.2017 15:17

I've found one test that takes about 20 seconds to process. It looks quite simple but for my greedy approach it's real hell

########
#......#
#------#
#*****-#
#------#
#$$$$$$#
#-----@#
########

Now it takes about 3 seconds to process this test but still TL 57-62...

Other not bad test:
########
#.....-#
#--##--#
#-*----#
#--#-#-#
#$$$$$$#
#-----+#
########

Edited by author 01.05.2011 00:06

Edited by author 01.05.2011 02:34

My method needs a plenty of memory to store information, although got a Memory Limit Exceeds, but it can give out a solution to all the hard data in discuss in less than 0.1s. however, I still found some data that make my program run very slow(up to 2s), and even can not provide a solution(the solution exists).

########
#.O....#
#####OO#
#.@$OO$#
#$O$O$O#
#OO$O$O#
#.$OOO.#
########


########
#.O.O..#
#####OO#
#.@$OO$#
#$O$O$O#
#OO$O$O#
#.$OO..#
########


########
#......#
#.OOO$@#
#.O$OO$#
#$O$O$O#
#O$$O$O#
#.$OOO.#
########


########
#......#
#.OOO$O#
#.@$OO$#
#$O$O$O#
#O$$O$O#
#.$OOO.#
########

can any one who passed this problem share some more outstanding ideas about how to optimize the algorithm?

 ######
##  . #
# * # #
# .$  #
#  #$##
## @ #
 #####

my personal favorites:
########
##.* $.#
#  * . #
#   *. #
## $.$ #
# $*$$$#
#..   @#
########

and next is hard only if you don't use any estimate func:
########
#.     #
#$ $ $ #
#@ $ $ #
#  $ $ #
#  ****#
#......#
########

Edited by author 17.08.2018 15:25