Table of Contents
题解
代码示例
Home Web Front-end HTML Tutorial Codeforces Round #256 (Div. 2)D 2 points answer_html/css_WEB-ITnose

Codeforces Round #256 (Div. 2)D 2 points answer_html/css_WEB-ITnose

Jun 24, 2016 pm 12:01 PM
round Answer

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
Copy after login

output

input

2 3 4
Copy after login

output

input

1 10 5
Copy after login

output

Note

A 2?×?3 multiplication table looks like this:

1 2 32 4 6
Copy after login

题解

题目意思是,从一个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;}
Copy after login


Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Eggman's Party uncovers the answers to the troublemaker's questions Eggman's Party uncovers the answers to the troublemaker's questions Feb 22, 2024 pm 01:10 PM

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?

What does round mean in php What does round mean in php Mar 10, 2023 am 10:04 AM

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);".

How to divide and round using PHP's round() function How to divide and round using PHP's round() function Mar 21, 2023 pm 04:32 PM

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.

Samsung Galaxy Z Flip6 review: Simple design and practical experience, is the answer to the discounted version? ! Samsung Galaxy Z Flip6 review: Simple design and practical experience, is the answer to the discounted version? ! Jul 30, 2024 pm 12:54 PM

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.

Ant New Village Today's Answer 2.22 Ant New Village Today's Answer 2.22 Feb 22, 2024 pm 01:10 PM

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.

Ant New Village Today's Answer 3.7 Ant New Village Today's Answer 3.7 Mar 07, 2024 am 11:37 AM

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.

Ant Manor Today's Answer 3.11 Ant Manor Today's Answer 3.11 Mar 10, 2024 am 11:34 AM

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

Ant Manor Today's Answer 2.24 Ant Manor Today's Answer 2.24 Feb 23, 2024 pm 01:13 PM

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

See all articles