The RUN CHASE: A Challenge for the Programmer in U...
in [General Programming]
|
From: CVS on 5 Apr 2010 03:12 In a game of cricket, 1. Assume you can score exactly as you want on each ball. 2. Single/Double/Triple/Four/Six are the options available to you on each ball.(no extras) 3. RISK is defined as the square of the score on each ball. * * * * Write a program that accepts:- a. Target runs to score (N) b. No. of balls to score it in (x) and prints the runs to score on each ball. Remember U have to ACHIEVE the target with MINIMUM RISK possible. For detailed problem statement and sample output plz refer http://2600hertz.wordpress.com/2010/04/04/ipl-the-run-chase/ Lets C who comes first... ;-) Good Luck!!
From: Willem on 5 Apr 2010 04:16 CVS wrote: ) In a game of cricket, ) ) 1. Assume you can score exactly as you want on each ball. ) ) 2. Single/Double/Triple/Four/Six are the options available to you on ) each ball.(no extras) ) ) 3. RISK is defined as the square of the score on each ball. ) ) * * * * ) Write a program that accepts:- ) a. Target runs to score (N) ) b. No. of balls to score it in (x) ) ) and prints the runs to score on each ball. ) ) Remember U have to ACHIEVE the target with MINIMUM RISK possible. I don't see what's so hard about this puzzle: For the current run, take N/x, round down to the nearest possible score, and score that. Then, you know what score you have to get with x-1 balls. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT
From: Richard Heathfield on 5 Apr 2010 05:49 CVS wrote: > In a game of cricket, > > 1. Assume you can score exactly as you want on each ball. > > 2. Single/Double/Triple/Four/Six are the options available to you on > each ball.(no extras) > > 3. RISK is defined as the square of the score on each ball. > > * * * * > Write a program that accepts:- > a. Target runs to score (N) > b. No. of balls to score it in (x) > > and prints the runs to score on each ball. > > Remember U have to ACHIEVE the target with MINIMUM RISK possible. Hypothesis: for scoring N, the minimum risk is achieved when you hit N singles. To score N + 1, we can do one of these things: * reduce N to N-5, then add a six. The effect on the risk is that R[N+1] is (R[N] - 5) + 36 = R[N] + 31, which is greater than R[N]; * reduce N to N-3, then add a four. This gives a risk greater than R[N] by 4*4-3 = 13; * reduce N to N-2, then add a three. This gives a risk greater than R[N] by 3*3-2 = 7; * reduce N to N-1, then add a two. This gives a risk greater than R[N] by 2*2-1 = 3; * simply add a single. This increases the risk by 1, the minimum. Now the base cases. To score 0, the least risky score is 0. To score 1, the least risky score is a single. To score 2, the least risky score is two singles. To score 3, the least risky score is three singles. To score 4, the least risky score is four singles. To score 5, the least risky score is five singles. And just to be sure, to score 6 the least risky score is six singles. Induction has shown us that singles are always the safest way. Since the overriding requirement is minimum risk, x is irrelevant and can be ignored. This fact suggests the following program: #include <stdio.h> #include <stdlib.h> #define MAX_LEN 32 int main(void) { char line[MAX_LEN] = {0}; fputs("Enter N\n", stderr); if(fgets(line, sizeof line, stdin) != NULL) { char *endptr = NULL; unsigned long n = strtoul(line, &endptr, 10); if(endptr > line) { fputs("N accepted. Enter x.\n", stderr); if(fgets(line, sizeof line, stdin) != NULL) { fputs("x accepted.\n", stderr); printf("The minimum risk is achieved via %lu singles.\n", n); } } } return 0; } -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: James Harris on 5 Apr 2010 06:21 On 5 Apr, 09:16, Willem <wil...(a)turtle.stack.nl> wrote: > CVS wrote: > > ) In a game of cricket, > ) > ) 1. Assume you can score exactly as you want on each ball. > ) > ) 2. Single/Double/Triple/Four/Six are the options available to you on > ) each ball.(no extras) > ) > ) 3. RISK is defined as the square of the score on each ball. > ) > ) * * * * > ) Write a program that accepts:- > ) a. Target runs to score (N) > ) b. No. of balls to score it in (x) > ) > ) and prints the runs to score on each ball. > ) > ) Remember U have to ACHIEVE the target with MINIMUM RISK possible. > > I don't see what's so hard about this puzzle: > For the current run, take N/x, round down to the nearest possible score, > and score that. Then, you know what score you have to get with x-1 balls. That seems almost right but what if the penultimate N/x results in 5? James
From: news.telesweet.net on 5 Apr 2010 06:46
On 4/5/2010 5:49 AM, Richard Heathfield wrote: > CVS wrote: >> In a game of cricket, >> >> 1. Assume you can score exactly as you want on each ball. >> >> 2. Single/Double/Triple/Four/Six are the options available to you on >> each ball.(no extras) >> >> 3. RISK is defined as the square of the score on each ball. >> >> * * * * >> Write a program that accepts:- >> a. Target runs to score (N) >> b. No. of balls to score it in (x) >> >> and prints the runs to score on each ball. >> >> Remember U have to ACHIEVE the target with MINIMUM RISK possible. > > Hypothesis: for scoring N, the minimum risk is achieved when you hit N > singles. > > To score N + 1, we can do one of these things: > > * reduce N to N-5, then add a six. The effect on the risk is that R[N+1] > is (R[N] - 5) + 36 = R[N] + 31, which is greater than R[N]; > * reduce N to N-3, then add a four. This gives a risk greater than R[N] > by 4*4-3 = 13; > * reduce N to N-2, then add a three. This gives a risk greater than R[N] > by 3*3-2 = 7; > * reduce N to N-1, then add a two. This gives a risk greater than R[N] > by 2*2-1 = 3; > * simply add a single. This increases the risk by 1, the minimum. > > Now the base cases. To score 0, the least risky score is 0. To score 1, > the least risky score is a single. To score 2, the least risky score is > two singles. To score 3, the least risky score is three singles. To > score 4, the least risky score is four singles. To score 5, the least > risky score is five singles. And just to be sure, to score 6 the least > risky score is six singles. > > Induction has shown us that singles are always the safest way. Since the > overriding requirement is minimum risk, x is irrelevant and can be ignored. You have implicitly assumed that x >= N in this argument. If x < N then it is simply impossible to score N on x balls by only scoring singles. -- Dan G |