oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

lights Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

lights.html

Problem Description

Rar the Cat has obtained a LED strip filled with N individual LED lights and wants to code them to light up in a certain manner. He at first labels the lights from 1 to N, and then lights the LEDs based on the rules below.

Initially, all the LED lights are turned off. Then for each positive integer not greater than N, (1..N), Rar the Cat toggles all the LED lights which labels are multiples of that number. Toggling a LED light means that if the light was originally on, it will now be turned off. If it was originally off, it would be turned on, akin to flipping a light switch.

As an example: When N is 10, Rar the Cat does the following steps in order:

  1. Initially, all the LED lights are turned off. (Off: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  2. Firstly, Rar the Cat toggles all the lights that are multiples of 1. (On: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  3. Secondly, Rar the Cat toggles all the lights that are multiples of 2. (On: 1, 3, 5, 7, 9 | Off: 2, 4, 6, 8, 10)
  4. Thirdly, Rar the Cat toggles all the lights that are multiples of 3, thereby turning LED 3 and 9 off while turning LED 6 on. (On: 1, 5, 6, 7 | Off: 2, 3, 4, 8, 9, 10)
  5. Fourthly, Rar the Cat toggles all the lights that are multiples of 4, thereby turning LED 4 and 8 on. (On: 1, 4, 5, 6, 7, 8 | Off: 2, 3, 9, 10)
  6. Then, Rar the Cat toggles all the lights that are multiples of 5, thereby turning LED 5 off while turning LED 10 on. (On: 1, 4, 6, 7, 8, 10 | Off: 2, 3, 5, 9)
  7. Next, Rar the Cat toggles all the lights that are multiples of 6, thereby turning LED 6 off. (On: 1, 4, 7, 8, 10 | Off: 2, 3, 5, 6, 9, 10)
  8. Subsequently, Rar the Cat toggles all the lights that are multiples of 7, thereby turning LED 7 off. (On: 1, 4, 8, 10 | Off: 2, 3, 5, 6, 7, 9)
  9. After that, Rar the Cat toggles all the lights that are multiples of 8, thereby turning LED 8 off. (On: 1, 4, 10 | Off: 2, 3, 5, 6, 7, 8, 9)
  10. Finally, Rar the Cat toggles all the lights that are multiples of 9, thereby turning LED 9 on. (On: 1, 4, 9, 10 | Off: 2, 3, 5, 6, 7, 8)
  11. Lastly, Rar the Cat toggles all the lights that are multiples of 10, thereby turning LED 10 off. (On: 1, 4, 9 | Off: 2, 3, 5, 6, 7, 8, 10)

Rar the Cat would like to know how many LED lights are turned on in the LED strip at the end of the day.

Input

Input consists of a single integer, N.

Output

A single integer, denoting how many LED lights are switched on in the LED strip at the end of the day.

Limits

Subtask 1 (9%): 0 < N ≤ 10

Subtask 2 (32%): 0 < N ≤ 1000

Subtask 3 (34%): 0 < N ≤ 1000000

Subtask 4 (25%): 0 < N ≤ 1018 (Please use long long to input)

Subtask 5 (0%): As per sample testcases.

Sample Testcase 1

Input:

10

Output:

3

Sample Testcase 2

This testcase adheres to the limits of subtask 2 to 4 only.

Input:

1000

Output:

31

Sample Testcase 3

This testcase adheres to the limits of subtask 3 and 4 only.

Input:

1000000

Output:

1000

Sample Testcase 4

This testcase adheres to the limits of subtask 4 only.

Input:

964785235727023492

Output:

982234817

lights.pdf

Your browser does not support embedded PDF files. Please download the PDF instead.

lights.docx

Tags

Number Theory, Raffles Cat Helping Contest 2013

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
19101s64MBMinimum
232101s64MBMinimum
334101s64MBMinimum
425201s64MBMinimum
5041s64MBMinimum

Attachments

Attachment Filesize Last Updated
lights_sample.zip987B31 Jan 2013, 15:12:59

Judge Compile Command

g++-8 ans.cpp -o lights -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.