Трое студентов, пятикурсник, третьекурсник и первокурсник, живут в одной комнате общежития и любят участвовать в соревнованиях по программированию по правилам ACM. У каждого из них свой подход к решению задач. Пятикурсник решает все задачи строго по порядку - сначала первую, затем вторую, и так до последней. Третьекурсник решает задачи строго в обратном порядке – сначала последнюю, затем предпоследнюю, и так до первой. А первокурсник сначала решает самую простую задачу, затем – самую простую из оставшихся задач, и так до самой сложной. Сложность задачи определяется временем, необходимым для её решения. Для решения одной и той же задачи наши студенты тратят одинаковое количество времени.
Ваша задача – по описанию соревнований по программированию определить, кто из студентов победит. Напомним, что по правилам ACM побеждает участник, за 300 минут решивший больше всего задач, а при равенстве количества задач – набравший меньше штрафного времени.
Наши студенты – очень сильные программисты, и при решении задач они не делают неправильных попыток. Поэтому за задачу начисляется штраф в размере количества минут от начала соревнования до её посылки на проверку. Если же и количество штрафного времени совпадает – то студент со старшего курса уступает победу студенту с младшего курса.
Формат ввода
Входной файл input.txt содержит натуральное число N (N ≤ 10) – количество задач. Во второй строке записаны N натуральных чисел – количество минут, необходимое для решения каждой задачи. Время решения задачи не превосходит 300 минут.
Формат вывода
В выходной файл output.txt выведите номер курса студента, одержавшего победу в олимпиаде.
Примеры
Ввод
3
40 30 60
Вывод 1
______________
Ввод
4
10 20 30 40
Вывод 1
______________
Пояснение к примерам
В первом тесте пятикурсник набрал 240 штрафных минут (40 + 70 + 130), третьекурсник – 280 (60 + 90 + 130), первокурсник - 230 минут (30 + 70 + 130).
Во втором тесте третьекурсник набрал 300 минут, а первокурсник и пятикурсник – 200 минут. Но пятикурсник уступил первокурснику.
Пояснение к решению
Задачу можно было решить гораздо проще - вывести 1 в файл output.txt, т.к. первокурсник всегда побеждает при таких условиях.
import java.util.*;
import java.io.*;
public class Contest {
private static ArrayList<String> list = new ArrayList<>(); // Коллекция для построчного считывания данных
private static ArrayList<Integer> time = new ArrayList<>(); // Коллекция для хранения времени на решение задач
private static int taskCountOne = 0, taskCountThree = 0, taskCountFive = 0; // Количество решенных задач
private static int mistakeCountOne = 0, mistakeCountThree = 0, mistakeCountFive = 0; // Количество штрафного времени по каждому заданию
private static int mistakeAllOne = 0, mistakeAllThree = 0, mistakeAllFive = 0; // Количество штрафного времени по каждому заданию
private static int maxTime = 300; // Максимальная продолжительность соревнований
private static void oneKurs(){
Collections.sort(time);
int one = 0;
for (Integer aTime : time) { // Расчет по первокурснику
if (one >= 0) {
one = maxTime - aTime;
maxTime = one;
taskCountOne++;
mistakeCountOne += aTime;
mistakeAllOne += mistakeCountOne;
} else {
break;
}
}
}
private static void threeKurs(){
Collections.reverse(time);
int three = 0;
for (Integer aTime : time) { // Расчет по третьекурснику
if (three >= 0) {
three = maxTime - aTime;
maxTime = three;
taskCountThree++;
mistakeCountThree += aTime;
mistakeAllThree += mistakeCountThree;
} else {
break;
}
}
}
private static void fiveKurs(){
int five = 0;
for (Integer aTime : time) { // Расчет по пятикурснику
if (five >= 0) {
five = maxTime - aTime;
maxTime = five;
taskCountFive++;
mistakeCountFive += aTime;
mistakeAllFive += mistakeCountFive;
} else {
break;
}
}
}
private static void time(){
maxTime = 300;
}
public static void main(String[] args) throws IOException {
String str;
FileReader file = new FileReader("input.txt"); // Считывание данных из файла
Scanner sc = new Scanner(file);
while(sc.hasNextLine()){
str = sc.nextLine();
list.add(str);
}
StringTokenizer st = new StringTokenizer(list.get(1), " ");
while(st.hasMoreTokens()){
time.add(Integer.valueOf(st.nextToken()));
}
fiveKurs();
time();
threeKurs();
time();
oneKurs();
// Определение победителя
String winner = (taskCountOne > taskCountThree && taskCountOne > taskCountFive) ? "1" :
(taskCountThree > taskCountOne && taskCountThree > taskCountFive) ? "3" : "5";
if(taskCountOne == taskCountThree && taskCountOne > taskCountFive){
winner = (mistakeAllOne == mistakeAllThree) ? "1" :
(mistakeAllOne > mistakeAllThree) ? "3" : "1";
}else if(taskCountOne == taskCountFive && taskCountOne > taskCountThree){
winner = (mistakeAllOne == mistakeAllFive) ? "1" :
(mistakeAllOne > mistakeAllFive) ? "5" : "1";
}else if(taskCountThree == taskCountFive && taskCountThree > taskCountOne){
winner = (mistakeAllThree == mistakeAllFive) ? "3" :
(mistakeAllThree > mistakeAllFive) ? "5" : "3";
}else{
if(taskCountOne == taskCountThree && taskCountOne == taskCountFive) {
winner = (mistakeAllOne == mistakeAllThree && mistakeAllOne == mistakeAllFive) ? "1" :
(mistakeAllOne == mistakeAllThree && mistakeAllOne < mistakeAllFive) ? "1" :
(mistakeAllThree == mistakeCountFive && mistakeAllThree < mistakeAllOne) ? "3" :
(mistakeAllOne == mistakeAllFive && mistakeAllOne < mistakeAllThree) ? "1" :
(mistakeAllFive < mistakeAllThree && mistakeAllFive < mistakeAllOne) ? "5" :
(mistakeAllThree < mistakeAllFive && mistakeAllThree < mistakeAllOne) ? "3" : "1";
}
}
FileWriter countStepFinish = new FileWriter("output.txt");// Запись числа в файл
countStepFinish.write(winner);
countStepFinish.close();
}
}
Github: https://github.com/DEBAGanov