Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1533
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1533
Detective Watson
By Cristhian Bonilha, UTFPR Brazil
Timelimit: 1
John Watson, after years working aside Sherlock Holmes, never understood how he was able to guess who was the killer so easily. On a certain night, however, Sherlock drunk so much that he told John what the secret was.
“Elementary dear Watson”, said Sherlock Holmes. “It is never the most suspicious, but the second most suspicious”. After he got the secret, John decided to solve a crime by his own, just to test if what Sherlock said made sense or it was just drunk talk.
Given a list with N integers, representing how much each person is suspect, help John Watson to decide who is the killer, according to the mentioned method.
Input
There will be several test cases. Each test case starts with an integer N (2 ≤ N ≤ 1000), representing the number of suspects.
Following there will be N distinct integers, where the i-th integer, for each 1 ≤ i ≤ N, represents how much the i-th person is suspect, given John Watson's opinion. Be V the value of i-th integer, 1 ≤ V ≤ 10000.
The last test case is indicated when N = 0, which should not be processed.
Output
For each test case print one line, containing one integer, representing the index of the killer, according to the mentioned method.
Sample Input | Sample Output |
3 |
1 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int main(void) {
int n, i, j, s, x, a;
int e[1000], f[1000];
while (scanf("%d", &n) == 1 && n != 0) {
for (i = 0; i < n; ++i) {
scanf("%d", &e[i]);
f[i] = e[i];
}
for (i = 0; i < n-1; ++i)
for (j = i+1; j < n; ++j)
if (f[i] > f[j]) {
x = f[i];
f[i] = f[j];
f[j] = x;
}
s = f[n-2];
for (i = 0; i < n; ++i)
if (s == e[i])
a = i + 1;
printf("%d\n", a);
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
3 5 2
5
1 15 3 5 2
0
Output
4
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
using namespace std;
int main(void) {
int n, i, j, s, x, a;
int e[1000], f[1000];
while (cin >> n && n != 0) {
for (i = 0; i < n; ++i) {
cin >> e[i];
f[i] = e[i];
}
for (i = 0; i < n-1; ++i)
for (j = i+1; j < n; ++j)
if (f[i] > f[j]) {
x = f[i];
f[i] = f[j];
f[j] = x;
}
s = f[n-2];
for (i = 0; i < n; ++i)
if (s == e[i])
a = i + 1;
cout << a << endl;
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
3 5 2
5
1 15 3 5 2
0
Output
4
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
static Reader in = new Reader(System.in);
static Writer out = new Writer(System.out);
public static void main(String[] args) throws IOException {
int N, f, s, fi, si, c;
while (true) {
N = in.nextInt();
if (N == 0) {
break;
}
f = 0;
s = 0;
fi = 0;
si = 0;
for (int i = 0; i < N; i++) {
c = in.nextInt();
if (c > f) {
s = f;
si = fi;
f = c;
fi = i;
} else if (c > s) {
s = c;
si = i;
}
}
out.println(si + 1);
}
in.close();
out.flush();
out.close();
}
////////////////////////////////////////////////////////////////////////////
///////////////////////////// INPUT / OUTPUT /////////////////////////////
////////////////////////////////////////////////////////////////////////////
static class Reader implements Closeable {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public Reader(InputStream input) {
reader = new BufferedReader(
new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
private StringTokenizer getTokenizer() throws IOException {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
String line = nextLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer;
}
public boolean hasNext() throws IOException {
return getTokenizer() != null;
}
public String next() throws IOException {
return hasNext() ? tokenizer.nextToken() : null;
}
public String nextLine() throws IOException {
tokenizer = null;
return reader.readLine();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public String[] nextStringArray(int size) throws IOException {
String[] array = new String[size];
for (int i = 0; i < size; i++) {
array[i] = next();
}
return array;
}
public int[] nextIntArray(int size) throws IOException {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = nextInt();
}
return array;
}
public long[] nextLongArray(int size) throws IOException {
long[] array = new long[size];
for (int i = 0; i < size; i++) {
array[i] = nextLong();
}
return array;
}
public double[] nextDoubleArray(int size) throws IOException {
double[] array = new double[size];
for (int i = 0; i < size; i++) {
array[i] = nextDouble();
}
return array;
}
@Override
public void close() throws IOException {
tokenizer = null;
reader.close();
}
}
static class Writer implements Closeable, Flushable {
private final PrintWriter writer;
public Writer(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
@Override
public void close() {
writer.close();
}
@Override
public void flush() {
writer.flush();
}
}
}
Copy The Code &
Try With Live Editor
Input
3 5 2
5
1 15 3 5 2
0
Output
4
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", "utf8").split("\n")
function main() {
const responses = []
for (let index = 0; index < input.length; index += 2) {
const numElements = input[index]
if (numElements == "0") break
const suspectList = input[index + 1].split(" ", +numElements)
const [, secondIndex] = nextBiggestNum(suspectList)
responses.push(secondIndex + 1)
}
console.log(responses.join("\n"))
}
main()
function nextBiggestNum(arr) {
let [maxIndex, prevIndex] = new Array(2).fill(-1)
let [max, prev] = new Array(2).fill(Number.NEGATIVE_INFINITY)
for (let index = 0; index < arr.length; index++) {
const value = Number(arr[index])
if (value > max) {
[prev, max] = [max, value];
[prevIndex, maxIndex] = [maxIndex, index]
} else if (value < max && value > prev) {
[prev, prevIndex] = [value, index]
}
}
return [prev, prevIndex]
}
Copy The Code &
Try With Live Editor
Input
3 5 2
5
1 15 3 5 2
0
Output
4
#5 Code Example with Python Programming
Code -
Python Programming
while True:
n = int(input())
if n == 0: break
e = [int(x) for x in str(input()).split()]
f = sorted(e)
s = f[len(f) - 2]
for i in range(len(e)):
if s == e[i]:
a = i + 1
print(a)
Copy The Code &
Try With Live Editor
Input
3 5 2
5
1 15 3 5 2
0
Output
4