ICPC 2011 - A. To Add or to Multiply
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2011/A-to-add-or-to-multiply. Edit
competitive_programming/icpc/2011/A-to-add-or-to-multiply/solution.tex to update the written solution and
competitive_programming/icpc/2011/A-to-add-or-to-multiply/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem A
To Add or to Multiply
Problem ID: addmul
The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer
needs. Processors of the a-C-m family (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different
operations:
A add a
M multiply by m
The processor receives an integer, executes a sequence of A and M operations (the program) that modifies the input, and
outputs the result. For example, the 1-C-2 processor executing the program AAAM with the input 2 yields the output
10 (the computation is 2 → 3 → 4 → 5 → 10), while the 5-C-3 processor yields 51 with the same program and input
(2 → 7 → 12 → 17 → 51).
You are an a-C-m programmer assigned to a top secret project. This means that you have not been told the precise
computation your program should perform. But you are given particular values p, q, r, and s and the following
conditions:
1. The input is guaranteed to be a number between p and q.
2. The output must be some number between r and s.
Given an a-C-m processor and the numbers p, q, r, and s, your job is to construct the shortest a-C-m program which,
for every input x such that p ≤ x ≤ q, yields some output y such that r ≤ y ≤ s. If there is more than one program of
minimum length, choose the one that come first lexicographically, treating each program as a string of As and Ms.
Input
The input contains several test cases. Each test case is given by a line with the six integers a, m, p, q, r, and s as
described above (1 ≤ a, m, p, q, r, s ≤ 109 , p ≤ q and r ≤ s).
The last test case is followed by a line with six zeros.
Output
For each test case, display its case number followed by the best program as described above. Display the word
“empty” if the best program uses no operations. Display the word “impossible” if there is no program meeting
the specifications.
Display the program as a sequence of space-separated strings, alternating between strings of the form “nA” and strings
of the form “nM”, where n > 0. Strings of the former type indicate n consecutive A operations, and strings of the
latter type indicate n consecutive M operations.
Follow the format of the sample output.
ICPC 2011 World Finals Problem A: To Add or to Multiply
Sample input Output for the Sample Input
1 2 2 3 10 20 Case 1: 1A 2M
1 3 2 3 22 33 Case 2: 1M 2A 1M
3 2 2 3 4 5 Case 3: impossible
5 3 2 3 2 3 Case 4: empty
0 0 0 0 0 0
ICPC 2011 World Finals Problem A: To Add or to Multiply
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2011\\A. To Add or to Multiply}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Write the structural observations that make the problem tractable.
\item State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
\item If the constraints matter, explain exactly which part of the solution they enable.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Describe the data structures and the state maintained by the algorithm.
\item Explain the processing order and why it is sufficient.
\item Mention corner cases explicitly if they affect the implementation.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
State the first key claim.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Lemma 2.}
State the next claim if needed.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
Combine the lemmas and finish the argument.
\section*{Complexity Analysis}
State the running time and memory usage in terms of the input size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Mention any non-obvious implementation detail that is easy to get wrong.
\item Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}