Magic Stone Problem Solution and Simulation
HKOI 2014 Junior
Magic Stone
Problem Prepared By Sampson Lee
Problem
•
Given four operation
–
Type Ti = 1: Buy Ai magic stones.
–
Type Ti = 2: The system gives you Ai magic stones.
–
Type Ti = 3: Dr. Jones uses Ai magic stones.
–
Type Ti = 4: Query: Among the magic stones Dr.
Jones currently has, at most how many of them
were bought? And at least how many of them
were bought?
•
Simulate the above process
Observation
•
At most how many of them were bought?
–
If we always use the stones system gave us, it
must be the best way to preserve the stones that
were bought
•
At least how many of them were bought?
–
If we always use the stones that were bought, it
must be the best way to preserve the stones that
were given by the system
Solution
•
Maintain four variables, namely p, q, r, s
–
p : number of stones given by the system if we
always use the stones given by the system first
–
q : number of stones bought if we always use the
stones given by the system first
–
r : number of stones given by the system if we
always use the stones we bought first
–
s : number of stones bought if we always use the
stones we bought first
Solution
•
How to maintain?
–
Type Ti = 1: add Ai to q and s
–
Type Ti = 2: add Ai to p and r
–
Type Ti = 3:
•
Subtract Ai from p and s until there are no stone within,
and subtract the residue stone from r and q
–
Type Ti = 4: Output q and r
•
END
In this problem, you are tasked with determining the maximum and minimum number of magic stones bought by Dr. Jones. Through a simulation process involving different operations on stones, you can find an optimal solution. By maintaining variables and following specific steps, you can calculate the quantities of stones purchased and given by the system. The solution method involves a systematic approach to handling the stones to optimize preservation and deduction. Follow the provided process to efficiently solve the Magic Stone Problem.
Uploaded on Feb 25, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
HKOI 2014 Junior Magic Stone Problem Prepared By Sampson Lee
Problem Given four operation Type Ti = 1: Buy Ai magic stones. Type Ti = 2: The system gives you Ai magic stones. Type Ti = 3: Dr. Jones uses Ai magic stones. Type Ti = 4: Query: Among the magic stones Dr. Jones currently has, at most how many of them were bought? And at least how many of them were bought? Simulate the above process
Observation At most how many of them were bought? If we always use the stones system gave us, it must be the best way to preserve the stones that were bought At least how many of them were bought? If we always use the stones that were bought, it must be the best way to preserve the stones that were given by the system
Solution Maintain four variables, namely p, q, r, s p : number of stones given by the system if we always use the stones given by the system first q : number of stones bought if we always use the stones given by the system first r : number of stones given by the system if we always use the stones we bought first s : number of stones bought if we always use the stones we bought first
Solution How to maintain? Type Ti = 1: add Ai to q and s Type Ti = 2: add Ai to p and r Type Ti = 3: Subtract Ai from p and s until there are no stone within, and subtract the residue stone from r and q Type Ti = 4: Output q and r
