In this HackerEarth Disk tower problem solution Your task is to construct a tower in N days by following these conditions:
- Every day you are provided with one disk of distinct size.
- The disk with larger sizes should be placed at the bottom of the tower.
- The disk with smaller sizes should be placed at the top of the tower.
The order in which the tower must be constructed is as follows:
- You cannot put a new disk on the top of the tower until all the larger disks that are given to you get placed.
Print N lines denoting the disk sizes that can be put on the tower on an ith day.
HackerEarth Disk tower problem solution.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.io.InputStream;
public class Main {
public static void main(String[] ARGS) {
new Thread(null, new Runnable() {
public void run() {
new Main().solve();
}
}, "1", 1 << 26).start();
}
void solve() {
InputStream IS = System.in;
OutputStream OS = System.out;
ScanReader in = new ScanReader(IS);
PrintWriter out = new PrintWriter(OS);
DiskTower disktower = new DiskTower();
disktower.solve(1, in, out);
out.close();
}
static class DiskTower {
public void solve(int testNumber, ScanReader in, PrintWriter out) {
int n = in.scanInt();
int current_need = n;
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < n; i++) {
int x = in.scanInt();
if (current_need == x) {
out.print(x + " ");
current_need--;
while (!queue.isEmpty() && current_need == queue.peek()) {
out.print(queue.poll() + " ");
current_need--;
}
} else {
queue.add(x);
}
out.println();
}
}
}
static class ScanReader {
private byte[] buf = new byte[4 * 1024];
private int index;
private BufferedInputStream in;
private int Total_Char;
public ScanReader(InputStream inputStream) {
in = new BufferedInputStream(inputStream);
}
private int scan() {
if (index >= Total_Char) {
index = 0;
try {
Total_Char = in.read(buf);
} catch (Exception e) {
e.printStackTrace();
}
if (Total_Char <= 0) return -1;
}
return buf[index++];
}
public int scanInt() {
int integer = 0;
int n = scan();
while (isWhiteSpace(n)) n = scan();
int neg = 1;
if (n == '-') {
neg = -1;
n = scan();
}
while (!isWhiteSpace(n)) {
if (n >= '0' && n <= '9') {
integer *= 10;
integer += n - '0';
n = scan();
}
}
return neg * integer;
}
private boolean isWhiteSpace(int n) {
if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
else return false;
}
}
}
Second solution
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > SolveTower (int N, vector<int> a) {
// Write your code here
vector<vector<int> > ans;
int done = N;
priority_queue<int> pq;
for(auto x: a){
pq.push(x);
vector<int> aux;
while(!pq.empty() && pq.top() == done){
aux.push_back(done);
pq.pop();
done--;
}
ans.push_back(aux);
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
assert(a.size() == N);
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
assert(1 <= N && N <= 1e6);
vector<int> a(N);
for(int i_a = 0; i_a < N; i_a++)
{
cin >> a[i_a];
}
vector<vector<int> > out_;
out_ = SolveTower(N, a);
for(int i = 0; i < out_.size(); i++){
for(int j = 0; j < out_[i].size(); j++){
cout << out_[i][j] << " ";
}
cout << "\n";
}
}
0 Comments