C++ Problem P1161: Turning On the Lights

Click the blue text

Follow us

P1161 Turning On the Lights

Problem Description

On an infinitely long road, there is a row of infinitely long streetlights, numbered as .

Each light can only be in one of two states: on or off. Pressing the switch of a certain light will change its state. If it was on, it will turn off. If it was off, it will turn on.

Initially, all lights are off. Xiao Ming can perform the following operation:

Specify two numbers, (where is a real number, and is a positive integer). Press the switch of the light numbered once. Here, represents the integer part of the real number .

After Xiao Ming has performed operations, he suddenly finds that only one light is on. He wants to know the number of this light, but it is too far away for him to see the number clearly.

Fortunately, Xiao Ming remembers the previous operations. So he comes to you, can you help him calculate the number of the light that is on?

Input Format

The first line contains a positive integer , indicating the number of operations.

Next, there are lines, each containing two numbers, . Here, is a real number with exactly decimal places, and is a positive integer.

Output Format

Only one positive integer, which is the number of the light that is on.

Input Example

#1

3

1.618034 13

2.618034 7

1.000000 21

Output Example

#1

20

Explanation/Hint

Note that .

For the data of , it satisfies ;

For the data of , it satisfies ;

For the data of , it satisfies ;

For the data of , it satisfies , and .

The data guarantees that after performing operations, there is exactly one light on, so no need to check for errors. Also, for all i, the maximum value of does not exceed .

💡 Problem Analysis

• Infinitely long streetlights (theoretically, the light numbers are infinite, but practically only the lights that can be operated on are considered)

• All lights are initially off

• Each operation: given ( a ) (real number, 6 decimal places), ( t ) (positive integer), press the switch of the light numbered

of the light.

• Ultimately, only one light will be on, find its number.

💡 Solution Approach

1️⃣ Determine the maximum range of light numbers:

• Since in each operation, the maximum light number will not exceed the integer part of , the maximum is about (2000000).

• So use a static array (e.g., bool state[2000005]) to represent the state of lights from number 1 to the maximum number (inclusive).

2️⃣ Process each operation:

• For each group ( (a, t) ), calculate the number sequentially, flipping the corresponding light’s state.

3️⃣ Flip operation:

• Initially all are false (off), pressing the switch means state[id] = !state[id].

4️⃣ Find the uniquely lit light:

• Traverse the entire state array to find the unique value that is true (on), and output it.

Mathematical Principle

Floor function (rounding down function):

Represents the largest integer not greater than ( x ) (rounding down).

In fact, ( k × a ) here is floating-point multiplication, so high precision processing is needed to prevent rounding errors.

Code Implementation

#include<iostream>   // Input and output stream#include<cmath>      // floor function (rounding down)#include<cstdio>     // scanf/printf, faster input and output
using namespace std;
const int MAX_ID = 2000005;  // Maximum number range (as guaranteed by the problem)
bool state[MAX_ID] = { false };  // Static array representing the state of lights (false=off, true=on)
int main() {
    int n;
    scanf("%d", &n);  // Read the number of operations
    for (int i = 0; i < n; ++i) {
        double a;
        int t;
        scanf("%lf %d", &a, &t);  // Read a and t
        for (int k = 1; k <= t; ++k) {
            int id = (int)floor(k * a);  // Calculate light number
            state[id] = !state[id];      // Flip the light's state
        }
    }
    // Find the uniquely lit light
    for (int id = 1; id < MAX_ID; ++id) {
        if (state[id]) {
            printf("%d\n", id);  // Output the number
            break;  // The problem guarantees only one light is on, exit once found
        }
    }
    return 0;
}

Click below to read the original text

Direct access to the Luogu problem bank for practice

Key Code Explanation

floor(x)

Gets the largest integer not greater than x (rounding down), defined in <cmath> in C++.

bool

Boolean type, true/false, indicating whether the light is on.

static array

An array with a fixed size allocated at compile time, such as bool state[MAX_ID].

Flip operation

state[id] = !state[id], meaning if it is true (on) it becomes false (off), and vice versa.

scanf/printf

Faster input and output than cin/cout (more efficient for large data inputs).

🔥【Notes】

• Use static arrays,avoiding dynamic allocation, ensuring reasonable space usage (maximum elements about 2000000).

• When reading and calculating floating-point multiplication with double type,do not use floating-point comparison, directly take floor.

• When input/output volume is large,prefer using scanf/printfto avoid timeout.

END

Like

Collect

Share

Explore the forefront of educational technology, empowering future learning!

“Bit Island Education Technology” is committed to using innovative technology to create a more efficient, interesting, and future-oriented learning experience.

• Get the latest educational technology products and course materials

• Learn practical and efficient learning methods and educational concepts

• Understand innovative teaching tools and classroom application cases

• Participate in exclusive activities to win learning benefits

Scan the code to follow us and start your journey in smart education! 👇

BIT ISLAND

Long press to scan

WeChat ID丨bit_island_Terry

WeChat Search丨Bit Island Education Technology