Prob.4 of NOIP 2008 (Junior) *Solution*
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.)
Fri, 21 Aug 2015 21:07:08 +0800
%%%It's so hard and I can't solve it.
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.
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.
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?
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. 메이저사이트
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. 소액결제현금화
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. 메이저사이트
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
Thu, 26 May 2022 00:11:37 +0800
This kind of lovely blog you’ve, glad I found it!? 토토사이트
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. 攝影器材
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. 電腦回收價格
Tue, 28 Jun 2022 16:19:00 +0800
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.
Sun, 02 Oct 2022 21:29:59 +0800
Thanks for helping out, superb info . iPhone 14
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. 카지노사이트
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.
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.
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! 온라인카지노
Sat, 17 Dec 2022 13:11:22 +0800
Shocking! Your substance is especially essential for us to give such a bewildering article.
Wed, 19 Apr 2023 14:35:15 +0800
Sun, 23 Apr 2023 10:33:59 +0800
Thanks you!
Xây nhà trọn gói tại tphcm Thi cong alu Giá thi công nhà khung thép Sua nha gia re Giam sat cong trinh Xay nha gia re WinconsMon, 07 Oct 2024 04:57:26 +0800
I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much.When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your. Influencers Gine Wuld
Mon, 07 Oct 2024 05:02:17 +0800
I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article.A very awesome blog post. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. Newzire
Mon, 07 Oct 2024 05:05:14 +0800
Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place..Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign. Vital Mag
Mon, 07 Oct 2024 05:07:32 +0800
I learn some new stuff from it too, thanks for sharing your information.You made such an interesting piece to read, giving every subject enlightenment for us to gain knowledge. Thanks for sharing the such information with us to read this... Usefullideas
Mon, 07 Oct 2024 05:09:03 +0800
Interesting post. I Have Been wondering about this issue, so thanks for posting. Pretty cool post.It 's really very nice and Useful post.ThanksThis is my first time visit here. From the tons of comments on your articles,I guess I am not only one having all the enjoyment right here! Web Ronix
Mon, 07 Oct 2024 20:51:14 +0800
Please continue this great work and I look forward to more of your awesome blog posts.You know your projects stand out of the herd. There is something special about them.This was really an interesting topic and I kinda agree with what you have mentioned here!I love seeing blog that understand the value of providing a quality resource for free.Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject. Techy Tips
Mon, 07 Oct 2024 20:52:16 +0800
i love reading this article so beautiful!!great job!Great Information sharing .. I am very happy to read this article .. thanks for giving us go through info.Fantastic nice. I appreciate this post. Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!..I appreciate everything you have added to my knowledge base.Admiring the time and effort you put into your blog and detailed information you offer.Thanks. TechnikerForsche
Mon, 07 Oct 2024 21:55:34 +0800
When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your.Interesting topic for a blog. I have been searching the Internet for fun and came upon your website.I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article...Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject.i love reading this article so beautiful!!great job! NewsVeteran
Tue, 08 Oct 2024 14:11:22 +0800
When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your.Interesting topic for a blog. I have been searching the Internet for fun and came upon your website.I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article...Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject.i love reading this article so beautiful!!great job! NewsVeteran
Wed, 13 Nov 2024 03:16:08 +0800
I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. Vibergirls