10274 - Fans and Gems

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

10274 - Fans and Gems

Post by Whinii F. » Wed Jan 28, 2004 7:58 pm

Hi! I'm solving this problem and confused about the sample input and output.

For the sample input given below,

Code: Select all

########
##   1##
##  2  #
#  1  ##
##2   ##
#   1@##
###   ##
#### ###
########
They have LURD (left, up, right, down) as the desired output. Two 2 s collide after LU and three 1 s disappear after RD.

but why DRU is not a valid output? Following is a simulation on DRU.

Code: Select all

########
##   1##
##  2  #
#  1  ##
##2   ##
#   1@##
###   ##
#### ###
########

After D
########
##    ##
##     #
#     ##
##    ##
# 2  1##
###12@##
####1###
########

After R: two 2 s disappear
########
##    ##
##     #
#     ##
##    ##
#    1##
###1 @##
####1###
########

After U: so we can remove all gems
########
## 111##
##   @ #
#     ##
##    ##
#     ##
###   ##
#### ###
########

I'm whole puzzled. Thanks in advance! :wink:

Regards,
JongMan @ Yonsei

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Jan 28, 2004 10:08 pm

After the two 2 disapper, the 1 moves one right (because the fans are still blowing). The fans stop blowing if nothing changes.
By the way, because the 1 moves one right, it will disappear together with the 1 below, so only one 1 is left and you can't find a solution any more

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Jan 31, 2004 10:38 am

Juz wanna ask, could we solve this problem with backtracking + B&B? Or is BFS the only way? (heard from a friend of mine)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Fri Feb 06, 2004 2:13 pm

Adrian: Yes, very true! I forgot to implement "keep blowing wind till there's no chages" feature. Now my program solves the example case correctly. Thanks!

Observer: It seems BFS is feasible (However it is a bit tricky to create lexicographically smallest output) . I used BFS and it runs fast.. (< 0.5sec) but painfully, I get WA. So what I'm saying, may be whole wrong. :wink:
JongMan @ Yonsei

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Feb 12, 2004 12:04 pm

I don't know hashing, so I just used DFS in my code.... And guess what, I got ACC in 0.5 sec!! :D

This is indeed a great problem~ and my solution looks long and ugly :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

10274 - Fans and Gems (Need I/O verification)

Post by txandi » Sun Feb 20, 2005 6:22 pm

Can anybody check this I/O??? I keep getting WA and I don't know why.

Code: Select all

20
5 14
##############
#@   1 3   1@#
#@#2#     #  #
#213  @13  @3#
##############

9 9
#########
#     3 #
# 3  @  #
#21  1@ #
#3     3#
# 2  # @#
#   #   #
## 3 2  #
#########

11 13
#############
# 2   2@ #  #
#2 3@ 1 @@ 2#
# 2    @2   #
#3 2 @ #  3 #
##    2#   2#
#3        1 #
##   #    3 #
#  #   1@# 1#
# 3#2  31 @##
#############

5 12
############
#3 @@ 2 1 3#
# 3 1#@ #  #
#      # 2 #
############

12 9
#########
#  12 #2#
#  #   1#
#      3#
#    2#1#
#1312#  #
# 2#    #
#      2#
###   1 #
#     23#
#@    @ #
#########

7 20
####################
#  ##     3#  1 23##
#3  @ 3 3          #
#1 3  1 #2  2    2 #
##   #      #1  1  #
# 2  #13@        21#
####################

11 7
#######
##   @#
# 2  @#
#  3#@#
#2# # #
# 3  2#
#    ##
# 3  ##
#3@  ##
# # 2 #
#######

7 15
###############
#  1 12     # #
#3  #23231 3  #
# 2 #     # 2 #
#   #  123 3 1#
# 2# 1  @1##23#
###############

5 9
#########
#  @1   #
#   3  ##
#1   31 #
#########

9 9
#########
# 1   1 #
#1   ####
# 2#  3 #
#  2   ##
#3    1 #
# 1     #
#  1@@  #
#########

10 7
#######
#1 1  #
#   @ #
##  1 #
#     #
#3#  ##
# # #1#
#   ###
#  1 3#
#######

7 11
###########
#    1#32##
#     2  3#
#@ @3   # #
#       2 #
#2  3   31#
###########

9 14
##############
#     2 12   #
# @          #
#1   #13 1@  #
#  #      #  #
#2# #   2 3  #
##  3 2   @@##
# 1        21#
##############

