


Codeforces Round #256 (Div. 2)D 2 points answer_html/css_WEB-ITnose
D. Multiplication Table
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Bizon the Champion isn't just charming, he also is very smart.
While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann?×?m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?
Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.
Input
The single line contains integers n, m and k (1?≤?n,?m?≤?5·105; 1?≤?k?≤?n·m).
Output
Print the k-th largest number in a n?×?m multiplication table.
Sample test(s)
input
2 2 2
output
input
2 3 4
output
input
1 10 5
output
Note
A 2?×?3 multiplication table looks like this:
1 2 32 4 6
题解
题目意思是,从一个n*m的乘法表(不要问我乘法表是什么)中选出第k小数(相同的数字会计算多次)。
比如样例 2 3 4
乘法表为
1 2 3
2 3 4
非减序列是:1, 2, 2, 3, 3, 4。第4个数字是3,所以输出3。
一开始我想到的是搜索,从n*m开始搜索,后来发现状态实在太多而且即便是搜索,时间复杂度是O(N * M)。
正确的解法是二分。二分答案(边界是[1, n * m]),然后在乘法表中去找比他小的数。因为乘法表是一个有规律的数表,所以针对每一列直接O(1)计算即可,总共计算N次。
总的时间复杂度是O(N * 2 * log(N))。
代码示例
/*****************************************************************************# COPYRIGHT NOTICE# Copyright (c) 2014 All rights reserved# ----Stay Hungry Stay Foolish----## @author :Shen# @name :D# @file :D.cpp# @date :2014/07/17 22:47# @algorithm :Binary Search******************************************************************************///#pragma GCC optimize ("O2")//#pragma comment(linker, "/STACK:1024000000,1024000000")#include <bits/stdc++.h>using namespace std;template<class T>inline bool updateMin(T& a, T b){ return a > b ? a = b, 1: 0; }template<class T>inline bool updateMax(T& a, T b){ return a < b ? a = b, 1: 0; }typedef long long int64;int64 n, m, k;bool check(int64 x){ int64 res = 0; for (int i = 1; i <= n; i++) { int64 tmp = min(i * m, x); res += tmp / i; } return res < k;}// 从小往大 计数,第k个int64 BinarySearch(int64 l, int64 r){ while (l < r) { int64 mid = (l + r) / 2; //cout << l << " " << mid << " " << r << endl; //cout << "check result: " << check(mid); if (check(mid)) l = mid + 1; else r = mid; //system("pause"); } return r;}int main(){ cin >> n >> m >> k; int64 Right = n * m, Left = 1; int64 ans = BinarySearch(Left, Right); cout << ans; return 0;}

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Eggboy Party has recently been very popular in finding troublemakers to answer questions. What are the answers to the 20 questions? Many players are afraid of making mistakes, so they search. In fact, these questions are very basic, and the answers have been summarized. Let’s take a look. Read this summary of answers to all 20 questions about spotting the troublemakers at Eggman's Party, it will definitely help you. Eggman Party Strategy Guide Eggman Party Unlocks Troublemaker Answers 1. As a scheming eggman, which of the following is your skill effect? Answer: It can make the knocked down Eggman invisible 2. After a game fails, the following Which behavior is wrong? Answer: Blaming Eggman for the failure. 3. Which of the following statements about emergency discussions is correct? Answer: When there is important information, you can initiate an emergency discussion to tell everyone 4. Which of the following is in the game?

In PHP, round means "rounding" and is a built-in function that converts floating point numbers into integers. This function can round floating point numbers and return an integer value of type float. The syntax is "round(number, precision,mode);".

The round() function is a very useful function in the PHP number formatting library, which can round floating point numbers to a specified number of decimal places. However, since PHP's division operation may suffer from infinite decimals or loss of precision, rounding of the divisor is also necessary. Next, we will explain in detail how to use PHP's round() function to divide and round.

In the field of folding screens, small folding screens are also loved by many young users due to their lightweight, portable, exquisite and compact fashion attributes. In the previous review of the Samsung Galaxy Z Fold6 large folding screen, I gave it a "more square and more AI" evaluation. The small folding screen released at the same time, Samsung Galaxy Z Flip 6, has also attracted much attention. So what will it be like? Today, let’s unlock this new fashion product together. "Light" design: The fashionable appearance on the fingertips is the same as Galaxy Z Fold 6. The Galaxy Z Flip 6 body adopts a square design. In the unfolded state, the fuselage is slender than the average candy bar machine. The front and rear are connected by a straight-sided middle frame, and the four R corners retain a rounded shape.

Which of the following occupations specializes in repairing damaged cosmetic products? Ant New Village’s today’s question. Today’s answer in Ant New Village is a makeup repairer. Some expensive cosmetics are more cost-effective to repair and reuse. For more details, follow the editor to read this article on Ant New Village in 2024. Today’s answer is the latest 2.22, I hope it can help you. Ant New Village Today's Answers Latest Ant New Village Today's Answers 2.22 Question: Which of the following professions specializes in repairing damaged makeup products? Answer: Makeup Restorer Analysis: Makeup restorers are craftsmen who specialize in repairing damaged makeup products. They grind, heat, sterilize, and mold Various processes such as molding and packaging are used to re-repair damaged cosmetic products.

Which of the following occupations is a good helper for scientific baby care? Ant New Village’s today’s question. Ant New Village’s today’s answer is nanny. Nanny is really professional in taking care of babies. Follow the editor to read this Ant New Village’s today’s answer 3.7 for the specific content. The latest 2024, I hope it can help you. Ant New Village Today's Answers Latest Ant New Village Today's Answers 3.7 Question: Which of the following professions is a good helper in scientific child care Answer: Nanny Analysis: A nanny is a good helper in scientific child care, which refers to the use of modern educational concepts and scientific methods Professionals who provide daily care, nursing and education for babies aged 0-3 years old.

What is today’s answer to Ant Manor 3.11? Today's questions are: Who is the protagonist of the idiom "stand out"? Which of the following vegetables has another name "chrysanthemum vegetable"? There are many friends who still don’t know the answer to the question, so the editor below will bring you today’s answers to the latest Ant Manor Chicken 3.11 in 2024. Interested friends, please come and find out together. Summary of today's answers to Ant Manor Today's answers to Ant Manor 3.11 Question 1: Who is the protagonist of the idiom "stand out"? Correct answer: Maosui Ant Manor 3.11 Question 1 answer details Question 2: Which of the following vegetables has another name "chrysanthemum vegetable"? Correct answer: Artemisia Ant Manor 3.11 question 2 answer details Ant Manor daily question How to participate: 1. First open Alipay

What is today’s answer to Ant Manor 2.24? Today’s questions are: In order to prevent the glutinous rice balls from sticking to the bottom of the pot, what should you do? What kind of holiday delicacy is "stars shining in dark clouds, pearls floating in turbid water"? There are many friends who still don’t know the answer to the question, so the editor below will bring you today’s answers to the latest Ant Manor Chicken 2.24 in 2024. Interested friends, please come and find out together. Summary of Ant Manor's Today's Answers Ant Manor's Today's Answers 2.24 Question 1: In order to prevent the glutinous rice balls from sticking to the bottom of the pot, what should be done? Correct answer: Tangyuan under boiling water Ant Manor 2.24 Question 1 answer details Question 2: What kind of holiday delicacy is "stars shining in dark clouds, beads floating in turbid water"? Correct answer: Tangyuan Ant Manor 2.24 question 2 answer details How to participate in the daily question of Ant Manor
