Prob.4 of NOIP 2008 (Junior) *Solution*

酱油 posted @ Sun, 16 Aug 2015 17:02:50 +0800 in OI life with tags Solution , 1311 readers

An Ad Hoc problem? Maybe... It was five years ago that I know the problem for the first time, but I've just solved the problem RECENTLY!

"Sky Gate":http://www.luogu.org/problem/show?pid=1058

Print a graph of cubes.
There is an area of n×m, and every point has its height a[i][j] (also the number of cubes on that point).
Every cube is just like this: 
..+---+
./   /|
+---+ |
|   | +
|   |/.
+---+..
"." means blank, 
"+" means a vertex, 
"-" means horizontal lines, 
"|" means vertical lines, 
" " means the plane of the cube
So if n=1, m=1, a[1][1]=2, you should print like this:
..+---+
./   /|
+---+ |
|   | +
|   |/|
+---+ |
|   | +
|   |/.
+---+..
If n=1, m=2, a[1][1]=a[1][2]=1, you should print like this:
..+---+---+
./   /   /|
+---+---+ | 
|   |   | +
|   |   |/.
+---+---+..
If n=2, m=1, a[1][1]=a[2][1]=1, you should print like this:
....+---+
.../   /|
..+---+ |
./   /| +
+---+ |/.
|   | +..
|   |/...
+---+....
Input:
n m
a[1][1] a[1][2] ... a[1][m]
a[2][1] a[2][2] ... a[2][m]
...
a[n][1] a[n][2] ... a[n][m]
Output:
The graph required
Sample Input:
3 4
2 2 1 2
2 2 1 1
3 2 1 2
Sample Output:
......+---+---+...+---+
..+---+  /   /|../   /|
./   /|-+---+ |.+---+ |
+---+ |/   /| +-|   | +
|   | +---+ |/+---+ |/|
|   |/   /| +/   /|-+ |
+---+---+ |/+---+ |/| +
|   |   | +-|   | + |/.
|   |   |/  |   |-| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......
Explanations:
Just a graph we see in 2 dimensions facing the 3-dimension, right?
For all 10 testcases: 1<=n,m<=50; 1<=a[i][j]<=100 (1<=i<=n, 1<=j<=m)

 

It's the last problem in NOIP 2008 Junior, and it can be very complexed to solve. (I've already told you in advance that I am always a WEAK DISH!) But we could think like this.

Since n, m and a[i][j] are really restricted, let's make a chart then.

So the first step is to figure out the size of the graph.

When making the chart, we could draw only one cube at a time. And we could draw at a point, and slowly go upwards on each grid, which exists in the "real world".

Start from the first line, print from left to right, and the cubes nearer to us will ignore things after them.

So the only difficulty is just about calculating the formula of printing positions...

Then we could have a try!

    #include <iostream>  
    #include <cstdio>  
    #include <cstdlib>  
    #include <cstring>  
    #include <cmath>  
    #include <algorithm>  
    #include <ctime>  
    #define DONS 1010  
    using namespace std;  
    int n,i,j,k,sizex,sizey,m,a[DONS][DONS],t[DONS],tt[DONS];  
    char graph[DONS][DONS];  
    void draw(int xx,int yy)  //print a cube while point (xx,yy) is its left vertex at the bottom
    {  
        graph[xx][yy]=graph[xx][yy+4]=graph[xx-2][yy+6]=graph[xx-3][yy]=graph[xx-3][yy+4]=graph[xx-5][yy+2]=graph[xx-5][yy+6]='+';  
        graph[xx][yy+1]=graph[xx][yy+2]=graph[xx][yy+3]=graph[xx-3][yy+1]=graph[xx-3][yy+2]=graph[xx-3][yy+3]=graph[xx-5][yy+3]=graph[xx-5][yy+4]=graph[xx-5][yy+5]='-';  
        graph[xx-1][yy]=graph[xx-1][yy+4]=graph[xx-2][yy]=graph[xx-2][yy+4]=graph[xx-3][yy+6]=graph[xx-4][yy+6]='|';  
        graph[xx-1][yy+5]=graph[xx-4][yy+5]=graph[xx-4][yy+1]='/';  
        graph[xx-1][yy+1]=graph[xx-1][yy+2]=graph[xx-1][yy+3]=graph[xx-2][yy+1]=graph[xx-2][yy+2]=graph[xx-2][yy+3]=graph[xx-4][yy+2]=graph[xx-4][yy+3]=graph[xx-4][yy+4]=graph[xx-2][yy+5]=graph[xx-3][yy+5]=' ';  
    }  
    int main()  
    {  
        scanf("%d%d",&n,&m);  
        sizey=(n<<1)+1+(m<<2);  
        for(i=1;i<=n;i++)  
        {  
            for(j=1;j<=m;j++){scanf("%d",&a[i][j]);tt[i]=max(tt[i],a[i][j]);t[i]=max(a[i][j]*3+1+(n-i+1)*2,t[i]);}  
            sizex=max(sizex,t[i]);  
        }  
        for(i=1;i<=sizex;i++)for(j=1;j<=sizey;j++)graph[i][j]='.';//initialization
        for(i=1;i<=n;i++)  
            for(j=1;j<=m;j++)  
                for(k=1;k<=a[i][j];k++)  
                draw(sizex-(n-i)*2-(k-1)*3,(n-i)*2+(j-1)*4+1);//please figure out the formula by your self  
        for(i=1;i<=sizex;i++){for(j=1;j<=sizey;j++)printf("%c",graph[i][j]);puts("");}      
        return 0;  
    }  

 

And that's it, not THAT difficult.

Of course there are more ways to solve the problem. Here I used an algorithm with time complexity O(n×m×max(a[i][j])).

 