8 18
##################
####  # ##      3#
#21 #   1 @@  @ ##
#3     @# 2  2 23#
#  #1@ #      # 1#
# 2             3#
#3  @    #       #
##################

12 20
####################
#       2# # 2  1 3#
#1  @1      3 #    #
#@2@1#@   @3#2#  2 #
#   #  2           #
#3#1       @1      #
#  2 #     @  13   #
# 2    1##2@#   #23#
#21   # 13    2   ##
#  @      #       ##
# # 1@    #@ 231   #
####################

11 7
#######
###1@2#
# 1 3 #
# #   #
#  3@ #
#     #
#23# @#
#32   #
#2    #
#  32 #
#######

5 13
#############
#  # 21  @ 3#
##1#@ #  2 2#
#   3    1  #
#############

7 19
###################
#3  1#3 1  3  @#1 #
#2#  @@   @323 1# #
#  3     @  #     #
#  ##23   1#12  21#
# 1#       2#     #
###################

9 12
############
#3#23 2  ###
# 31   @  ##
#3  2#3 #3 #
#    2  3 @#
# 1   1  ###
#      2 2 #
# 1  #13  @#
############

9 17
#################
# 3 3  212 3 #32#
# 1    2  3 @  ##
#  1        1 1 #
##2 2##1  1#    #
#   @ 2 3   #3  #
#2  1   13      #
#@3  3 3 @ @ 3#@#
#################

My program gives

Code: Select all

RDLULRD
DRURDLDLURU
RLURULURDL
-1
RDLULURDLDRD
RDLDLURDRURD
LDRD
-1
-1
RDLDR
-1
LDRDLUL
RULDRDLDRUL
RDRULURDLD
RDLULRUL
DLUD
-1
LULDLURDRD
DLDRU
DURULDRU
If this I/O is correct, can anybody tell me some critical one?

Thanks!!

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Mon Feb 28, 2005 10:26 pm

I got AC now. The input above this is ok.
My (silly) mistake:
There is one line after each map, ignore them.
I assumed this line was empty, but I was wrong, it was full of garbage... I shoud have thought about this before wasting a lot of time debugging a correct program... In my opinion these kind of "tricky" inputs shoud be supressed from the judge.
Anyway it's AC now, I'm happy :D

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

10274 Fans and Gems

Post by LlatzerandToni » Sun Apr 23, 2006 1:52 pm

Hi!

We have a problem. Our output isn't correct for the online-judge. However, the answer seems correct. We don't know if it is just a problem of output writing. We have tried this input:
26
9 8
########
##...1##
##..2..#
#..1..##
##2...##
#...1@##
###...##
####.###
########

7 8
########
#212121#
#......#
#.#.#.##
#.#....#
#.....##
########
jdsnjcdsjasnbcanxbsxbcajhsxdb
4 4
####
#1.#
#@2#
####

5 5
#####
#1..#
##@@#
#1..#
#####

5 14
##############
#@...1.3...1@#
#@#2#.....#..#
#213..@13..@3#
##############
djsnfcjdsnjfsnjnsjn32j32j32j4n32jkn4jn2jn4kj32n432.4nj324n2jn42.32n432jn4324j2.432.42j3.4324j24j2.4j324j.4j32.4j32.4j32.4j242432j.4j2.4j32.4j32.4j2.4j32n4j32
9 9
#########
#.....3.#
#.3..@..#
#21..1@.#
#3.....3#
#.2..#.@#
#...#...#
##.3.2..#
#########

11 13
#############
#.2...2@.#..#
#2.3@.1.@@.2#
#.2....@2...#
#3.2.@.#..3.#
##....2#...2#
#3........1.#
##...#....3.#
#..#...1@#.1#
#.3#2..31.@##
#############

5 12
############
#3.@@.2.1.3#
#.3.1#@.#..#
#......#.2.#
############

12 9
#########
#..12.#2#
#..#...1#
#......3#
#....2#1#
#1312#..#
#.2#....#
#......2#
###...1.#
#.....23#
#@....@.#
#########

7 20
####################
#..##.....3#..1.23##
#3..@.3.3..........#
#1.3..1.#2..2....2.#
##...#......#1..1..#
#.2..#13@........21#
####################

11 7
#######
##...@#
#.2..@#
#..3#@#
#2#.#.#
#.3..2#
#....##
#.3..##
#3@..##
#.#.2.#
#######

