Simulation
Author: Darren Yao
Contributors: Allen Li, Siyong Huang, Juheon Rhee
Directly simulating the problem statement.
Resources | ||||
---|---|---|---|---|
IUSACO | This module is based on Chapter 5 of Darren Yao's book |
Since there's no formal algorithm involved, the intent of the problem is to assess competence with one's programming language of choice and knowledge of built-in data structures. At least in USACO Bronze, when a problem statement says to find the end result of some process, or to find when something occurs, it's usually sufficient to simulate the process naively.
Example 1
Focus Problem – try your best to solve this problem before continuing!
Solution
We can simulate the process. Store an array that keeps track of which shell is at which location, and Bessie's swapping can be simulated by swapping elements in the array. Then, we can count how many times Elsie guesses each shell, and the maximum points she can earn is the maximum amount of times a shell is guessed.
#include <algorithm>#include <cstdio>#include <vector>using std::vector;int main() {freopen("shell.in", "r", stdin);int n;
Example 2
Focus Problem – try your best to solve this problem before continuing!
Solution
We can simulate the process of pouring buckets. The amount of milk poured from bucket to bucket is the smaller of the amount of milk in bucket (which is ) and the remaining space in bucket (which is ). We can just handle all of these operations in order, using an array to store the maximum capacities of each bucket, and an array to store the current milk level in each bucket, which we update during the process. Example code is below.
#include <algorithm>#include <cstdio>#include <iostream>#include <vector>using namespace std;const int N = 3; // The number of buckets (which is 3)const int TURN_NUM = 100;
Problems
Easier
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Bronze | Easy | Show TagsSimulation | |||
Bronze | Easy | Show TagsSimulation | |||
Bronze | Easy | Show TagsSimulation | |||
Bronze | Easy | Show TagsSimulation | |||
Bronze | Easy | Show TagsSimulation |
Harder
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Bronze | Normal | Show TagsSimulation | |||
Bronze | Normal | Show TagsSimulation | |||
Bronze | Normal | Show TagsSimulation | |||
Bronze | Normal | Show TagsSimulation | |||
Bronze | Normal | Show TagsSimulation | |||
Old Bronze | Hard | Show TagsSimulation | |||
Bronze | Hard | Show TagsSimulation | |||
Bronze | Very Hard | Show TagsSimulation |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!