Интересная олимпиадная задача. [закрыт]

193
20 июля 2019, 07:30

Есть задачка, довольно простая, я думаю. Решение пришло сразу же: Мы ищем максимальный из дней (d-итых), и выводим какой это день недели. Т.к чтобы они могли встретится, все дни должны быть делителем наибольшего дня. (Те. мы заводим массив дней, и сортируем по убыванию, все элементы являются делителем первого) Валится на тесте 4. Не могу найти ошибку.

Грин-де-Вальд хочет собрать своих сторонников. Но, к сожалению, он может сделать это не в любой день. Всего у Грин-де-Вальда есть n сторонников. Пронумеруем их от 1 до n. Сторонник с номером i, исходя из личных убеждений, посещает место встречи каждые di дней (то есть если интервал между двумя посещениями сторонника с номером i составляет di дней). Грин-де-Вальд помнит, что в последний раз все его сторонники одновременно появлялись на месте встречи в день недели с номером s. Помогите ему определить, какой номер будет иметь день недели, когда все сторонники снова одновременно окажутся на месте встречи. Напомним, что в неделе 7 дней, Грин-де-Вальд пронумеровал их числами от 1 до 7 в порядке

следования. Формат входных данных Первая строка входных данных содержит два целых числа n и s (1 ⩽ n ⩽ 105 , 1 ⩽ s ⩽ 7). Вторая строка содержит n целых чисел di (1 ⩽ di ⩽ 20). Формат выходных данных Выведите единственное число от 1 до 7 — номер дня недели

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import static java.lang.Integer.parseInt;
/**
 * Created by Andrey on 31.12.2018.
 */
public class Main {
    static int scanInt() throws IOException {
        return parseInt(scanString());
    }

    static String scanString() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }
    static BufferedReader in;
    static StringTokenizer tok;
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        int n = scanInt();
        int s = scanInt();
        ArrayList<Integer> days = new ArrayList<>();
        for(int i = 0; i < n; ++i){
            days.add(scanInt());
        }
        days.sort(Collections.reverseOrder());

        ArrayList<Integer> week = new ArrayList<>();
        for(int i = 0; i < 1000; ++i){
            week.add(1);
            week.add(2);
            week.add(3);
            week.add(4);
            week.add(5);
            week.add(6);
            week.add(7);
        }
        System.out.println(week.get(s+days.get(0) - 1));



    }
}
Answer 1

Я бы сделал немного по-другому. Я бы нашёл НОК от всех Di, таким образом, найдя периодичность встреч.

Далее, я бы прибавил данное значение к дню нашей последней встречи, чтобы найти следующий день встречи, и взял бы его по модулю 7.

Если ответ равен нулю, то выводим семь, т.к. 7/14/21/... % 7 == 0 и это стоит учесть.

Таким образом, решение схематически может выглядеть примерно вот так:

n, s = input()
d[]  = input_array()
period = lcm(d[0], d[1], ..., d[n - 1])
new_day = (s + period) % 7
if new_day == 0: new_day = 7
output(new_day)
Answer 2

если так?

public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    // число сторонников и день недели
    String[] nsStr = reader.readLine().split(" ");
    int n= Integer.parseInt(nsStr[0]); // число сторонников
    int s = Integer.parseInt(nsStr[1]); // день недели
    // период в днях для каждого сторонника
    String[] diStrArr = reader.readLine().split(" ");
    int[] di = new int[diStrArr.length];
    for (int i = 0; i < diStrArr.length; i++) {
        di[i] = Integer.parseInt(diStrArr[i]);
    }
    // наименьшее общее кратное для всех периодов
    int gcd = 1;
    for (int i = 0; i < di.length; i++) {
        gcd = gcd * di[i] / getLCM(gcd, di[i]);
    }
    // день недели
    int weekDay = (gcd + s) % 7;
    weekDay = weekDay == 0 ? 7 : weekDay;
    // вывод
    System.out.println(weekDay);
}
// наибольший общий делитель
public static int getLCM(int a, int b) {
    while (a != b) {
        int a1 = Math.min(a, b);
        int b1 = Math.abs(a - b);
        a = a1;
        b = b1;
    }
    return a;
}
READ ALSO
Stream API. Метод reduce()

Stream API. Метод reduce()

Вопрос касательно третьей формы метода:

179
Как в Hibernate создать запрос с параметром?

Как в Hibernate создать запрос с параметром?

Всем приветИзучаю Hibernate, делаю запрос

196
Java фризы во время выполнения

Java фризы во время выполнения

Собрал игру нa LibGDX в Eclipse, запускаю и каждые 10± секунд происходит дроп фреймрейта до 5-10 на пару секунд и освобождается 10Мб+ оперативной памятиДумал...

144