In this HackerEarth Fun Game Capillary problem solution A and B are playing a game. In this game, both of them are initially provided with a list of n numbers. (Both have the same list but their own copy).
Now, they both have a different strategy to play the game. A picks the element from the start of his list. B picks from the end of his list.
You need to generate the result in form of an output list.
Method to be followed at each step to build the output list is:
- If the number picked by A is bigger than B then this step's output is 1. B removes the number that was picked from their list.
- If the number picked by A is smaller than B then this step's output is 2. A removes the number that was picked from their list.
- If both have the same number then this step's output is 0. Both A and B remove the number that was picked from their list.
- This game ends when at least one of them has no more elements to be picked i.e. when the list gets empty.
Output the built output list.
HackerEarth Fun Game <Capillary> problem solution.
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
import static java.lang.Math.*;
import java.util.concurrent.ThreadLocalRandom;
public class Sol implements Runnable {
long mod = (long)1e9 + 7;
void solve(InputReader in, PrintWriter w) {
int n = in.nextInt();
Queue<Integer> A = new LinkedList<>();
Stack<Integer> B = new Stack<>();
for(int i=0;i<n;i++) {
int x = in.nextInt();
A.add(x);
B.push(x);
}
ArrayList<Integer> res = new ArrayList<>();
while(!B.isEmpty() && !A.isEmpty()) {
int a = A.peek();
int b = B.peek();
if(a > b) {
res.add(1);
B.pop();
}
else if(a < b) {
res.add(2);
A.poll();
}
else {
res.add(0);
A.poll();
B.pop();
}
}
w.print(res.get(0));
for(int i=1;i<res.size();i++) w.print(" "+res.get(i));
}
void init() throws Exception {
//Scanner in;
InputReader in;
PrintWriter w;
boolean online = false;
String common_in_fileName = "\\in";
String common_out_fileName = "\\out";
int test_files = 0;
for (int file_no = 0; file_no <= test_files; file_no++) {
String x = "" + file_no;
if (x.length() == 1) x = "0" + x;
String in_fileName = common_in_fileName + "" + x;
String out_fileName = common_out_fileName + "" + x;
if (online) {
//in = new Scanner(new File(in_fileName + ".txt"));
in = new InputReader(new FileInputStream(new File(in_fileName + ".txt")));
w = new PrintWriter(new FileWriter(out_fileName + ".txt"));
} else {
//in = new Scanner(System.in);
in = new InputReader(System.in);
w = new PrintWriter(System.out);
}
solve(in, w);
w.close();
}
}
public void run() {
try {
init();
} catch (Exception e) {
System.out.println(e);
e.printStackTrace();
}
}
public static void main(String args[]) throws Exception {
new Thread(null, new Sol(), "Sol", 1 << 28).start();
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public String nextLine() {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public double nextDouble() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, nextInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, nextInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
Second solution
#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[1000001];
int main()
{
ios_base::sync_with_stdio(0);
int n;
assert(cin >> n);
for(int i = 1; i <= n; i++){
assert(cin >> a[i]);
}
vector<int> ans;
int p1 = 1 , p2 = n;
while(p1 <= n && p2 >= 1){
if(a[p1] < a[p2]){
ans.push_back(2);
++p1;
}
else if(a[p1] > a[p2]){
ans.push_back(1);
--p2;
}
else{
ans.push_back(0);
++p1;
--p2;
}
}
for(int i: ans)
cout << i << " ";
}
0 Comments