The PIN of a door lock has L digits and may start with 0.
Looking at the keypad, k of the digit keys are worn.
The PIN is made only of the digits on worn keys, and the digit of every worn key is used at least once.
This lock does not let you press the same digit twice in a row, so any two neighbouring digits of the PIN are different.
The owner only remembers that the digits of the PIN add up to S.
Print on the first line how many PINs satisfy all of these conditions.
If there is at least one, print the smallest of them (as a number) on the second line and the largest on the third line.
Write a PIN with all L digits, keeping its leading zeros.
If exactly one PIN fits, write it on both the second and the third line.
If none fits, print only 0 on the first line.
Input
The first line has L, k and S separated by single spaces. The second line has the k digits of the worn keys separated by single spaces. The digits are between 0 and 9, all different, and in no particular order. 1 ≤ L ≤ 5, 1 ≤ k ≤ 10, 0 ≤ S ≤ 45
Output
The number of PINs that fit on the first line. If there is at least one, the smallest PIN on the second line and the largest on the third (each with L digits)
Example 1 · stdin
4 2 14
0 7
stdout
2
0707
7070
Example 2 · stdin
3 2 3
1 2
stdout
0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
When the conditions are hard to solve with one formula, generate every candidate and test each one. Here there are 10^L of them, from 00…0 to 99…9, and L is at most 5, so at most 100,000. Trap one: a PIN is not a number but a row of L digits. Starting the loop at 10^(L−1) misses every answer that starts with 0, such as 0707 in the first example. Trap two: taking digits with while (x > 0) stops before the leading zeros. In the second example it sees only the 1 and 2 of 12 (= 012) and counts it as matching worn keys 1 and 2, so take exactly L digits. Trap three: 'uses only worn keys' and 'uses every worn key' are different conditions and both must be checked. With worn keys 1, 2, 3, counting 121 is wrong. Python checks both at once by comparing character sets: set(pin) != worn. Trap four: if you keep the answer as a number and print it as is, 0707 comes out as 707. Padding with zeros is spelled differently in each language: Python f"{code:0{length}d}", JavaScript/TypeScript String(code).padStart(length, "0"), Java String.format("%0" + length + "d", code), C# code.ToString("D" + length), C printf("%0*d", length, code) (the width is passed as the argument for *), C++ std::setfill('0') << std::setw(length) (setw applies only to the very next value, so repeat it for each value), Craykon ("" + code).PadLeft(length, "0").
Pythonmain.py · 22 lines
length, k, target = map(int, input().split())worn = set(input().split()) # 닳은 키를 글자 집합으로: {"0", "7"}count = 0first = last = ""for code in range(10 ** length): # 0부터: 0으로 시작하는 비밀번호도 있다 pin = f"{code:0{length}d}" # 앞을 0으로 채워 length자리로 if set(pin) != worn: # 닳은 키만, 그리고 빠짐없이 continue if any(a == b for a, b in zip(pin, pin[1:])): # 이웃한 자리가 같으면 안 된다 continue if sum(map(int, pin)) != target: continue count += 1 if count == 1: first = pin last = pin # 작은 수부터 보므로 마지막에 본 것이 가장 크다print(count)if count > 0: print(first) print(last)
JavaScriptmain.js · 33 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [length, , target] = lines[0].trim().split(/\s+/).map(Number);const worn = lines[1].trim().split(/\s+/).map(Number);// 비밀번호 한 개가 세 조건을 모두 지키는지 본다function fits(pin) { const used = new Set(pin); // 문자열을 넣으면 글자 하나하나가 들어간다 if (used.size !== worn.length || !worn.every((d) => used.has(String(d)))) return false; let sum = 0; for (let i = 0; i < pin.length; i++) { if (i > 0 && pin[i] === pin[i - 1]) return false; // 이웃한 자리가 같으면 안 된다 sum += Number(pin[i]); } return sum === target;}let count = 0;let first = "";let last = "";// 0부터: 0으로 시작하는 비밀번호도 있다for (let code = 0; code < 10 ** length; code++) { const pin = String(code).padStart(length, "0"); // 앞을 0으로 채워 length자리로 if (!fits(pin)) continue; count++; if (count === 1) first = pin; last = pin; // 작은 수부터 보므로 마지막에 본 것이 가장 크다}console.log(count);if (count > 0) { console.log(first); console.log(last);}
TypeScriptmain.ts · 35 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [length, , target] = lines[0].trim().split(/\s+/).map(Number);const worn: number[] = lines[1].trim().split(/\s+/).map(Number);// 비밀번호 한 개가 세 조건을 모두 지키는지 본다function fits(pin: string): boolean { const used = new Set<string>(pin); // 문자열을 넣으면 글자 하나하나가 들어간다 if (used.size !== worn.length || !worn.every((d) => used.has(String(d)))) return false; let sum = 0; for (let i = 0; i < pin.length; i++) { if (i > 0 && pin[i] === pin[i - 1]) return false; // 이웃한 자리가 같으면 안 된다 sum += Number(pin[i]); } return sum === target;}let count = 0;let first = "";let last = "";// 0부터: 0으로 시작하는 비밀번호도 있다for (let code = 0; code < 10 ** length; code++) { const pin: string = String(code).padStart(length, "0"); // 앞을 0으로 채워 length자리로 if (!fits(pin)) continue; count++; if (count === 1) first = pin; last = pin; // 작은 수부터 보므로 마지막에 본 것이 가장 크다}console.log(count);if (count > 0) { console.log(first); console.log(last);}
JavaMain.java · 49 lines
import java.util.*;public class Main { static int length, target; static boolean[] worn = new boolean[10]; // 비밀번호 한 개가 세 조건을 모두 지키는지 본다 static boolean fits(int code) { boolean[] used = new boolean[10]; int sum = 0, prev = -1, x = code; // while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; // 닳지 않은 키이거나 이웃과 같다 used[d] = true; sum += d; prev = d; } for (int d = 0; d < 10; d++) if (worn[d] && !used[d]) return false; // 닳았는데 쓰지 않은 키 return sum == target; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); length = sc.nextInt(); int k = sc.nextInt(); target = sc.nextInt(); for (int i = 0; i < k; i++) worn[sc.nextInt()] = true; int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) { // 0부터: 0으로 시작하는 비밀번호도 있다 if (!fits(code)) continue; count++; if (first < 0) first = code; last = code; } System.out.println(count); if (count > 0) { String format = "%0" + length + "d"; // 앞을 0으로 채워 length자리로 System.out.println(String.format(format, first)); System.out.println(String.format(format, last)); } }}
C#Main.cs · 56 lines
using System;using System.Linq;class Program{ static int length, target; static bool[] worn = new bool[10]; // 비밀번호 한 개가 세 조건을 모두 지키는지 본다 static bool Fits(int code) { var used = new bool[10]; int sum = 0, prev = -1, x = code; // while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; // 닳지 않은 키이거나 이웃과 같다 used[d] = true; sum += d; prev = d; } for (int d = 0; d < 10; d++) if (worn[d] && !used[d]) return false; // 닳았는데 쓰지 않은 키 return sum == target; } static void Main() { int[] head = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); length = head[0]; target = head[2]; foreach (string s in Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries)) worn[int.Parse(s)] = true; int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) // 0부터: 0으로 시작하는 비밀번호도 있다 { if (!Fits(code)) continue; count++; if (first < 0) first = code; last = code; } Console.WriteLine(count); if (count > 0) { string format = "D" + length; // "D4"는 앞을 0으로 채운 4자리 Console.WriteLine(first.ToString(format)); Console.WriteLine(last.ToString(format)); } }}
C++main.cpp · 49 lines
#include <array>#include <iomanip>#include <iostream>int length, target;std::array<bool, 10> worn{};// 비밀번호 한 개가 세 조건을 모두 지키는지 본다bool fits(int code) { std::array<bool, 10> used{}; int sum = 0, prev = -1, x = code; // while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; // 닳지 않은 키이거나 이웃과 같다 used[d] = true; sum += d; prev = d; } return used == worn && sum == target; // 닳은 키를 빠짐없이 썼는지는 배열끼리 견준다}int main() { int k; std::cin >> length >> k >> target; for (int i = 0; i < k; i++) { int d; std::cin >> d; worn[d] = true; } int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) { // 0부터: 0으로 시작하는 비밀번호도 있다 if (!fits(code)) continue; count++; if (first < 0) first = code; last = code; } std::cout << count << '\n'; if (count > 0) { // setfill은 한 번 정하면 계속 가지만 setw는 바로 다음 값 하나에만 듣는다 std::cout << std::setfill('0') << std::setw(length) << first << '\n' << std::setw(length) << last << '\n'; }}
Cmain.c · 51 lines
#include <stdbool.h>#include <stdio.h>static int length, target;static bool worn[10];/* 비밀번호 한 개가 세 조건을 모두 지키는지 본다 */static bool fits(int code) { bool used[10] = {false}; int sum = 0, prev = -1, x = code; /* while (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 */ for (int i = 0; i < length; i++) { int d = x % 10; x /= 10; if (!worn[d] || d == prev) return false; /* 닳지 않은 키이거나 이웃과 같다 */ used[d] = true; sum += d; prev = d; } for (int d = 0; d < 10; d++) if (worn[d] && !used[d]) return false; /* 닳았는데 쓰지 않은 키 */ return sum == target;}int main(void) { int k; if (scanf("%d %d %d", &length, &k, &target) != 3) return 0; for (int i = 0; i < k; i++) { int d; if (scanf("%d", &d) != 1) return 0; worn[d] = true; } int limit = 1; for (int i = 0; i < length; i++) limit *= 10; int count = 0, first = -1, last = -1; for (int code = 0; code < limit; code++) { /* 0부터: 0으로 시작하는 비밀번호도 있다 */ if (!fits(code)) continue; count++; if (first < 0) first = code; last = code; } printf("%d\n", count); if (count > 0) { /* %0*d: 너비를 인수로 받아 앞을 0으로 채운다 */ printf("%0*d\n", length, first); printf("%0*d\n", length, last); } return 0;}
Craykonmain.cray · 68 lines
// 비밀번호 한 개가 세 조건을 모두 지키는지 본다맞나(code, length, target, worn){ used = NewList(10, false); sum = 0; prev = -1; x = code; // 동안 (x > 0)이 아니라 꼭 length번: 앞자리의 0도 자리다 for (i = 0; i < length; i++) { d = x % 10; x = Mathf.Quot(x, 10); if (!worn[d] || d == prev) { return false; // 닳지 않은 키이거나 이웃과 같다 } used[d] = true; sum += d; prev = d; } for (d = 0; d < 10; d++) { if (worn[d] && !used[d]) { return false; // 닳았는데 쓰지 않은 키 } } return sum == target;}head = Console.ReadNumbers();length = head[0];target = head[2];worn = NewList(10, false);foreach (d in Console.ReadNumbers()){ worn[d] = true;}limit = 1;for (i = 0; i < length; i++){ limit *= 10;}count = 0;first = -1;last = -1;// 0부터: 0으로 시작하는 비밀번호도 있다for (code = 0; code < limit; code++){ if (맞나(code, length, target, worn)) { count += 1; if (first < 0) { first = code; } last = code; }}Console.WriteLine(count);if (count > 0){ // 수를 문자열로 바꾼 다음 앞을 0으로 채워 length자리로 Console.WriteLine(("" + first).PadLeft(length, "0")); Console.WriteLine(("" + last).PadLeft(length, "0"));}