SPOJ.com - Problem CHKL

CHKL - Distributing Chocolates

no tags

Ohani’s uncle has just returned from USA and brought a lot of chocolates for her. Ohani is very excited about it and wants to distribute the chocolates among her friends. But she is in a great problem. How she will distribute chocolates? Then suddenly an idea came in her mind.

Ohani loves lucky numbers a lot. She always thinks N is a lucky number for her. She wants to give chocolates to her friends according to the proper divisors of N. For this reason she needs chocolates as much as the sum of divisors of N. For example: If Ohani’s lucky number is 12, then it’s proper divisors are 1, 2, 3, 4 and 6. So, she need at most (1+2+3+4+6) = 16 chocolates. Now, if Ohani has 3 friends, then she can distribute chocolates them as below:

Give 1^st friend 2 chocolates, 2^nd friend 3 and 3^rd friend 4 chocolates

Give 1^st friend 2 chocolates, 2^nd friend 4 and 3^rd friend 6 chocolates and so on.

But Ohani don’t have much time to calculate at most how much chocolates she needs and again if she will be able to distribute chocolates between her M friends with her lucky number N.

(Note: A positive proper divisor is a positive divisor of a number N, excluding N itself)

Input

The first line of the input denotes the number of test cases T (T <= 1000000).

The next T lines describe each test case. Each test case contains two numbers, N (2<=N <= 1000000) & M (1<=M<=1000000) where N denotes Ohani’s lucky number and M denotes her number of friends.

Output

Each test case has one line of output. If it is impossible to distribute chocolates among M friends then just output:
Case X: Impossible

Here X is the test case number.

Otherwise, if it is possible to distribute, then first output a word “Yes” and then the number of chocolates Ohani at most needs to keep with her in the formate below:

Case X: Yes Y

Here, X is the test case number and Y is the number of chocolates.

Sample Input	Output for Sample Input
2 3 2 12 3	Case 1: Impossible Case 2: Yes 16

Problem Setter: Raihat Zaman Niloy, Jahangirnagar University

Alternative Solution: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology

Submit solution!

hide comments

< Previous 1 2 Next >

	Francky: 2014-12-08 21:55:26 @Lakshman (in reply at PHONY) : here is a recent problem, and the psetter seems to have forgot the rejudge... @psetter : please rejudge all submissions and allow all languages, there's no reason for such limitations. --edit--> Thanks to admin Piotr, it's done. Many thanks. Last edit: 2014-12-08 22:33:55
	Min_25: 2014-12-08 21:55:26 This problem seems to be switched (by the author) to Cube (on 2014/08/07 ?), but the submitted solutions have not been rejudged. Last edit: 2014-12-03 05:42:30
	[Lakshman]: 2014-12-08 21:55:26 @Ranjan Kumar order is not necessary he can give any number of chocolate (of course the proper divisor) to any of his friend.
	Ranjan Kumar Singh: 2014-12-08 21:55:26 is it fix that first friend should get 2??? 1 chocolate is not given...??? help iam getting WA
	Ranjan Kumar Singh: 2014-12-08 21:55:26 I am getting WA...help me with tricky cases
	[Lakshman]: 2014-12-08 21:55:26 @Francky now I have AC, and I got AC with scanf & printf with my method in .56s and with fast IO .36s. one more thing there no M > 100. --ans(Francky)--> So it should be OK to "show" it again. --Lakshman->Thanks Francky Fully agree with Min_25 Last edit: 2014-06-24 08:42:01
	[Lakshman]: 2014-12-08 21:55:26 @Min_25 I think I have some doubt about what I have understood form the problem if we took the above example given in problem statement if she have 6 friends then she can't distribute the chocolates among her friends and answer is "Impossible" correct me if I am wrong Last edit: 2014-06-23 19:30:39
	Min_25: 2014-12-08 21:55:26 Although the time limit is very strict, test cases seem to be correct. We need fast I/O functions to get AC. EDIT: @Lakshman You are right. EDIT2: I confirmed that this problem can be solved without fast I/O functions. However, I still think that the time limit should be relaxed. Last edit: 2014-06-24 08:35:56
	Francky: 2014-12-08 21:55:26 Problem hidden, waiting for probable IO check, or explanations to psolver. (It's true there's yet one AC, but ...) --edit(Francky)--> It seems Min_25 solved the problem ; maybe we'll have some infos. --edit2(Francky)--> As fast IO are required to get AC, psetter is asked to set better constraints on time limit, or justify that a better method is awaited. Problem still hidden waiting for that. Last edit: 2014-06-23 19:58:41
	[Lakshman]: 2014-12-08 21:55:26 @Md Abdul Alim don't you have some time for problem solvers to answer their queries? Last edit: 2014-06-23 16:07:39

Submit solution!

Added by:	Alim
Date:	2014-06-15
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All