7 15
###############
#..1.12.....#.#
#3..#23231.3..#
#.2.#.....#.2.#
#...#..123.3.1#
#.2#.1..@1##23#
###############

5 9
#########
#..@1...#
#...3..##
#1...31.#
#########

9 9
#########
#.1...1.#
#1...####
#.2#..3.#
#..2...##
#3....1.#
#.1.....#
#..1@@..#
#########

10 7
#######
#1.1..#
#...@.#
##..1.#
#.....#
#3#..##
#.#.#1#
#...###
#..1.3#
#######

7 11
###########
#....1#32##
#.....2..3#
#@.@3...#.#
#.......2.#
#2..3...31#
###########

9 14
##############
#.....2.12...#
#.@..........#
#1...#13.1@..#
#..#......#..#
#2#.#...2.3..#
##..3.2...@@##
#.1........21#
##############

8 18
##################
####..#.##......3#
#21.#...1.@@..@.##
#3.....@#.2..2.23#
#..#1@.#......#.1#
#.2.............3#
#3..@....#.......#
##################

12 20
####################
#.......2#.#.2..1.3#
#1..@1......3.#....#
#@2@1#@...@3#2#..2.#
#...#..2...........#
#3#1.......@1......#
#..2.#.....@..13...#
#.2....1##2@#...#23#
#21...#.13....2...##
#..@......#.......##
#.#.1@....#@.231...#
####################
.
11 7
#######
###1@2#
#.1.3.#
#.#...#
#..3@.#
#.....#
#23#.@#
#32...#
#2....#
#..32.#
#######
.
5 13
#############
#..#.21..@.3#
##1#@.#..2.2#
#...3....1..#
#############

7 19
###################
#3..1#3.1..3..@#1.#
#2#..@@...@323.1#.#
#..3.....@..#.....#
#..##23...1#12..21#
#.1#.......2#.....#
###################
.
9 12
############
#3#23.2..###
#.31...@..##
#3..2#3.#3.#
#....2..3.@#
#.1...1..###
#......2.2.#
#.1..#13..@#
############
.
9 17
#################
#.3.3..212.3.#32#
#.1....2..3.@..##
#..1........1.1.#
##2.2##1..1#....#
#...@.2.3...#3..#
#2..1...13......#
#@3..3.3.@.@.3#@#
#################

12 20
####################
#@@1232#3123123....#
#.....##....#......#
#1.#....#..........#
#.2......#.#.......#
#..3#..............#
#3..333.3.3.3.3....#
#@..#..@..3.3@.....#
#....#.##..........#
#.1.2.1..2.1#2.1.21#
#.3.3.3.3.3#3.3..13#
####################
vndsfjfndjnvfjdnvjv .dnfjvfdjnvfjdngjdffg.df.j4..3j32h432h4.3h32h4.j32hj32hj32.h4j32h
3 6
######
#1##1#
######
And got this output:
LURD
DL
-1
DRDLURD
RDLULRD
DRURDLDLURU
RLURULURDL
-1
RDLULURDLDRD
RDLDLURDRURD
LDRD
-1
-1
RDLDR
-1
LDRDLUL
RULDRDLDRUL
RDRULURDLD
RDLULRUL
DLUD
-1
ULURULDRDLRDLUL
DLDRU
RLUDRU
DLULULDRDRDL
-1
We don't exactly know wether we must put an endline at the last answer. We have tried both options with no results because we always get WA.
If anyone knows which could be our problem...it would be reallly great.
Thanks, have a nice problemsetday!!!!!!!!

PS:We have dots instead of spaces in our input but it was just to put this entry here in the forum(dont be lazy and get a replace in any editor to try the input).
Lol

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10274 - Fans and Gems

Post by brianfry713 » Tue May 01, 2012 10:53 pm

For your input:

Code: Select all

26
9 8
########
##   1##
##  2  #
#  1  ##
##2   ##
#   1@##
###   ##
#### ###
########

7 8
########
#212121#
#      #
# # # ##
# #    #
#     ##
########
jdsnjcdsjasnbcanxbsxbcajhsxdb
4 4
####
#1 #
#@2#
####

5 5
#####
#1  #
##@@#
#1  #
#####

5 14
##############
#@   1 3   1@#
#@#2#     #  #
#213  @13  @3#
##############
djsnfcjdsnjfsnjnsjn32j32j32j4n32jkn4jn2jn4kj32n432 4nj324n2jn42 32n432jn4324j2 432 42j3 4324j24j2 4j324j 4j32 4j32 4j32 4j242432j 4j2 4j32 4j32 4j2 4j32n4j32
9 9
#########
#     3 #
# 3  @  #
#21  1@ #
#3     3#
# 2  # @#
#   #   #
## 3 2  #
#########

