Постановка задачи

Шеф хочет провести несколько соревнований Дивизиона-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);
          }
    
  }
 }
}

Надеюсь, вам понравилась статья. Пожалуйста, дайте аплодисменты этой статье и подпишитесь на меня для других будущих блогов, связанных с программированием.

Ссылки

https://www.codechef.com/JAN21C/problems/DIVTHREE