[BaekJun, C++] 1018: Movie Director

 

https://www.acmicpc.net/problem/1436

문제

It is said that 666 represents the end of the world. Therefore, many blockbuster movies often use titles containing the number 666. Director Sean is in charge of a movie series called "The End of the World." When George Lucas created Star Wars, he named the movies as Star Wars 1, Star Wars 2, Star Wars 3, Star Wars 4, Star Wars 5, and Star Wars 6, and similarly, Peter Jackson named his movies as The Lord of the Rings 1, The Lord of the Rings 2, The Lord of the Rings 3 when making "The Lord of the Rings." However, Sean decided to make his movie titles a bit different to demonstrate that he surpasses George Lucas and Peter Jackson.

The term "end of the world number" refers to a number with at least three consecutive 6s. The smallest end of the world number is 666, and the next larger numbers are 1666, 2666, 3666, and so on. Therefore, Sean's first movie's title will be "The End of the World 666," and the second movie's title will be "The End of the World 1666," and so on. In general, the title of the Nth movie made by Sean is "The End of the World" followed by the Nth smallest end of the world number.

Input

the first line is N, N is an integer less than or equal to 10,000

Output

It prints the Nth movie title

 

Code

#include <string> #include <vector> #include <algorithm> #include <iostream> using namespace std; int n; int main() { cin >> n; int cnt = 0; int i = 1; while (n != cnt) { int temp = i; while (temp) { if (temp % 1000 == 666) { // check if the last 3 digits are 666 cnt++;//if they are, break and add count break; } else { temp = temp / 10; //if not, divide to check the next 3 consecutive 3 digits } } i++;// check every positive integer starting from 1 } cout << i - 1; }

It was difficult to find if there are three consecutive 6's while it's easy to find just one


but just check if the nubmer mod 1000 is 666 and keep on dividing by 10

so it's a Brute Force Problem


 

Time Complexity

O(n^2)

 

Space Complexity
O(1)


Comments

Post a Comment

Popular posts from this blog

[BaekJun, C++] 1018: Repainting a Chess Board

Image
  https://www.acmicpc.net/problem/1018 Problem Jimin found an M×N sized board in his mansion that is divided into MN unit squares. Some of these squares are painted black, while the rest are white. Jimin wants to cut the board into 8×8-sized chessboards. A chessboard must have alternating black and white squares. Specifically, each cell should be painted either black or white, and two squares sharing an edge must have different colors. Therefore, there are only two ways to color the chessboard. One has the top-left square white, and the other has it black. There is no guarantee that the board is already colored like a chessboard, so Jimin plans to cut it into 8×8 pieces and repaint some of the squares. Naturally, he can choose the 8×8 sections from anywhere. Your task is to write a program that calculates the minimum number of squares that Jimin needs to repaint. Input The first line contains two integers, N and M. N and M are natural numbers greater than or equal to 8 and less tha...
Read more

Binary Search: The Efficient Solution for Sorted Arrays

Image
Binary Search is a powerful algorithm that allows you to efficiently search for a target element within a sorted array. This algorithm works by repeatedly dividing the search space in half, which makes it an extremely efficient method for finding elements in large, ordered datasets. The Prerequisite: Sorted Array Before we dive into the details of Binary Search, it's important to understand that this algorithm can only be applied to sorted arrays. If the array is not sorted, Binary Search will not work correctly, and you may end up with incorrect results. The reason for this requirement is that Binary Search relies on the fact that the array is already in order. This allows the algorithm to make informed decisions about which half of the array to search next, based on the comparison between the target element and the middle element of the current search space. The Binary Search Algorithm The Binary Search algorithm follows these steps: 1. Initialize the search space: Set the lowe...
Read more

[BaekJun,C++]1929: finding primes

Image
  https://www.acmicpc.net/problem/1929 Problem: Write a program that prints all prime numbers between M and N, inclusive. Input: The natural numbers M and N are given on the first line, separated by a space. (1 ≤ M ≤ N ≤ 1,000,000) The input guarantees that there is at least one prime number between M and N. Output: Print the prime numbers in ascending order, one per line. #include < iostream > #include < cstdio > #include < algorithm > using namespace std; int m, n; int main(void) { cin >> m >> n; int size = n - m + 1; int* prime = new int[n + 1]; prime[1] = 0; for (int i = 2; i < n + 1; i++) { prime[i] = 1; } //eratostheneses sieve for (int i = 2; i < n + 1;i++) { if (prime[i] == 0) { continue;// continue, break } else { for (int j = i * 2; j < n + 1; j += i) { //you don't always have to incerase the index by 1 prime[j] = 0; } } ...
Read more