If you have a better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)

 

 

 

 

 

 

 

 

Avatar_small
orz hhw said:
Fri, 21 Aug 2015 21:07:08 +0800

%%%It's so hard and I can't solve it.

Avatar_small
Best Hosting Review said:
Tue, 06 Jul 2021 19:35:37 +0800

Amazing article. It is fascinating to read. I truly prefer to peruse a particularly decent article. Thank you! keep having a good time.

Avatar_small
Bangalore Escorts said:
Wed, 03 Nov 2021 14:56:11 +0800

I'm happy to be here. I truly like this superb post that you have accommodated us. I guarantee this would be advantageous for the vast majority of individuals.

Avatar_small
Bangalore Escorts Se said:
Tue, 18 Jan 2022 17:36:41 +0800

I high like this post. It's difficult to come by the great from the awful now and again, yet I think you've nailed it! would you mind refreshing your blog with more data?

Avatar_small
AAA said:
Tue, 01 Feb 2022 21:50:48 +0800

Wow, cool post. I’d like to write like this too – taking time and real hard work to make a great article… but I put things off too much and never seem to get started. Thanks though. 메이저사이트

Avatar_small
AAA said:
Fri, 25 Feb 2022 19:19:17 +0800

I’m impressed, I have to admit. Actually rarely will i encounter a weblog that’s both educative and entertaining, and without a doubt, you could have hit the nail about the head. Your notion is outstanding; the problem is an issue that not enough people are speaking intelligently about. I am happy that we stumbled across this at my search for some thing relating to this. 소액결제현금화

Avatar_small
AAA said:
Tue, 01 Mar 2022 18:07:45 +0800

You produced some decent points there. I looked on the internet with the problem and discovered most individuals go in addition to along with your website. 메이저사이트

Avatar_small
AAA said:
Sun, 27 Mar 2022 00:37:14 +0800

Your blog has the same post as another author but i like your better.;~,*. Smooth Residential Transition & Adjustment

Avatar_small
AAA said:
Thu, 26 May 2022 00:11:37 +0800

This kind of lovely blog you’ve, glad I found it!? 토토사이트

Avatar_small
AAA said:
Sat, 04 Jun 2022 05:03:01 +0800

Heya! I just wanted to ask if you ever have any issues with hackers? My last blog (wordpress) was hacked and I ended up losing a few months of hard work due to no back up. Do you have any methods to protect against hackers? 麥克風 I enjoy you because of all of your efforts on this website. Kim take interest in getting into investigations and it is easy to see why. We know all concerning the dynamic mode you produce priceless ideas by means of the web blog and as well as recommend participation from some other people on this area then our own daughter is certainly becoming educated a lot of things. Take pleasure in the remaining portion of the year. You’re carrying out a splendid job. 攝影器材

Avatar_small
AAA said:
Mon, 13 Jun 2022 04:16:13 +0800

You made some decent points there. I looked on the net with the problem and located most people should go along with with the web site. 電腦回收價格

Avatar_small
Anamika said:
Tue, 28 Jun 2022 16:19:00 +0800
A particularly tangling page I saw this kind of weblog. I like your pearls. I like your chance out additionally.  Independent Escorts in Bangalore Thankful for sharing.
 
Avatar_small
AP 10th Biology Ques said:
Wed, 14 Sep 2022 17:20:27 +0800

Candidates can download 10th class biology subject sample papers pdf and key topics with assignments in all exam formats of the board like SA-1, SA-2, FA-1, FA-2, FA-3 and FA-4.Telugu Medium, AP 10th Biology Question PaperEnglish Medium and Urdu Medium Students of the State who studying Class 10th Grade can download the AP SSC Biology Model Papers 2023 for theory, objective and bit questions to Self Practice.Telugu Medium, English Medium and Urdu Medium Students of the State who studying Class 10th Grade can download the AP SSC Biology Model Papers 2023 for theory, objective and bit questions to Self Practice.

Avatar_small
meidir said:
Sun, 02 Oct 2022 21:29:59 +0800

Thanks for helping out, superb info . iPhone 14

Avatar_small
meidir said:
Wed, 02 Nov 2022 00:29:00 +0800

I do believe all of the ideas you’ve introduced on your post. They are really convincing and can definitely work. Still, the posts are too brief for newbies. Could you please lengthen them a bit from subsequent time? Thank you for the post. 카지노사이트

Avatar_small
Call Girls in Luckno said:
Mon, 07 Nov 2022 18:15:11 +0800

The experience for the people here Call Girl in Lucknow the things will be served here with the joy out here.

Avatar_small
Chennai Call Girls said:
Mon, 07 Nov 2022 18:18:48 +0800

People have been working out with the things here that have been coming out here with the <a href="http://www.callgirlsdelhincr.in/call-girls-in-chennai/">Call Girl in Chennai</a> and explore all the details here with the fantastic things.

Avatar_small
meidir said:
Sat, 19 Nov 2022 00:27:23 +0800

Have you ever considered about including a little bit more than just your articles? I mean, what you say is fundamental and all. Nevertheless just imagine if you added some great graphics or videos to give your posts more, “pop”! Your content is excellent but with images and clips, this site could certainly be one of the greatest in its field. Great blog! 온라인카지노

Avatar_small
Bangalore Escorts said:
Sat, 17 Dec 2022 13:11:22 +0800

Shocking! Your substance is especially essential for us to give such a bewildering article.

Avatar_small
shivani02 said:
Wed, 19 Apr 2023 14:35:15 +0800
If you’re interested in bringing companionship and sensuality into your life, it’s time to think about hiring an escort. These beautiful people are ready to give you all the attention you desire.

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter