Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7762 - Гоёл чимэглэлийн цуглуулга

Виктория өөрийн дуртай дэлгүүрүүдээс үнэтэй гоё чимэглэлийн хэрэгслүүдийг худалдан авч байна.

Дэлгүүр бүр A төрлийн гоёл чимэглэлийг худалддаг, энд i-р гоёл i долларын (1 <= i <= A)  үнэтэй байдаг.

Ижил төрлийн бүтээгдэхүүний үнэ адилхан бөгөөд дэлгүүр нь аль төрлийн гоёл чимэглэлийг хангалттай хэмжээнд нийлүүлдэг гэж үзье.

Виктория дараах дүрмийн дагуу нийт L гоёл чимэглэлийг худалдан авахыг хүсэж байна.

Захиалсан L бүтээгдэхүүний ямар ч N элементтэй дэд олонлог дор хаяж D ялгаатай төрлийн гоёл чимэглэлийг агуулж байх ёстой.

Жишээлбэл: L=6, N=3, D=2 бол тэр 6 гоёл сонгох бөгөөд  уг 6 бүтээгдэхүүний ямар ч 3 элементтэй дэд хэсэг нь дор хаяж 2 ялгаатай төрлийнх байх ёстой.

T удаагийн дэлгүүр явахад  харгалзах L, A, N болон D утгууд өгөгдсөн бол Викториягийн дэлгүүр явах бүрд зарцуулж болох хамгийн их мөнгийг олж хэвлэнэ үү. Хэрэв тийм боломж байхгүй бол түүнийг хүслээ биелүүлээгүй гэж үзээд SAD гэдэг утгыг хэвлээрэй. Дэлгүүр явах бүрийн хариу болох утгыг шинэ мөрд хэвлээрэй.

Оролтын хэлбэр

Эхний мөрд дэлгүүр явсан утга T тоо байна.

Дараагийн T мөрд дэлгүүр явалт бүрд харгалзах L, A, N болон D утгууд хоосон зайгаар тусгаарлагдан өгөгдөнө. 

Зааглалт


  • 1 <= T <= 10^6
  • 1 <= D <= N <= L <= 10^5
  • 1 <= A <= 10^9
  • Бүх T хувьд L -үүдийн нийлбэр  <= 8*10^6.

    • Гаралтын хэлбэр

    Худалдаа хийх явалт бүрд Викториягийн зарцуулж болох хамгийн их хэмжээний мөнгийг нэг нэгээр мөрүүдэд хэвлэ. Хэрэв худалдан авах дүрмийг хангасан зүйлсийн цуглуулга байхгүй бол мөнгөний оронд SAD хэвлээрэй.

    Жишээ Оролт

    2

    6 5 3 2

    2 1 2 2

    Жишээ Гаралт

    24

    SAD

    Тайлбар

    Худалдан авалт 1

    Бид дараахыг мэднэ:

  • Виктория L=6 гоёл худалдаж авахыг хүссэн.
  • Дэлгүүр {1, 2, 3, 4, 5} гэсэн A=5 төрлийн гоёл зарж байгаа.
  • Түүний сонгосон L = 6 гоёлын хувьд аль ч N = 3 дэд хэсэг дор хаяж D = 2 ялгаатай төрөлтэй байх ёстой.

    • Виктория  худалдан авах дүрмээ ханган хамгийн их мөнгө зарцуулж байхаар {3, 4, 5, 5, 4, 3}  гэж бараагаа сонговол эдгээрийн нийт үнэ 3 + 4 + 5 + 5 + 4 + 3 = 24 болох тул гаралтын эхний мөрд 24-г хэвлэнэ.

    Худалдан авалт 2

    Бид дараахыг мэднэ:

  • Виктория L = 2 гоёл худалдаж авахыг хүссэн.
  • Дэлгүүр { 1 } гэсэн A = 1 төрлийн гоёл зарж байгаа. /зөвхөн нэг төрлийн/
  • Түүний сонгосон L = 2 гоёлын хувьд аль ч N = 2 дэд хэсэг дор хаяж D = 2 ялгаатай төрөлтэй байх ёстой.

    • Мэдээж энэ үед түүнд хоёр өөр төрлийн бараа сонгох боломжгүй тул худалдан авалтын дүрэм биелэхгүй. Иймд дараагийн мөрд SAD гэж хэвлэнэ.


    Орчуулсан : Р.Мижиддорж МУБИС, доктор

    Submit solution!
    Нэмсэн:Bataa
    Огноо:2020-03-30
    Хугацааны хязгаарлалт:1s
    Эх кодын хэмжээний хязгаарлалт:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Програмчлалын хэлүүд:ADA95 ASM32 ASM64 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
    Эх сурвалж:https://www.hackerrank.com/challenges/accessory-collection/problem
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.