oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

coincombinations Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

coincombinations.html


Josephine was working one day at her money exchange booth when a customer walked up to her.
“Can you take these coins and give the same value to me in as many different ways as possible?”
Being quite blur and stupid, Josephine replied, “Isn’t there only one way?”
“No, there are definitely more ways to do it than one.”

Write a program to prove to Josephine that there is more than one way to make a value
with a set amount of coins.

Given n (1 ≤ n ≤ 50) coins, each of value n(i) (1 ≤ n(i) ≤ 10,000) and a
value v (1 ≤ v ≤ 10,000), calculate how many different ways you can make the
value v with the coins given, mod 13371337.

POINTS: 100

PROBLEM NAME: coincombinations

INPUT FORMAT:

Line 1:     The first line contains two integers, n and v, separated by a space.
Line 2...n: Each line contains one integer each, with the (i + 1)th line representing
			the value of coin n(i). 

INPUT DETAILS:

Every coin has a unique value. The values of the coins might not necessarily be less
than the value v.

SAMPLE INPUT:

3 4
1
2
3

OUTPUT FORMAT:

Line 1: A single integer which is the number of ways that the set of coins can make the
given value, mod 13371337.

OUTPUT:

4

OUTPUT DETAILS:

4 can be made in exactly four ways with the given coins:
(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3).

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o coincombinations -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.