C. Divide by Three

Codeforces

IDCF792C

Time1000ms

Memory256MB

Difficulty—

dpgreedymathnumber theory

English · Original

Chinese · Translation

Formal · Original

A positive integer number _n_ is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a _beautiful_ number by erasing some of the digits, and you want to erase as few digits as possible. The number is called beautiful if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 3. For example, _0_, _99_, _10110_ are beautiful numbers, and _00_, _03_, _122_ are not. Write a program which for the given _n_ will find a beautiful number such that _n_ can be transformed into this number by erasing as few digits as possible. You can erase an arbitraty set of digits. For example, they don't have to go one after another in the number _n_. If it's impossible to obtain a beautiful number, print _\-1_. If there are multiple answers, print any of them. ## Input The first line of input contains _n_ — a positive integer number without leading zeroes (1 ≤ _n_ < 10100000). ## Output Print one number — any beautiful number obtained by erasing as few as possible digits. If there is no answer, print - 1. [samples] ## Note In the first example it is enough to erase only the first digit to obtain a multiple of 3. But if we erase the first digit, then we obtain a number with a leading zero. So the minimum number of digits to be erased is two.

一块黑板上写有一个正整数 #cf_span[n]，它至多包含 #cf_span[105] 位数字。你需要通过擦除一些数字将其变为一个 _美丽的_ 数字，并希望擦除尽可能少的数字。一个数字被称为美丽的，当且仅当它至少包含一位数字、没有前导零，且是 #cf_span[3] 的倍数。例如，_0_、_99_、_10110_ 是美丽的数字，而 _00_、_03_、_122_ 不是。请编写一个程序，对于给定的 #cf_span[n]，找出一个美丽的数字，使得可以通过擦除尽可能少的数字将 #cf_span[n] 转换为该数字。你可以任意选择一组数字进行擦除（例如，它们不必在 #cf_span[n] 中连续出现）。如果无法得到一个美丽的数字，请输出 _-1_。如果有多个答案，请输出其中任意一个。输入的第一行包含 #cf_span[n] —— 一个没有前导零的正整数（#cf_span[1 ≤ n < 10100000]）。输出一个数字——通过擦除尽可能少的数字得到的任意一个美丽的数字。如果没有答案，请输出 #cf_span[ - 1]。在第一个例子中，只需擦除第一个数字即可得到一个 #cf_span[3] 的倍数。但如果我们擦除第一个数字，就会得到一个带有前导零的数字。因此，最少需要擦除两个数字。 ## Input 输入的第一行包含 #cf_span[n] —— 一个没有前导零的正整数（#cf_span[1 ≤ n < 10100000]）。 ## Output 输出一个数字——通过擦除尽可能少的数字得到的任意一个美丽的数字。如果没有答案，请输出 #cf_span[ - 1]。 [samples] ## Note 在第一个例子中，只需擦除第一个数字即可得到一个 #cf_span[3] 的倍数。但如果我们擦除第一个数字，就会得到一个带有前导零的数字。因此，最少需要擦除两个数字。

**Definitions** Let $ n $ be a string of digits representing a positive integer, with $ 1 \leq |n| \leq 10^5 $, and no leading zeros. A **beautiful number** is a non-empty string $ b $ such that: - $ b $ has no leading zeros (i.e., if $ |b| > 1 $, then $ b[0] \neq '0' $), - The integer value of $ b $ is divisible by 3. **Constraints** - $ n $ is given as a decimal string with no leading zeros. - The goal is to delete the **minimum number of digits** from $ n $ to form a beautiful number $ b $. - Digits may be deleted arbitrarily (not necessarily contiguous). **Objective** Find any beautiful number $ b $ obtainable by deleting as few digits as possible from $ n $. If no such $ b $ exists, output $ -1 $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Divide by Three",
    "description": {
      "content": "A positive integer number _n_ is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a _beautiful_ number by erasing some of the digits, and you want to era",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF792C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A positive integer number _n_ is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a _beautiful_ number by erasing some of the digits, and you want to era...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一块黑板上写有一个正整数 #cf_span[n]，它至多包含 #cf_span[105] 位数字。你需要通过擦除一些数字将其变为一个 _美丽的_ 数字，并希望擦除尽可能少的数字。\n\n一个数字被称为美丽的，当且仅当它至少包含一位数字、没有前导零，且是 #cf_span[3] 的倍数。例如，_0_、_99_、_10110_ 是美丽的数字，而 _00_、_03_、_122_ 不是。\n\n请编写一个程序，对...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n $ be a string of digits representing a positive integer, with $ 1 \\leq |n| \\leq 10^5 $, and no leading zeros.  \n\nA **beautiful number** is a non-empty string $ b $ such that:...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments