forked from Open-CT/openct-tasks
154 lines
8.2 KiB
HTML
154 lines
8.2 KiB
HTML
<!doctype html>
|
|
<html>
|
|
<head>
|
|
<meta charset="utf-8">
|
|
<title>2017-EN-07</title>
|
|
<script>
|
|
window.stringsLanguage = 'en';
|
|
</script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/pemFioi/importModules-1.1.js" id="import-modules"></script>
|
|
<script class="remove" type="text/javascript">
|
|
var modulesPath = '../../../_common/modules';
|
|
importModules([
|
|
'jquery-1.7.1', 'jquery-ui.touch-punch', 'raphael-2.2.1', 'JSON-js',
|
|
'beav-1.0', 'beaver-task-2.0', 'simulation-2.0', 'raphaelFactory-1.0',
|
|
'delayFactory-1.0', 'simulationFactory-1.0', 'drag_lib-2.0',
|
|
'graph-1.0', 'visual-graph-1.0', 'graph-mouse-1.0', 'randomGenerator-1.0',
|
|
'platform-pr', 'buttonsAndMessages', 'installationAPI.01', 'miniPlatform',
|
|
'taskStyles-0.1']);
|
|
</script>
|
|
<script class="remove" type="text/javascript">
|
|
var json = {
|
|
"id": "http://castor-informatique.fr/tasks/2017/2017-FR-07-graph-representation/",
|
|
"language": "en",
|
|
"version": "fr.01",
|
|
"authors": "Arthur Charguéraud, Mathias Hiron, Nir Lavee, France-ioi",
|
|
"translators": "Mohamed El-Sherif",
|
|
"license": "CC BY-SA 3.0",
|
|
"taskPathPrefix": "",
|
|
"modulesPathPrefix": "",
|
|
"browserSupport": [],
|
|
"fullFeedback": true,
|
|
"acceptedAnswers": [],
|
|
"usesRandomSeed": false
|
|
};
|
|
</script>
|
|
<script type="text/javascript">
|
|
var taskStrings = {
|
|
success: "Congratulations, you have succeeded !",
|
|
missingVertex: "There are missing photos. Move the red ball to other cells, then click the button to add a photo.",
|
|
missingEdge: "There are missing black lines between some photos. Click on two photos to link them.",
|
|
shouldAddVertices: "Now click on the photos to link them by lines, as explained in the statement.",
|
|
wrongEdge: "At least one black line is incorrect. Click on it to remove it.",
|
|
vertexExists: "This photo has already been added. Drag the red ball to take another.",
|
|
vertexAdded: "The picture was taken.",
|
|
wrongCell: "At each step, the ball can only be moved to a neighboring cell.",
|
|
droppingOnBall: "The two balls can not be placed in the same cell.",
|
|
dragError: "Drag the red ball to a nearby cell.",
|
|
dropMinimalDistance: "", // Photos cannot be too close to each other // ok to say nothing.
|
|
edgeExists: "The two photos are already connected. Click on the line to remove it.",
|
|
needEdges: "All photos were taken. Click on two photos to link them by a line according to the rule of the statement. Note that you can move the photos on the grey board."
|
|
};
|
|
</script>
|
|
<script type="text/javascript" src="task.js"></script>
|
|
<style>
|
|
#anim_container {
|
|
text-align: center;
|
|
padding-top: 15px;
|
|
}
|
|
#anim {
|
|
display: inline-block;
|
|
}
|
|
#validation {
|
|
margin-top: 1em;
|
|
text-align: center;
|
|
}
|
|
#validation input {
|
|
padding: 2px 10px 2px 10px;
|
|
}
|
|
#configTable {
|
|
margin: auto;
|
|
width: 740px;
|
|
}
|
|
#configContainer {
|
|
padding-left: 40px;
|
|
text-align: center;
|
|
}
|
|
#addSituation {
|
|
padding: 10px;
|
|
margin-left: 10px;
|
|
}
|
|
#messageConfig {
|
|
font-weight: bold;
|
|
color: red;
|
|
width: 400px;
|
|
height: 5em;
|
|
margin: 10px;
|
|
}
|
|
</style>
|
|
</head>
|
|
<body>
|
|
|
|
<div id="task">
|
|
<h1>Photos Game</h1>
|
|
<div id="tabsContainer"></div>
|
|
<div id="taskContent">
|
|
<div style="float:right;text-align:center; margin-left:20px; border: solid black 1px; padding:5px 10px 10px 10px "><p style="margin-top: 10px; margin-bottom: 10px"><b>Example</b></p><p style="margin-top: 0px; margin-bottom: 20px">with a board of 2 cells</p><img src="example.png"></div>
|
|
<p>Help the beaver to take pictures of all possible positions <span class="easy medium">of the red ball.</span><span class="hard">of the two red balls.</span>
|
|
</p>
|
|
<p>You can do this by moving <span class="easy medium">the ball</span><span class="hard">the balls</span> from one cell to a neighboring cell then click the "Take a Picture" button.
|
|
</p>
|
|
<p>
|
|
You will find all the taken photos on the grey area below. Draw a line between any two photos if it is possible to move the red ball from one cell to another cell.
|
|
|
|
</p>
|
|
<p>
|
|
Click on the photos to link them with lines.
|
|
</p>
|
|
|
|
|
|
<center><table>
|
|
<tr>
|
|
<td><div id="anim_config"></div></td>
|
|
<td>
|
|
<div><input type="button" value="Take a Picture" id="addSituation" /></div>
|
|
<div id="messageConfig"> </div>
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
</center>
|
|
<div style="font-weight: bold; margin-top: 1em; text-align: center">Photos:</div>
|
|
<div id="anim_container">
|
|
<div id="anim_graph"></div>
|
|
</div>
|
|
<img src="icon.png" style="display:none">
|
|
</div>
|
|
</div><!-- task -->
|
|
<div id="solution">
|
|
|
|
<h2>Solution</h2>
|
|
|
|
<p class="easy medium">We take a picture for each of <span class="easy">4</span><span class="medium hard">5</span> possible positions of the ball. To find your way easily, you can arrange the photos in the gray frame depending on the position of the ball in each photo, as shown below. We can then add lines between the photos describing positions where the ball has moved only one square.</p>
|
|
|
|
<p class="hard">We take a picture for each of the 6 possible configurations of the two marbles. To find your way easily, we can organize the photos. For example, we can make a first column with the photos having a ball in the box at the top left, and a second column with the photos having no ball in this box. You can also sort the photos inside the column, according to the filling of the other boxes. We can then add the features corresponding to the possible displacements of the balls.</p>
|
|
|
|
<p>
|
|
<img class="easy" src="Sol_easy_1.png">
|
|
<img class="medium" src="Sol_medium_1.png">
|
|
<img class="hard" src="Sol_hard_1.png">
|
|
</p>
|
|
|
|
<p>To be sure you have not forgotten any features, you can check the lines that start from each photo. For a given photo, we count <span class="easy medium">the number of white squares around the ball</span><span class="hard">the number of white boxes around the first ball, to which is added the number of white boxes around the second ball</span>. <span class="easy medium">This number</span><span class="hard">Total</span> must correspond to the number of lines that are connected to this photo, since this corresponds to the number of possible displacements.</p>
|
|
|
|
<h2>It's computer science !</h2>
|
|
|
|
<p>This topic illustrates how to represent situations (photos of a state) and transitions (displacement of a marble) in the form of a <b>graph</b>, that is to say, a set of objects, some of which are connected to each other by lines. It is very interesting to reduce a problem to a graphical view, because there are many very efficient algorithms for dealing with problems expressed by graphs.</p>
|
|
|
|
<p>Some problems naturally appear as a graph, such as finding a way to travel from one city to another: the graph is then made up of the cities and roads that connect them. In other problems, on the contrary, the graph is not really visible at first glance. We then speak of <b> implicit graph</b>.
|
|
<p>The expertise of a programmer is to be able to detect that a problem that does not look like a graph problem can still be expressed as a graph. Such a programmer can then, instead of developing an ad-hoc and inefficient algorithm, rely on a standard and highly efficient graphing algorithm.</p>
|
|
|
|
|
|
</div> <!-- task-solution -->
|
|
</body>
|
|
</html>
|