11 13
#############
# 2   2@ #  #
#2 3@ 1 @@ 2#
# 2    @2   #
#3 2 @ #  3 #
##    2#   2#
#3        1 #
##   #    3 #
#  #   1@# 1#
# 3#2  31 @##
#############

5 12
############
#3 @@ 2 1 3#
# 3 1#@ #  #
#      # 2 #
############

12 9
#########
#  12 #2#
#  #   1#
#      3#
#    2#1#
#1312#  #
# 2#    #
#      2#
###   1 #
#     23#
#@    @ #
#########

7 20
####################
#  ##     3#  1 23##
#3  @ 3 3          #
#1 3  1 #2  2    2 #
##   #      #1  1  #
# 2  #13@        21#
####################

11 7
#######
##   @#
# 2  @#
#  3#@#
#2# # #
# 3  2#
#    ##
# 3  ##
#3@  ##
# # 2 #
#######

7 15
###############
#  1 12     # #
#3  #23231 3  #
# 2 #     # 2 #
#   #  123 3 1#
# 2# 1  @1##23#
###############

5 9
#########
#  @1   #
#   3  ##
#1   31 #
#########

9 9
#########
# 1   1 #
#1   ####
# 2#  3 #
#  2   ##
#3    1 #
# 1     #
#  1@@  #
#########

10 7
#######
#1 1  #
#   @ #
##  1 #
#     #
#3#  ##
# # #1#
#   ###
#  1 3#
#######

7 11
###########
#    1#32##
#     2  3#
#@ @3   # #
#       2 #
#2  3   31#
###########

9 14
##############
#     2 12   #
# @          #
#1   #13 1@  #
#  #      #  #
#2# #   2 3  #
##  3 2   @@##
# 1        21#
##############

8 18
##################
####  # ##      3#
#21 #   1 @@  @ ##
#3     @# 2  2 23#
#  #1@ #      # 1#
# 2             3#
#3  @    #       #
##################

12 20
####################
#       2# # 2  1 3#
#1  @1      3 #    #
#@2@1#@   @3#2#  2 #
#   #  2           #
#3#1       @1      #
#  2 #     @  13   #
# 2    1##2@#   #23#
#21   # 13    2   ##
#  @      #       ##
# # 1@    #@ 231   #
####################
 
11 7
#######
###1@2#
# 1 3 #
# #   #
#  3@ #
#     #
#23# @#
#32   #
#2    #
#  32 #
#######
 
5 13
#############
#  # 21  @ 3#
##1#@ #  2 2#
#   3    1  #
#############

7 19
###################
#3  1#3 1  3  @#1 #
#2#  @@   @323 1# #
#  3     @  #     #
#  ##23   1#12  21#
# 1#       2#     #
###################
 
9 12
############
#3#23 2  ###
# 31   @  ##
#3  2#3 #3 #
#    2  3 @#
# 1   1  ###
#      2 2 #
# 1  #13  @#
############
 
9 17
#################
# 3 3  212 3 #32#
# 1    2  3 @  ##
#  1        1 1 #
##2 2##1  1#    #
#   @ 2 3   #3  #
#2  1   13      #
#@3  3 3 @ @ 3#@#
#################

12 20
####################
#@@1232#3123123    #
#     ##    #      #
#1 #    #          #
# 2      # #       #
#  3#              #
#3  333 3 3 3 3    #
#@  #  @  3 3@     #
#    # ##          #
# 1 2 1  2 1#2 1 21#
# 3 3 3 3 3#3 3  13#
####################
vndsfjfndjnvfjdnvjv  dnfjvfdjnvfjdngjdffg df j4  3j32h432h4 3h32h4 j32hj32hj32 h4j32h
3 6
######
#1##1#
######
My AC code gives:

Code: Select all

LURD
DL
-1
DRDLURD
RDLULRD
DRURDLDLURU
RLURULURDL
-1
RDLULURDLDRD
RDLDLURDRURD
LDRD
-1
-1
RDLDR
-1
LDRDLUL
RULDRDLDRUL
RDRULURDLD
RDLULRUL
DLUD
-1
LULDLURDRD
DLDRU
DURULDRU
URLDRDLDRDU
-1
My DFS was too slow but BFS works well. Yes, there should be a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”