+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: Coding (https://sinister.li/Forum-Coding--71)
+--- Thread: CCC Challenges (/Thread-CCC-Challenges)
CCC Challenges - Inori - 01-15-2016
I'm doing prep for CCC, which is a big algorithmic competition sponsored by the University of Waterloo, which is the top Computer Science school in Canada. Sadly, I can only do the junior competition, but the challenges are still pretty good. I'll update this thread periodically as I get more problems.
Quick Note: All input is taken from stdin, not arguments or files
Problems:
Spoiler: <span style="font-size: 4pt;" class="mycode_size">2011 J2 - Who Has Seen The Wind</span>
Problem Description:
Margaret has looked at the wind floating over the prairies for a long time. After these observations, she has created a formula that will describe the altitude of a weather balloon launched from her house. In particular, her equation predicts the altitude A (in metres above the ground) at hour t after launching her balloon is:
where h is an integer value representing the humidity as a value between 0 and 100 inclusive.
Margaret is curious at what the earliest hour is (if any) that her weather balloon will hit the ground after launch, so long as it is no more than the maximum time, M, that Margaret is willing to wait.
You can assume that the weather balloon touches ground when A ≤ 0.
In order to do this, your program should use the formula to calculate the altitude when t = 1,
t = 2, and so on, until the balloon touches the ground or t = M is reached.
Input Specification:
The input is two non-negative integers: h, the humidity factor, followed by M, the maximum
number of hours Margaret will wait for the weather balloon to return to ground. You can assume
0 ≤ h ≤ 100 and 0 < M < 240.
Output Specification:
The output will be one of the following possibilities:
• The balloon does not touch ground in the given time.
• The balloon first touches ground at hour:
T
where T is a positive integer value representing the earliest hour when the balloon has altitude less than or equal to zero.
Sample 1:
Sample 2:
Margaret has looked at the wind floating over the prairies for a long time. After these observations, she has created a formula that will describe the altitude of a weather balloon launched from her house. In particular, her equation predicts the altitude A (in metres above the ground) at hour t after launching her balloon is:
Code:
A = −6t^4 + ht^3 + 2t^2 + tMargaret is curious at what the earliest hour is (if any) that her weather balloon will hit the ground after launch, so long as it is no more than the maximum time, M, that Margaret is willing to wait.
You can assume that the weather balloon touches ground when A ≤ 0.
In order to do this, your program should use the formula to calculate the altitude when t = 1,
t = 2, and so on, until the balloon touches the ground or t = M is reached.
Input Specification:
The input is two non-negative integers: h, the humidity factor, followed by M, the maximum
number of hours Margaret will wait for the weather balloon to return to ground. You can assume
0 ≤ h ≤ 100 and 0 < M < 240.
Output Specification:
The output will be one of the following possibilities:
• The balloon does not touch ground in the given time.
• The balloon first touches ground at hour:
T
where T is a positive integer value representing the earliest hour when the balloon has altitude less than or equal to zero.
Sample 1:
Code:
30
10
#output
The balloon first touches ground at hour:
6Sample 2:
Code:
#input
70
10
#output
The balloon does not touch ground in the given time.Spoiler: <span style="font-size: 4pt;" class="mycode_size">2011 J3 - Sumac Sequences</span>
Problem Description:
In a sumac sequence, t1, t2, .., tm, each term is an integer greater than or equal 0. Also, each term, starting with the third, is the difference of the preceding two terms (that is, tn+2 = tn − tn+1 for n ≥ 1). The sequence terminates at tm if tm−1 < tm. For example, if we have 120 and 71, then the sumac sequence generated is as follows:
120, 71, 49, 22, 27.
This is a sumac sequence of length 5.
Input Specification:
The input will be two positive numbers t1 and t2, with 0 < t2 < t1 < 10000.
Output Specification:
The output will be the length of the sumac sequence given by the starting numbers t1 and t2.
Sample:
In a sumac sequence, t1, t2, .., tm, each term is an integer greater than or equal 0. Also, each term, starting with the third, is the difference of the preceding two terms (that is, tn+2 = tn − tn+1 for n ≥ 1). The sequence terminates at tm if tm−1 < tm. For example, if we have 120 and 71, then the sumac sequence generated is as follows:
120, 71, 49, 22, 27.
This is a sumac sequence of length 5.
Input Specification:
The input will be two positive numbers t1 and t2, with 0 < t2 < t1 < 10000.
Output Specification:
The output will be the length of the sumac sequence given by the starting numbers t1 and t2.
Sample:
Code:
#input
120
71
#output
5Spoiler: <span style="font-size: 4pt;" class="mycode_size">2012 J2 - Sounds Fishy</span>
Problem Description:
A fish-finder is a device used by anglers to find fish in a lake. If the fish-finder finds a fish, it will
sound an alarm. It uses depth readings to determine whether to sound an alarm. For our purposes, the fish-finder will decide that a fish is swimming past if:
• there are four consecutive depth readings which form a strictly increasing sequence (such as 3 4 7 9) (which we will call “Fish Rising”), or
• there are four consecutive depth readings which form a strictly decreasing sequence (such as 9 6 5 2) (which we will call “Fish Diving”), or
• there are four consecutive depth readings which are identical (which we will call “Constant Depth”).
All other readings will be considered random noise or debris, which we will call “No Fish.”
Your task is to read a sequence of depth readings and determine if the alarm will sound.
Input Specification:
The input will be four positive integers, representing the depth readings. Each integer will be on
its own line of input.
Output Specification:
The output is one of four possibilities. If the depth readings are increasing, then the output
should be Fish Rising. If the depth readings are decreasing, then the output should be Fish
Diving. If the depth readings are identical, then the output should be Fish At Constant
Depth. Otherwise, the output should be No Fish.
Sample 1:
Sample 2:
A fish-finder is a device used by anglers to find fish in a lake. If the fish-finder finds a fish, it will
sound an alarm. It uses depth readings to determine whether to sound an alarm. For our purposes, the fish-finder will decide that a fish is swimming past if:
• there are four consecutive depth readings which form a strictly increasing sequence (such as 3 4 7 9) (which we will call “Fish Rising”), or
• there are four consecutive depth readings which form a strictly decreasing sequence (such as 9 6 5 2) (which we will call “Fish Diving”), or
• there are four consecutive depth readings which are identical (which we will call “Constant Depth”).
All other readings will be considered random noise or debris, which we will call “No Fish.”
Your task is to read a sequence of depth readings and determine if the alarm will sound.
Input Specification:
The input will be four positive integers, representing the depth readings. Each integer will be on
its own line of input.
Output Specification:
The output is one of four possibilities. If the depth readings are increasing, then the output
should be Fish Rising. If the depth readings are decreasing, then the output should be Fish
Diving. If the depth readings are identical, then the output should be Fish At Constant
Depth. Otherwise, the output should be No Fish.
Sample 1:
Code:
#input
30
10
20
20
#output
No FishSample 2:
Code:
#input
1
10
12
13
#output
Fish RisingSpoiler: <span style="font-size: 4pt;" class="mycode_size">2012 J3 - Icon Scaling</span>
Problem Description:
You have been asked to take a small icon that appears on the screen of a smart telephone and scale it up so it looks bigger on a regular computer screen.
The icon will be encoded as characters (x and *) in a 3 × 3 grid as follows:
Write a program that accepts a positive integer scaling factor and outputs the scaled icon. A scaling factor of k means that each character is replaced by a k × k grid consisting only of that character.
Input Specification:
The input will be a positive integer k such that k < 25.
Output Specification:
The output will be 3k lines, which represent each individual line scaled by a factor of k and
repeated k times. A line is scaled by a factor of k by replacing each character in the line with k
copies of the character.
Sample:
You have been asked to take a small icon that appears on the screen of a smart telephone and scale it up so it looks bigger on a regular computer screen.
The icon will be encoded as characters (x and *) in a 3 × 3 grid as follows:
Code:
*x*
xx
* *Write a program that accepts a positive integer scaling factor and outputs the scaled icon. A scaling factor of k means that each character is replaced by a k × k grid consisting only of that character.
Input Specification:
The input will be a positive integer k such that k < 25.
Output Specification:
The output will be 3k lines, which represent each individual line scaled by a factor of k and
repeated k times. A line is scaled by a factor of k by replacing each character in the line with k
copies of the character.
Sample:
Code:
#input
3
#output
***xxx***
***xxx***
***xxx***
xxxxxx
xxxxxx
xxxxxx
*** ***
*** ***
*** ***Sample solutions:
Spoiler: 2011 J2
Code:
h=input()
m=input()
t=1
while 1:
a=(-6*(t**4))+(h*(t**3))+(2*(t**2))+t
if a<0: break
t+=1
if t<=m:
print "The balloon first touches the ground at hour:\n"+str(t)
else:
print "The balloon does not touch the ground in the given time."Spoiler: 2011 J3
Code:
f=input()
s=input()
l=2
while 1:
f,s=s,f-s
if s<=0: break
l+=1
print lSpoiler: 2012 J2
Code:
r=[]
for i in range(4):
r.append(input())
if r[0]<r[1] and r[1]<r[2] and r[2]<r[3]:
print "Fish Rising"
elif r[0]>r[1] and r[1]>r[2] and r[2]>r[3]:
print "Fish Diving"
elif r[0]*4==sum(r):
print "Fish At Constant Depth"
else:
print "No Fish"Spoiler: 2012 J3
Code:
ico=['*x*',' xx','* *']
s=input()
for x in ico:
for i in range(s):
print ''.join([x[0]*s,x[1]*s,x[2]*s])RE: CCC Challenges - The Real Slim Shady - 01-15-2016
(01-15-2016, 04:06 PM)Chitoge Wrote: sponsored by the University of Waterloo, which is the top Computer Science school in Canada.
Is that what they tell you? hehe
RE: CCC Challenges - Shebang - 01-15-2016
I forget what grade you're in, I thought you'd be doing the Senior competition now.
@The Real Slim Shady - I may be biased since I go there, but I'd have to agree that it's the best
RE: CCC Challenges - Inori - 01-15-2016
(01-15-2016, 05:31 PM)The Real Slim Shady Wrote: Is that what they tell you? hehe
Lol, regardless, it's pretty damn good.
(01-15-2016, 07:09 PM)Shebang Wrote: I forget what grade you're in, I thought you'd be doing the Senior competition now.
I'm in grade 10, so I could do either, but I'm doing prep and study at a programming school and proxy registering through my school, so j it is.
RE: CCC Challenges - Nil - 01-15-2016
These are fun. Thanks for sharing.
RE: CCC Challenges - Rick - 01-17-2016
What are these challenges supposed to be for, as in what is this competition you're doing? Are you given these challenges and told to just do them in a set time frame? How long is the time?
RE: CCC Challenges - Oni - 01-18-2016
(01-15-2016, 05:31 PM)The Real Slim Shady Wrote: Is that what they tell you? hehe
It's what any decent university will try to tell you.
RE: CCC Challenges - Inori - 01-18-2016
(01-17-2016, 11:37 PM)Rick Wrote: What are these challenges supposed to be for, as in what is this competition you're doing? Are you given these challenges and told to just do them in a set time frame? How long is the time?
There's 5 problems like this, and you get 5 tries for each. Your goal is to solve them all in the shortest time, so there's no limit.
RE: CCC Challenges - The Real Slim Shady - 01-18-2016
(01-18-2016, 12:21 AM)Oni Wrote: It's what any decent university will try to tell you.
a decent university will lie to you?