Постановка задачи
Шеф хочет провести несколько соревнований Дивизиона-3. У шефа есть N сеттеров, которые заняты созданием для него новых задач. i-й установщик составил Ai задач, где 1≤i≤N.
В Дивизионе-3 должно быть ровно K задач. Шеф-повар хочет спланировать следующие дни D, используя текущие проблемы. Но Chef не может проводить более одного соревнования Дивизиона-3 в день.
Учитывая эти ограничения, можете ли вы помочь Chef найти максимальное количество соревнований Дивизиона 3, которые можно провести в эти дни D?
Вход:
- Первая строка ввода содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев.
- Первая строка каждого набора входных данных содержит три целых числа через пробел — N, K и D соответственно.
- Вторая строка каждого набора входных данных содержит N целых чисел A1,A2,…,AN, разделенных пробелом соответственно.
Вывод:
Для каждого набора входных данных выведите одну строку, содержащую одно целое число ― максимальное количество конкурсов Дивизиона 3, которое Chef может провести за эти D дней.
Ограничения
- 1≤T≤103
- 1≤N≤102
- 1≤K≤109
- 1≤D≤109
- 1≤Ai≤107 для каждого действительного i
Подзадачи
Подзадача №1 (40 баллов):
- N=1
- 1≤A1≤105
Подзадача 2 (60 баллов): исходные ограничения.
Пример ввода:
5
1 5 31
4
1 10 3
23
2 5 7
20 36
2 5 10
19 2
3 3 300
1 1 1
Пример вывода:
0
2
7
4
1
Объяснение:
- Пример 1: у шеф-повара только A1=4A1=4 задачи, и ему нужно K=5K=5 задач для соревнования Дивизиона-3. Таким образом, Chef не сможет проводить соревнования Дивизиона 3 в течение 31 дня. Следовательно, первый вывод равен 00.
- Пример 2: у шеф-повара A1=23A1=23 задачи, и ему нужно K=10K=10 задач для конкурса Дивизиона-3. Chef может выбрать любые 10+10=2010+10=20 задач и за эти 3 дня провести 22 конкурса Дивизиона-3. Следовательно, второй выход равен 22.
- Пример 3: у Chef есть A1=20A1=20 проблем от установщика-1 и A2=36A2=36 проблем от установщика-2, всего 5656 проблем. Шефу нужно K=5K=5 задач на каждый конкурс Дивизиона-3. Таким образом, Chef может подготовить 1111 соревнований Дивизиона-3. Но так как мы планируем только на ближайшие D=7D=7 дней, а Chef не может проводить более 11 конкурсов в день, Chef не может проводить более 77 конкурсов. Следовательно, третий выход равен 77.
Код (решение)
Код реализован на Java.
import java.util.*; class Codechef { public static void main (String[] args) throws java.lang.Exception { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-- > 0){ int n = sc.nextInt(); int k = sc.nextInt(); int d = sc.nextInt(); int count,sum =0; } if(sum < k){ System.out.println("0"); } else if(sum==k){ System.out.println("1"); } else{ count = sum / k; if(count <= d) System.out.println(count); else System.out.println(d); } } } }
Надеюсь, вам понравилась статья. Пожалуйста, дайте аплодисменты этой статье и подпишитесь на меня для других будущих блогов, связанных с программированием.
Ссылки